# Scheduling Algorithms for a Hybrid Flow Shop under Uncertainty
## 4 Computation of Schedules
According to \(x_{ilk_{n}k_{n}j}=1\) define \(k_{n}\). 2. \(\quad\)Exchange positions of selected jobs \(j\) and \(j_{s}\) with setting \(x_{ilkj}=0\), \(x_{ilk_{n}k_{n}j_{s}}=0\), \(x_{ilk_{j}s}=1\), and \(x_{ilk_{n}j_{k_{n}}}=1\). 3. Save solution in \(x_{n}\), execute Algorithm 2 (ECT) and compute makespan \(C_{max}(x_{n})\). 4. **if\(C_{max}(x_{n


```
**Algorithm 4****Tabu and Local Search--Steepest Descent**
```
1. Given a feasible initial solution \(x\) with makespan \(C_{max}(x)\). Choose parameter \(iterations\) and set \(termination:=iterations\). Choose parameter \(method\in\{shift,swap\}\). Choose parameter \(tabu\in\{true,false\}\). 2. if\(tabu=true\)  Initialize tabu set \(T:=\{x\}\). Choose parameter \(t>0\). else  Initialize tabu set \(T:=\{\}\). 3. repeat\(termination\
eq 0\)  Duplicate \(x_{n}:=x\). Initialize set \(S:=\{\}\). for all jobs \(j\) on stage 1. For the selected job \(\exists tx_{\exists ij}=1\). According to \(x_{\exists ij}=1\) define \(l\) and \(k\). for all\(l_{n}\in E_{ij}\) if\(method=shift\)  Shift job \(j\) to machine \(l_{n}\) and choose random a position to insert job \(j\) on this machine \(l_{n}\). Save solution in \(x_{n}\), execute Algorithm 2 (ECT) and compute makespan \(C_{max}(x_{n})\). if\(x_{n}\
ot\in T\) \(S=S\cup\{x_{n}\}\). if\(method=swap\) for all\(j_{n}\) on the selected machine \(l_{n}\)  According to \(x_{l_{n},k_{n},j_{n}}=1\) define \(k_{n}\). Exchange positions of jobs \(j\) and \(j_{n}\) with \(x_{\exists lij}=x_{l_{n},k_{n},j_{n}}=0\), \(x_{\exists ij_{n}}=x_{\exists i_{n},k_{n},j}=1\). Execute Algorithm 2 (ECT). Save solution in \(x_{n}\) and compute makespan \(C_{max}(x_{n})\). if\(x_{n}\
ot\in T\) \(S=S\cup\{x_{n}\}\). if\(tabu=true\) \(T=T\cup S\). if\(|T|>t\)  Delete the \(|T|-t\) elements from \(T\), which are added earliest. if\(S=\{\}\)  Set \(termination:=0\). for all schedules \(x_{n}\in S\). if\(C_{max}(x_{n})<C_{max}(x)\) \(x:=x_{n}\), \(C_{max}(x):=C_{max}(x_{n})\). \(termination:=iterations\). else \(termination:=termination-1\). ```
**Algorithm 5****Tabu and Local Search--Steepest Descent**
```
1. Given a feasible initial solution \(x\) with makespan \(C_{max}(x)\). Choose parameter \(iterations\) and set \(termination:=iterations\). Choose parameter \(method\in\{shift,swap\}\). Choose parameter \(tabu\in\{true,false\}\). if\(tabu=true\)  Initialize tabu set \(T:=\{x\}\). Choose parameter \(t>0\). else  Initialize tabu set \(T:=



In the following, the algorithms of [30] are presented. ## 5 Parameter Uncertainty

All algorithms presented in the previous section are assumed to have full access to the information about the problem. However, this is rarely found in practical scenarios. Usually, information about a system includes uncertainty and some parameters like processing times underlie statistical fluctuation. Some of the parameters can be described by statistical models like distributions or stochastic processes, whereas for other parameters like machine breakdowns only very little information is available. If uncertainty is modeled by stochastic distributions, a stochastic optimization problem can be formulated; see [PERSON] and [PERSON] [31]. The complexity of solving stochastic optimization problems is higher than the complexity of solving the related deterministic models. For realistic stochastic hybrid flow shop problems, even the analysis of a single configuration cannot be evaluated analytically with exact methods. Instead, for optimization of such models, stochastic discrete event simulation has to be coupled with metaheuristic optimization methods; see [PERSON] et al. [32]. Stochastic simulation needs a lot of computation time for function evaluation and metaheuristic optimization methods often need numerous function evaluations. Therefore, the computation of nearly optimal schedules and the evaluation with simulation in every iteration with a random initial schedule can exceed available computation time in production planning of mostly only a few minutes.