# Near-Optimal Heuristics for Just-In-Time Jobs Maximization in Flow Shop Scheduling
## 5 Computational Experiments and Results
### Problem Instances  
The instances were separated into two groups, with Group 1 consisting of small instances and Group 2 of medium and large ones. In each group, the instances are divided into classes defined by the number of jobs (\(n\)), number of machines (\(m\)) and scenarios of due dates, with 100 instances randomly generated for each class to reduce the sampling error.  
The processing times were generated in the interval \(U\)[1,99], as in the most production scheduling scenarios found in the literature (e.g., [21,22]). In Group 1, the parameters were \(n\in\{5,\,6,\,7,\,8,\,10\}\) and \(m\in\{2,\,3,\,5\}\) and, in Group 2, \(n\in\{15,\,20,\,30,\,50,\,80,\,100\}\) and \(m\in\{5,\,10,\,15,\,20\}\). These values were chosen to cover a significant range of instances of various sizes.  
The generation of due dates followed the method used by [23], with a uniform distribution in the interval \([P(1-T-R/2),\,P(1-T+R/2)]\), where \(T\) and \(R\) are the tardiness factor of jobs and dispersion range of due dates, respectively, and \(P\) the lower bound for the makespan which is defined as in Taillard [24]:  
\[P=\max\left\{\max_{1\leq k\leq m}\left\{\sum_{j=1}^{n}p_{jk}+\min_{j}\sum_{q=1} ^{k-1}p_{jq}+\min_{j}\sum_{q=k+1}^{m}p_{jq}\right\},\max_{j}\sum_{k=1}^{m}p_{ jk}\right\} \tag{13}\]  
The following scenarios represent the configurations obtained by varying the values of \(T\) and \(R\):  
* Scenario 1: low tardiness factor (\(T=0.2\)) and small due date range (\(R=0.6\));
* Scenario 2: low tardiness factor (\(T=0.2\)) and large due date range (\(R=1.2\));
* Scenario 3: high tardiness factor (\(T=0.4\)) and small due date range (\(R=0.6\)); and  
\begin{table}
\begin{tabular}{l l c c c c c} \hline \hline  & \multirow{2}{*}{**Heuristic**} & \multicolumn{3}{c}{**Initial Ordering**} & \multicolumn{3}{c}{**Neighborhood Search**} \\ \cline{3-6}  & & **EDD** & **MST** & **Insertion** & **Permutation** & **Fwd/Bwd** \\ \hline \multirow{3}{*}{NEH-based} & H1 & x & & & & \\  & H2 & x & & x & x & \\  & H3 & & x & & & \\  & H4 & & x & x & x & \\ \hline \multirow{3}{*}{Hodgson-based} & H5 & x & & & & \\  & H6 & x & & x & x & \\ \cline{1-1}  & H7 & & x & & & \\ \cline{1-1}  & H8 & & x & x & & \\ \hline \multirow{2}{*}{Other} & H9 & x & & & & \\ \cline{1-1}  & H10 & & x & & & x \\ \hline \hline \end{tabular}
\end{table}
Table 2: Composition of heuristic’s structure.  
* Scenario 4: high tardiness factor (\(T\) = 0.4) and large due date range (\(R\) = 1.2).  
Using these parameters, 6000 instances were generated in Group 1, divided in 60 classes. That is, five levels of number of jobs, three levels of number of machines, four scenarios and 100 instances per class (5 \(\times\) 3 \(\times\) 4 \(\times\) 100 = 6000). For Group 2, 9600 instances were generated, divided in 96 classes, six levels of number of jobs, four levels of number of machines, four scenarios and 100 instances per class (6 \(\times\) 4 \(\times\) 4 \(\times\) 100 = 9600). A total of 15,600 instances were generated and their parameters are summarized in Table 3.