## 3 Task Scheduling with Mixed-Integer Programming
### Task Scheduling with the Kinematic Constraints
Using the collision information, the distance vector \(\mathbb{D}\) is calculated in lines 17 \(\sim\) 18. Stage 2 in Section 3.2 is processed in lines 19 \(\sim\) 25. ### Subproblem Optimization Strategy

This section deals with how to apply the subproblem optimization strategy by dividing one \(\mathbb{T}\) into several. In the previous section, if the whole \(\mathbb{T}\) is applied to the formulation, the actual work cannot begin until all processes have been computed. In the real process, it is necessary to modify or add a task in the middle, so online planning is necessary. We established a strategy to divide \(\mathbb{T}\) to carry out online planning, which was one of the limitations of the previous study [25]. The process of executing the subproblem optimization strategy is in Algorithm 3. Our first goal is to recursively divide \(\mathbb{T}\) into subproblems. \(\mathcal{S}\) is set as the maximum number of tasks in a subproblem in line 2. In line 4, \(\mathcal{G}\) is set as a group of subproblems. Let the \(i\)th component in \(\mathcal{G}\) be defined as \(\mathbb{T}_{i}\). \(\text{Divide}(\mathbb{T}_{i})\) divides \(\mathbb{T}_{i}\) into several proper size of subproblem. The method to divide \(\mathbb{T}_{i}\) is as follows. If \(\mathbb{T}_{i}\) contains \(m\) tasks and \(n\) dishes and \(\mathbb{T}_{i}\) is divided into \(s\) segments, then one segment of \(\mathbb{T}\) contains \(m/s\) tasks when \(m/s\in\mathbb{N}\). In each segment, the tasks located in the first sequence of each dish are gradually filled. In the case of \(m/s\
otin\mathbb{N}\), each segment contains a different number of tasks. Moreover, considering the continuity of tasks, the tasks that cannot be separated from each other should be placed in one segment. If \(\mathbb{T}_{i}\) is divided into \(s\) problems, the outputs become \(\mathbb{T}_{i,1},...,\mathbb{T}_{i,s}\), and these are described in line 8. The each components of outputs \(\mathbb{T}_{i,1},...,\mathbb{T}_{i,s}\) are used as input of Divide in the next step. This step (lines 5 to 10) is executed until the number of tasks in all components of \(\mathcal{G}\) is reduced under \(\mathcal{S}\). After dividing the problem, the optimization of all subproblems should be solved. Let the \(i\)th \(t\), \(L(\mathcal{T})\), and \(R(\mathcal{T})\) be defined as \(t_{seg,i}\), \(L(\mathcal{T})_{seg,i}\), and \(R(\mathcal{T})_{seg,i}\), respectively. Then, the result of optimizations of \(\mathbb{T}_{i}\) is that \(t_{seg,i},L(\mathcal{T})_{seg,i},R(\mathcal{T})_{seg,i}\) can be obtained from SolveOptimization(\(\mathbb{T}_{i}\)). The final results \(t,L(\mathcal{T}),R(\mathcal{T})\) are the stack of each segmented result. ```
1:\(\mathbb{T}=\{(\mathcal{T},\tau,\mathcal{L}_{s},\mathcal{L}_{e},A)\}\)
2:\(\mathcal{S}\leftarrow\) Maximum number of tasks in segmented \(\mathbb{T}\)
3:\(\mathcal{G}\leftarrow\) Group of segmented \(\mathbb{T}\)
4:\(\mathcal{G}\).insert(\(\mathbb{T}\))
5:whileNumberOfTasks(\(\forall\mathbb{T}_{i}\in\mathcal{G}\)) \(>\mathcal{S}\)do
6:\(g\leftarrow\) Empty list
7:for\(\mathbb{T}_{i}\) in \(\mathcal{G}\)do
8:\(\mathbb{T}_{i,1},...,\mathbb{T}_{i,s}\leftarrow\)Divide(\(\mathbb{T}_{i}\))
9:\(g\).insert(\(\mathbb{T}_{i,1},...,\mathbb{T}_{i,s}\))
10:\(\mathcal{G}\gets g\)
11:for\(\mathbb{T}_{i}\) in \(\mathcal{G}\)do
12:\(t_{seg,i},L(\mathcal{T})_{seg,i},R(\mathcal{T})_{seg,i}\leftarrow\)SolveOptimization(\(\mathbb{T}_{i}\))
13:\(t\).insert(\(t_{seg,i}\))
14:\(L(\mathcal{T})\).insert(\(L(\mathcal{T})_{seg,i}\))
15:\(R(\mathcal{T})\).insert(\(R(\mathcal{T})_{seg,i}\))
```

**Algorithm 3**Subproblem optimization strategy. ## 4 Experiment

In this section, the results of the test Algorithms 1 and 3 are presented. In the simulated experiments, the results were observed when changing the number of tasks and the number of segments. The optimization solver used is MOSEK [50], running on a desktop computer with a CPU of Intel Core i7 10700K @ 3.80 GHz and 32 GB of RAM at 2666 MHz.