# Scheduling Algorithms for a Hybrid Flow Shop under Uncertainty
## 4 Computation of Schedules
The analysis is illustrated in Figures 8-13. In [PERSON] et al. (2018), we also analyzed the variation in objective function values caused by stochastic components in the metaheuristics for an exemplary week. Steepest Descent and tabu search algorithms provide the same objective value without variation over different runs. In contrast, the random descent algorithms provide more varying schedules. The majority of their values differ within about a quarter of a day, which means that the influence of the stochastic is relatively small in all of the developed metaheuristics of this paper. Figure 8: Optimization results for quantile 60%. Figure 3:0 Optimization results for quantile 90%. Figure 3:1 Optimization results for quantile 80%. Figure 3:2 Optimization results for quantile 92%. The largest computation time over all algorithms and weeks in optimization was about 4 min 45 s for a tabu search (swap) run and the minimum was less than 1 s for the calculation of SPT. The results of \(C_{max}\) are visualized in Figures 8-13. Since the initial solution for the local search and tabu search algorithms is given by SPT, it is not surprising that, over all selected values for the

Figure 3:3 Optimization results for quantile 91%. Figure 3:4 Optimization results for quantile 93%. quantile, the six metaheuristics provide better results than SPT. However, the difference between the \(C_{max}\) values and SPT is respectable. To show how the degree of usage for the machines increases in the production period by using metaheuristics rather than a static approach like SPT, Figure 14 compares one schedule of SPT and one schedule of a metaheuristic, namely the random descent (swap) exemplar for week 12. In contrast, the difference in makespan when comparing only the six metaheuristics for each week is minor. Hence, with this evaluation, we cannot determine which of the metaheuristics will perform best in the application case and which schedule should be applied in practice. Instead, we need simulation to see which solution of the metaheuristics is the most convenient and robust. Due to the high importance in our application case of fulfilling weekly demands as completely as possible, we also evaluate which quantile value for scrap performs best in optimization with regard to the makespan \(C_{max}\). The results are also shown in Figures 8-13. It was found that the quantiles 60%, 80%, 90% and 91% provide similar good results for makespan. In contrast, comparing the \(C_{max}\) values of the 60%, 80%, 90% and 91% group of quantiles, and the 92% and 93% group shows large differences. The differences between 91% and 92% are also illustrated in an exemplary comparison of schedules in Figure 3:5 By increasing the value of the quantile by one percent in this exemplary week, the production volume \(productionvolume_{ij}\) of one specific product increases from around 13 thousand parts to about 60 thousand parts and causes the extreme extension of the makespan shown in Figure 3:6 Considering the results of Figures 8-13, a production with a quantile higher than 91% seems uneconomical in this application case. To guarantee a sufficiently high degree of fulfilled orders and avoid extreme overproduction, we recommend the 91% quantile for the selected period of the application case. Figure 3:7 Comparison of schedules in MS Project for Shortest Processing Time (SPT) (**above**) and Random Descent swap (**below**) in calendar week 12 for quantile 91%. Figure 3:8 Comparison of schedules in MS Project for quantile 91% (**above**) and quantile 92% (**below**) in calendar week 13 with tabu search swap. For comparing the fulfillment of orders and evaluating the makespan under near-realistic conditions for the different quantile values, we use simulation. Figures 16-19 show the variation in four different key indicators of the simulation results per quantile. For each algorithm and each calendar week, we run the simulation 40 times so that, per data point, we take the average of up to 280 simulation runs.