# Scheduling Algorithms for a Hybrid Flow Shop under Uncertainty
## 3 Related Work
(2018) compare 24 constructive heuristics for \(FHM\), \(((PM^{(k)})_{k=1}^{c})\mid skip\mid C_{max}\) and the evaluation of their experiments shows that two SPT-based and one LPT-based heuristic generate the best schedules according to \(C_{max}\). They do not take unrelated machines into account. [PERSON] et al. (2018) use tabu search for \(FFM\), \(((PM^{(k)})_{k=1}^{c})\mid batch\), \(skip\mid C_{max}\). Since the study works with \(batch\), the algorithm contains many details that cannot be used for this work. [PERSON] et al. (2018) apply tabu search to \(FFM\), \(((PM^{(k)})_{k=1}^{c})\mid block\), \(skip\mid C_{max}\). For their sequence of jobs, they swap two jobs in each iteration. The positions of the two exchanged jobs are saved in the tabu list. To schedule the created sequence, the earliest available machine on every stage is chosen for the job and the stages on which the job has to be produced. [PERSON] et al. (2018) modify a variable neighbourhood search of [PERSON] (2018) for the problem \(FHM\), \(((RM^{(k)})_{k=1}^{c})\mid M_{j}\), \(skip\mid C_{max}\). To change the solutions, one of the six neighborhood strategies is applied randomly:  
* swapping two jobs on one machine;
* swapping three jobs on one machine;
* shifting the position of a job on one machine;
* swapping of two jobs in the schedule (jobs can be scheduled on the same or different machines);
* shifting a job within a processing stage;* relocating of a block of three consecutive jobs to a new position in a processing stage. Thus, no study provides local search and tabu search algorithms for the problem of our paper, which is specified in Section 2. Furthermore, the above mentioned approaches are all based on a fully parametrized deterministic model. One way to optimize stochastic models is the use of sample average approximations, which are used by [PERSON] and [PERSON] [21] with variable neighborhood search to optimize a two-stage flow shop problem describing a real world production process in the metalworking industry. In contrast to our problem, the number of machines is smaller, machine qualification and setup times are not required, and the behavior of orders seems to be more homogeneous. In this case, production data are not used to determine model parameters. Instead, the sampling averaging of simulation results is used to determine the parameters of the optimization problem, which are analyzed with similar methods to the ones that we apply, but tabu lists do not seem to be used. [PERSON] and [PERSON] [22] studied buffering in the area of machine scheduling for a parallel machine environment with one stage. They add idle times to the schedule, which depend on the variance of the processing times of the jobs. Uncertainties regarding demand are taken into account by limiting the number of jobs that can be produced in a given production period or by completely blocking resources for unexpected demand. Their study differs from our study since the variance of the processing times in our application case plays a minor role, whereas scrap rates have high influence on the demand. In addition, we can use significant historical data of demand developments to adjust the demand according to the articles through clustering. Our approach is also related to approaches that combine simulation and optimization [23]. Regarding the different possibilities in this area to combine optimization and simulation, our study is allocated in the category of first computing a schedule for a deterministic model, which is evaluated afterwards in the detailed simulation model. In a further step, schedules can be enhanced based on the simulation results. [PERSON] et al. [24] introduced this technique as simheuristics. In application scenarios, the model has to be built, i.e., parameters have to be estimated and demands have to be forecasted. For parameter estimation and modeling from available data, standard methods of input modeling, as summarized, for example, in Law [25], may be applied.