# Scheduling Algorithms for a Hybrid Flow Shop under Uncertainty
## 2 Description of the Basic Model  
The problem analyzed in this paper is a two-stage hybrid flow shop (\(FH2\)), in which a set of jobs \(N=\{1,\ldots,n\}\) has to be completed. To produce the components, there are two production stages \(i\), with \(i\in M\) with \(M=\{1,2\}\), through which each job \(j\in N\) follows the same route. At each stage \(i\) a job is processed by at most one machine \(l\), with \(l\in M_{i}=\{1,\ldots,m_{i}\}\), where \(m_{i}\geq 1\). As far as possible, we set the parameters according to [PERSON] et al. [2] and [PERSON] et al. [3], to support a more homogeneous notation for machine scheduling studies. The following assumptions hold for our model. In brackets, descriptions of the assumptions from the notation in the paper by [PERSON] et al. [4] are added. 1. In the first stage, all jobs are available at time zero. 2. Jobs that are to be produced in the first and last stage can only start in the second stage, after the job has been finished completely in the first stage. 3. Each machine can only handle one job at the same time. 4. Processing of a job on a machine is not interrupted, i.e., preemption is not allowed. 5. The problem contains machine qualifications (\(M_{j}\)), i.e., each job can only be processed on certain machines at each stage, where the set of eligible machines is \(E_{ij}\), with \(1\leq|E_{ij}|\leq m_{i}\). 6. Some jobs visit only one of the stages (\(skip\)). The set of stages to be visited is \(F_{j}\), where \(1\leq|F_{j}|\leq 2\)  
Figure 2: Production flow of the application case in AnyLogic 8.5. Jobs do not need to be dispatched in the same order in all stages. Thus, no fix permutation is considered. * There are infinite buffers in front, between and at the end of the two stages. * Processing times \(p_{ilj}\) of one product of job \(j\) are described by independent stochastic distributions separated by machine, stage and job, i.e., machines are unrelated. Especially in the first stage, processing times differ by machine (\(RM^{(1)}\)), in the second stage, they are machine-independent (\(PM^{(2)}\)). * For setup times \(s_{i}\), stochastic distributions over all machines and jobs per stage are available. * For scrap rates \(r_{ij}\), job- and stage-related stochastic distributions are available for both stages. Scrap parts are those parts which do not pass the quality check. * Available parts on stock \(stock_{ij}\) are included to fulfill the demand. * The objective is to minimize the makespan \(C_{max}\), where \(C_{max}\) is the maximum completion time and \(C_{ij}\) defines the completion time of a job \(j\) on stage \(i\), where \(C_{max}=\max_{i\in M,j\in N}C_{ij}\). * Order quantities of the job's \(demand_{ij}\) underlie uncertainty and may change even during the week when the job is produced, which results in varying production volumes \(productionvolume_{ij}\). The needed processing time for one job is the \(productionvolume_{ij}*p_{ilj}\). According to [PERSON] [5] and [PERSON] [6], this problem can be formalized in the [PERSON] et al. [4] notation as \(FH2\), \((RM^{(1)},\ PM^{(2)})\mid M_{j}\), \(skip\mid C_{max}\). In addition, several uncertainties in the model parameters as listed above have to be included, which are not formalized in [PERSON] et al. [4] notation. In addition, these other parameters of the [PERSON] et al. [4] notation are needed in the following sections:  
* \(S_{sd}\): sequence-dependent setup times
* _avail_: block times for machines
* \(rm\): block times for machines at the start of the production time
* \(lag\): overlapping or gaps between the processing of jobs in successive stages
* _prec_: priority relationships between jobs, i.e., one jobs needs to begin production before another job can be started  
Following [PERSON] et al. [2] and to support a more homogeneous notation for machine scheduling studies, the variables \(x_{iljk}\) and \(x\) are introduced. With these variables, the schedules can be described to their fullest extent with \(x=(x_{iljk})_{i\in M,l\in M_{i},j\in N}\).