# Heuristics for a Two-Stage Assembly-Type Flow Shop with Limited Waiting Time Constraints
## 4 Computational Experiments
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{\(m\)} & \multirow{2}{*}{\(n\)} & \multicolumn{2}{c}{**CPU 1**} & \multicolumn{4}{c}{**NI 2**} \\ \cline{3-8}  & & **Set A** & **Set B** & **Set C** & **Set A** & **Set B** & **Set C** \\ \hline \multirow{8}{*}{2} & 10 & 0.1 [0, 0.2] & 0.1 [0, 0.1] & 0 [0, 0] & 0 & 0 & 0 \\  & 20 & 58.9 [0.1, 172.2] & 0.1 [0.1, 0.1] & 0.1 [0.1, 0.1] & 0 & 0 & 0 \\  & 30 & 716.2 [0.3, \(T_{L}\)] & 0.6 [0.1, 2.2] & 0.3 [0.2, 0.4] & 1 & 0 & 0 \\  & 40 & 754.7 [6.2, \(T_{L}\)] & 0.4 [0.2, 0.5] & 0.4 [0.2, 0.5] & 2 & 0 & 0 \\  & 50 & \(T_{L}\) & 0.8 [0.5, 1.3] & 0.7 [0.4, 0.9] & 5 & 0 & 0 \\ \hline \multirow{8}{*}{5} & 10 & 1.2 [0, 2.7] & 0.4 [0, 1.3] & 0.1 [0, 0.1] & 0 & 0 & 0 \\  & 20 & \(T_{L}\) & 98.2 [0.2, 489.9] & 2.8 [0.1, 12.9] & 5 & 0 & 0 \\  & 30 & \(T_{L}\) & 360.6 [0.4, \(T_{L}\)] & 1.2 [0.6, 2.5] & 5 & 1 & 0 \\  & 40 & \(T_{L}\) & 15.6 [0.5, 70.9] & 177.8 [0.9, 873.8] & 5 & 0 & 0 \\  & 50 & \(T_{L}\) & 344.6 [1.6, 1630.4] & 207.8 [2.6, 998.8] & 5 & 0 & 0 \\ \hline \multirow{8}{*}{10} & 10 & 6.3 [2.5, 13] & 0.8 [0.1, 2.3] & 1.4 [0.1, 2.4] & 0 & 0 & 0 \\  & 20 & 1440.7 [3.4, \(T_{L}\)] & 1075.8 [1.8, \(T_{L}\)] & 1080.4 [0.6, \(T_{L}\)] & 4 & 2 & 3 \\ \cline{1-1}  & 30 & \(T_{L}\) & 1086.3 [5.6, \(T_{L}\)] & 527.5 [3.3, \(T_{L}\)] & 5 & 3 & 1 \\ \cline{1-1}  & 40 & \(T_{L}\) & 1419.2 [54.8, \(T_{L}\)] & 1455.2 [76, \(T_{L}\)] & 5 & 3 & 4 \\ \cline{1-1}  & 50 & \(T_{L}\) & 805.5 [26.2, \(T_{L}\)] & 1756.3 [1637.6, \(T_{L}\)] & 5 & 2 & 3 \\ \hline \hline \end{tabular}  
* Average \([\min,\max]\) computation time, where \(T_{L}\) = 1800 s. 2 Number of instances not terminated within 1800 s.  
\end{table} 
Table 3: Performance of MIP using CPLEX. \(obj_{\textit{worst}}\) represent the best and worst, respectively. According to the definition of RDI, the lower the RDI, the better the performance. A summary of the results is in Table 4 which provides the average RDI and number of instances (out of 75) that LS# found the best solutions. As observed from the table, LS1 outperformed the other rules. This indicates that the first stage on which LS1 focuses is more important than the second stage, probably because the decision on sequencing jobs on the parallel machines in the first stage must consider the limited waiting time constraints. However, in the second stage, there is a single assembly machine, and the sequence is equivalent to the sequence in the first stage because this study considers only permutation schedules. Thus, if a shop manager wants to focus on either stage, the result recommends the first stage. In summary, LS1 showed the best performance among the proposed list scheduling rules, therefore LS1 will offer an initial seed sequence for MNEH in the subsequence experiments. To check the efficiency of the interchange method in the proposed MNEH, comparison tests were performed on the instances with up to \(n=50\). In this test, initial seed sequences were obtained using LS1. Table 5 and Figure 6 show the results that show the effectiveness of the interchange method in MNEH. The table reports the percentage change defined as \(100\times(obj_{\textit{MNEH}}-obj_{\textit{NEH}})/obj_{\textit{NEH}}\). Note that the negative percentage change indicates that MNEH found a better solution than NEH. As revealed in the table, MNEH worked better than NEH, which indicates that the simple interchange method can improve the solution quality. In addition, the improvement was more apparent when the problem size increased. The same result was obtained in Set A than in Sets B and C as shown in Figure 6. Thus, it can be concluded that the interchange method used in MNEH worked well. In addition, although the interchange procedure was added, MNEH provided a solution for all instances in less than a second.