# Scheduling Algorithms for a Hybrid Flow Shop under Uncertainty
## 4 Computation of Schedules
\begin{table}
\begin{tabular}{l l l l l} \hline \hline \multicolumn{1}{c}{**Foreessing Times \(p_{ij}\) and Setup Times \(s_{i}\)**} & \multicolumn{2}{c}{**Scrap Rate \(r_{ij}\)**} \\ \hline
**Scenario** & **Optimization** & **Simulation** & **Optimization** & **Simulation** \\ \hline data on dedicated machine available & median per job and machine & random value from distribution per job and machine & mean value or value from quantile per job and machine & random value from distribution per job over all machines \\ \hline no data on dedicated machines available for the job, but job data at the stage available & median per job over all machines & random value from distribution per job over all machines & mean value or value from quantile per job & random value from distribution per job over all machines \\ \hline no job-related and machine-related data available, but estimates for job data are available from external sources (e.g., expert knowledge) & estimated data for the job at the stage & estimated data for the job at the stage & - & - \\ \hline no job-related and machine-related data available, but data for all jobs at the stage available & median over all machines for all jobs & random value from distribution over all machines for all jobs & mean value or value from quantile over all machines for all jobs \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Data concept for scheduling parameters in optimization and simulation. Figure 3: Boxplot for processing times for one exemplar of similar jobs \(j\) on different machines at stage \(1\) of the same machine type. ## 6 Clustering and Forecasting in the Application Case

In order to allocate the appropriate production volume (\(productionvolume_{ij}\)) per job and stage and to meet the final customer demand volume, scrap and customer ordering behavior have to be considered. Therefore, the currently known demand per job and stage (\(demand_{ij}\)) as well as historical data of scrap and demand are used. The procedure of including these factors is described in the following and finally results in Equation (1). The clustering procedure was first mentioned in [PERSON] et al. (2019). For clustering demand data and identifying high-risk jobs (see Figure 4), k-means\(++\) is applied with three parameters and the result is shown in Figure 5. For k-means\(++\), [PERSON] and [PERSON] (2019) theoretically prove and show in their results the quality of the algorithm against k-means algorithms for clustering. The three parameters for clustering are namely:

* the probability that the demand of a job grows by 500 or more parts in the last week based on historical data (\(emp\_prob\));
* the average increase in demand per job (only counted if the demands are increased) (\(mean\_pos\_diff\));
* and the variance of the variation coefficient for the demands of the last three observations of the previously ordered amount. (\(var\_vark\_last\_3\)). Following the elbow method, see [PERSON] et al. (2019), k-means should be applied for our application case with four clusters. After analyzing the data, we computed the four clusters as shown in Figure 5 and defined the jobs of cluster 3 and 4 (marked in light red in Figure 5) as high-risk jobs. The demand for high-risk jobs is multiplied with job-related safety factors, namely \(SF2_{ij}\), where \(1\geq SF2_{ij}\geq 2\). The safety factor is used to keep the slot for the higher demand in the schedule reserved. Instead of only planning with the \(\frac{demand_{ij}-stock_{ij}}{(1-r_{ij})}\) for high-risk-articles, the production volume for risky jobs is extended in this first step to \(\frac{demand_{ij}-stock_{ij}}{(1-r_{ij})}\ \cdot\ SF2_{ij}\), where \(SF2_{ij}\geq 1\) for high-risk jobs \(j\). Figure 4: Time series of demands of a high-risk job. The demands of non high-risk jobs are multiplied with \(SF2_{ij}=1\).