# Scheduling Algorithms for a Hybrid Flow Shop under Uncertainty
## 3 Related Work  
A large number of papers on scheduling in hybrid flow shops are available. Overviews can be found in [PERSON] [6], [PERSON] et al. [7], and [PERSON] et al. [8]. In the following, a selected number of studies that deal with problems related to our problem (see Section 2) are discussed. [PERSON] et al. [9] test three constructive heuristics for the problem \(FHM\), \(((PM^{(k)})_{k=1}^{k})\mid M_{j}\), \(S_{sd}\), \(avail\mid C_{max}\). Based on [PERSON] and [PERSON] [10], they assign the jobs in the processing stages \(i>1\) in the order of completion times of the previous stage. They evaluate that Shortest Processing Time (SPT) provides better results than Longest Processing Time (LPT). A heuristic based on the algorithm of [PERSON] (1977) gave the best results in their study. In the field of metaheuristics, a version of simulated annealing, which is a local search algorithm with the acceptance of setbacks, outperforms a genetic algorithm. In each step, the position of a randomly selected job in the first stage is changed. In the following processing steps, the jobs are dispatched according to the Earliest Completion Times (ECT) using the completion times of the previous step. [PERSON] et al. (2018) present a study dealing with an enormous number of realistic components in the problem \(FHM\), \(((RM^{(k)})_{k=1}^{c})\mid M_{j}\), \(S_{sd}\), \(rn\), \(lag\), \(prec\), \(skip\mid C_{max}\). Yet the study only compares constructive heuristics and finds that NEH, a heuristic first published for flow shops by [PERSON] et al. (2018), provides the best solutions. [PERSON] et al. (2018) compare for \(FH2\), \((RM^{(1)},1^{(2)})\mid M_{j}\mid C_{max}\) sixteen combinations of heuristics. They do not consider skipping stages. To form a production sequence for the first stage, [PERSON] et al. (2018) use the following methods: random sequence, SPT using processing times of the first stage, LPT using process times of the second processing stage, and [PERSON]'s algorithm. Once the queue is created, for each method, the jobs are assigned to the machines of the second processing stage with four different rules. They find that the modified Johnson, rule by planning the second stage according to the Earliest Completion Times (ECT) of the first stage, \(C_{1j}\) performs best. For \(FHM\), \(((PM^{(k)})_{k=1}^{c})\mid S_{sd}\), \(skip\mid C_{max}\) [PERSON] et al. (2018) conduct job sequencing and machine assignment in the same step. All stages \(i\) are scheduled according to the Earliest Completion Times (ECT) of the stage \(i\) itself and they take the arrival times at the stages into account, if \(i>1\), which result from \(C_{i-1j}\). In comparison to other constructive algorithms for their problem and for their test data, this constructive algorithm gives the best results. The paper also uses Iterated Local Search, which outperforms the other tested metaheuristics, like genetic algorithms, up to a number of 80 jobs. Since their problem takes sequence-dependent processing times into account, the problem in combination with applying these algorithms corresponds to unrelated machine problems. In [PERSON] and [PERSON] (2018), several constructive heuristics are compared with simulated annealing (SA) and a genetic algorithm (GA) for the computation of schedules for flow shops with non-unique jobs. Again, SA and GA outperform constructive heuristics but GA does not, in general, do better than SA. [PERSON] and [PERSON] (2018) analyze flow shops with resource constraints where limited resources have to be assigned and a schedule has to be computed simultaneously. They show that an evolutionary algorithm gives good results for this class of scheduling problems. The models in the papers differ from our models in several aspects, e.g., they do not consider machine qualification, stochastic demands and scrap. [PERSON] et al.