# Scheduling Algorithms for a Hybrid Flow Shop under Uncertainty
## 4 Computation of Schedules  
Taking the findings of Section 3 into account, we choose to apply SPT, local searches and tabu searches, and ECT schedules the jobs for the basic model described in Section 2. We also apply algorithms for the restriction of machine qualifications, skipping stages, and unrelated machines. At first, the first stage is scheduled with one of the algorithms, which then is combined with ECT in each case to schedule the second stage. Thus, we obtain Algorithms 1-4, which were already presented in our conference paper [PERSON] et al. (2018). To create an initial solution, we generate feasible schedules with SPT (Algorithm 1), which uses ECT (Algorithm 2). With Algorithm 1, jobs are ordered according to their increasing average processing times in stage 1 and after that they are scheduled successively to stage 1 on the machines, which becomes available. When the scheduling of all jobs to stage 1 is finished, stage 2 is scheduled with Algorithm 2 according the job completion times of stage 1. ```
1. Order jobs \(j\) according their increasing average processing times in stage 1 (\(productionvolume_{1j}\cdot p_{1j}\)) and save the queue in \(PrioList\). 2. Whenever a machine in stage 1 becomes available, select next unscheduled job \(j\) of \(PrioList\) that is qualified for the given machine and schedule \(j\) on the available machine. 3. Execute Algorithm 2 (ECT). 4. **return** schedule \(x\) with \(C_{max}(x)\). ```  
**Algorithm 1**Shortest Processing Time, SPT  
Based on this initial solution, six algorithms of Algorithms 3 and 4 optimize the solution. Both can be computed with one of the variants \"shift\" or \"swap\". With \"shift\", one randomly selected job in each iteration is positioned elsewhere in the existing schedule. In contrast, \"swap\" exchanges the positions of two randomly selected jobs. After one of these moves and the consideration of the eligibility restrictions for machines and stages, the resulting new schedule is compared with the old schedule and checked for improvement by computing and comparing makespans. Random Descent generates a new solution out of the existing one and if this solution performs better, regarding \(C_{max}\), the new solution is the starting point for the new testing of solutions. In contrast, Steepest Descent first tests for one job \(j\) the solutions in the neighborhood of the current solution, which are created by shifting or swapping that job to all the other machines that are eligible for that job. Furthermore, Algorithm 4 can be executed with or without tabu list (\(tabu\in\{true,false\}\)). If tabu list is used, the algorithms avoid testing a solution \(x\) again which has already been tested and is currently part of the tabu list. So, the tabu list contains elements \(x\), which have been tested before. If there is no improvement in the makespan within a predefined amount of iterations, Algorithms 3 and 4 terminate. By choosing all possible combinations of \(method\in\{shift,swap\}\) and \(tabu\in\{true,false\}\) in Algorithm 4, we have four variants of that algorithm. By computing the two possibilities \(method\in\{shift,swap\}\)in Algorithm 3, we have two further algorithms to evaluate. So, in total, with SPT, we get seven different optimization algorithms for the basic model of Section 2. ```
1. Given a feasible initial solution \(x\) with makespan \(C_{max}(x)\). Choose parameter \(iterations>0\) and set \(termination:=iterations\). Choose parameter \(method\in\{shift,swap\}\). 2. **while\(termination\
eq 0\)** 1. \(\quad\)Duplicate \(x_{n}:=x\). 2. Randomly choose a job \(j\) on stage \(i=1\). For this job \(\exists\mathrm{I}x_{ilkj}=1\). According to \(x_{ilkj}=1\) define \(l\) and \(k\). 3. Randomly choose a machine \(l_{n}\in E_{ij}\). 4. **if\(method=shift\)** 1. \(\quad\)Shift job \(j\) to machine \(l_{n}\) and choose randomly a position to insert job \(j\) on this machine \(l_{n}\). 2. **if\(method=swap\)** 1. \(\quad\)Choose randomly a job \(j_{s}\) on selected machine \(l_{n}\). For this job \(\exists\mathrm{I}x_{ilk_{n}j}=1\).