## 3 Task Scheduling with Mixed-Integer Programming
### Task Scheduling with the Kinematic Constraints
In the case of \(\mathbb{T}\) that has 120 tasks, run-time is reduced from 499 s to 2.433 s. The average

\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Problem**} & \multicolumn{3}{c}{**Disjunctive [40]**} & \multicolumn{3}{c}{**Our Method**} \\ \cline{2-7}  & **Makespan(s)** & **Run-Time(s)** & **Opt** & **Makespan(s)** & **Run-Time(s)** & **Opt** \\ \hline
2 \(\times\) 2 & 347.9 & 0.50 & 10 & 347.9 & 0.80 & 10 \\
3 \(\times\) 2 & 361.8 & 1.18 & 10 & 320.8 & 1.24 & 10 \\
4 \(\times\) 2 & 420.8 & 9.03 & 10 & 405 & 13.78 & 10 \\
5 \(\times\)



reduced run-time is 73.81% and 98.9% when the number of tasks is more than 60. Through the experimental results, it can be seen that the optimization strategy for subproblems has an advantage in terms of computational time and total elapsed time, especially when the size of the problem is large. It can be expected that this strategy will be optimized to perform tremendous cooking tasks that humans cannot perform. To examine how the subproblem optimization strategy can respond to change of task in the middle of executing, three cases with changing situations are verified. \(\mathbb{T}\) used in this experiment is randomly generated, and it contains four dishes. \(\mathcal{D}_{1}\) contains 10 tasks, \(\mathcal{D}_{2}\) has 15, \(\mathcal{D}_{3}\) has 10, and \(\mathcal{D}_{4}\) has 13. The first case is to add one more plate in the middle of the process. If it is assumed that the robot is working in a restaurant kitchen, this can be happened when a customer orders an additional dish. In Figure 5a, the result of the first case is shown. In the first part of the timeline, only \(\mathcal{D}_{1}\) to \(\mathcal{D}_{3}\) are processed. At the time indicated by the red dashed line, the command was given to start cooking \(\mathcal{D}_{4}\). As shown in the figure, \(\mathcal{D}_{4}\) started successfully and finished the entire process. The second case is when the dish is removed in the middle of the process. This situation can happen when the order is canceled. In Figure 5b, \(\mathcal{D}_{1}\) to \(\mathcal{D}_{4}\) are processed simultaneously by the robot. However, \(\mathcal{D}_{4}\) is removed after the time indicated by the red dashed line. After that, \(\mathcal{D}_{4}\) is not processed at all. The last case is that one dish is restarted after a failure. It is assumed that the situation is such that if the robot drops any ingredients earlier during cooking, then cooking has to be restarted from the beginning. There are two red dashed line in Figure 5c. The line on the left indicates the time at which the robot fails \(\mathcal{D}_{4}\). After recognizing the failure, the restart command is given in the second red line. From this, \(\mathcal{D}_{4}\) is restarted again from the beginning. Through all three cases, it is shown that our algorithm can conduct online planning. Figure 4: The comparison result of the full-sized \(\mathbb{T}\) and segmented \(\mathbb{T}\). Each \(\mathbb{T}\) contains 2 dishes and 30 to 120 tasks. (**a**) The result of the total elapsed time (makespan + run-time). (**b**) The run-time result of the experiment using full-sized \(\mathbb{T}\). (**c**) The run-time result of the experiment using segmented \(\mathbb{T}\). ## 5 Conclusions

In this article, a framework is proposed that can optimally schedule multiple cooking tasks simultaneously. Two mixed-integer programs are formulated to schedule a sequence of tasks and to assign robot arms to tasks. For executing online planning, a subproblem optimization strategy is also proposed. Even though the makespan increased by 6.02%, the run-time was significantly reduced by 98.9%, so the total elapsed time was reduced by 7.89% in a big problem with over 110 tasks. The approach was validated on a real-sized _taskset_ and segmented _taskset_. Moreover online planning was validated in situations where tasks are suddenly reordered. Although this work was proposed for the scheduling of cooking tasks, it can be applied to any

Figure 5: Examples of online planning.