# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 6 Computational Experiments and Results
### Numerical Results
This implies that simultaneously applying a strict limitation of the acceptance of inferior schedules in the search procedure and a restriction of the possible interchanges based on the objective function value is not reasonable. \begin{table}
\begin{tabular}{l c c c c c c} \hline \hline \multirow{2}{*}{**Inst.**} & \multirow{2}{*}{\(\mathbf{(m,n)}\)} & \multirow{2}{*}{MIP} & \multicolumn{3}{c}{**API**} & \multicolumn{3}{c}{**TAPI**} \\ \cline{4-7}  & & & \(\overline{\sum T_{i}}\) & \(\min(\sum T_{i})\) & \(\overline{\sum T_{i}}\) & \(\min(\sum T_{i})\) \\ \hline la01 & \((5,10)\) & 762 * & 787.4 & 773 & **783.8** & 773 \\ la02 & \((5,10)\) & 266 * & 283.4 & 266 * & **277.6** & 266 * \\ la03 & \((5,10)\) & 357 * & 357.0 * & 357 * & 357.0 * & 357 * \\ la04 & \((5,10)\) & 1165 * & **1217.2** & 1165 * & 1284.2 & 1165 * \\ la05 & \((5,10)\) & 557 * & 557.0 * & 557 * & 557.0 * & 557 * \\ \hline la06 & \((5,15)\) & 2516 & **2790.0** & 2616 & 2912.4 & 2847 \\ la07 & \((5,15)\) & 1677 * & 1942.2 & 1869 & **1904.2** & 1677 * \\ la08 & \((5,15)\) & 1829 * & 2335.0 & 1905 & **2129.6** & 1829 * \\ la09 & \((5,15)\) & 2851 & 3275.2 & 3161 & **3226.6** & 3131 \\ la10 & \((5,15)\) & 1841 * & 2178.2 & 2069 & **2119.4** & 2046 \\ \hline la11 & \((5,20)\) & 6534 & 6186.2 & 5704 & **5846.4** & 5253 \\ la12 & \((5,20)\) & 5286 & 5070.0 & 4859 & **4997.8** & 4809 \\ la13 & \((5,20)\) & 7737 & 7850.6 & 7614 & **7611.8** & 7342 \\ la14 & \((5,20)\) & 6038 & **6616.8** & 5714 & 6872.4 & 6459 \\ la15 & \((5,20)\) & 7082 & **7088.6** & 5626 & 7153.6 & 6330 \\ \hline la16 & \((10,10)\) & 330 * & 395.8 & 335 & **360.8** & 335 \\ la17 & \((10,10)\) & 118 * & 144.2 & 120 & **118.8** & 118 * \\ la18 & \((10,10)\) & 159 * & **229.4** & 159 * & 264.0 & 235 \\ la19 & \((10,10)\) & 243 * & 306.6 & 243 * & **301.0** & 243 * \\ la20 & \((10,10)\) & 42 * & 55.6 & 42 * & **42.0 * & 42 * \\ \hline la21 & \((10,15)\) & 1956 & **2847.2** & 2101 & 2961.8 & 2680 \\ la22 & \((10,15)\) & 1455 & **2052.8** & 1773 & 2123.0 & 1988 \\ la23 & \((10,15)\) & 3436 & **3692.6** & 3506 & 3746.8 & 3424 \\ la24 & \((10,15)\) & 560 * & 966.8 & 761 & **724.0** & 644 \\ la25 & \((10,15)\) & 1002 & **1557.4** & 1289 & 1583.0 & 1390 \\ \hline la26 & \((10,20)\) & 7961 & 9275.8 & 8475 & **8600.8** & 7858 \\ la27 & \((10,20)\) & 8915 & **7588.0** & 6596 & 7641.8 & 6457 \\ la28 & \((10,20)\) & 2226 & 3430.8 & 2876 & **3367.6** & 2849 \\ la29 & \((10,20)\) & 2018 & **2948.0** & 2432 & 3099.0 & 2626 \\ la30 & \((10,20)\) & 6655 & 7621.6 & 6775 & **7372.8** & 6395 \\ \hline la31 & \((10,30)\) & 20,957 & 18,921.8 & 17,984 & **18,409.6** & 17,751 \\ la32 & \((10,30)\) & 23150 & 21,991.4 & 20,401 & **21,632.2** & 20,546 \\ la33 & \((10,30)\) & none & **22,494.2** & 19,750 & 22,913.2 & 20,553 \\ la34 & \((10,30)\) & none & **20,282.8** & 18,633 & 21,911.8 & 19,577 \\ la35 & \((10,30)\) & none & 21,895.0 & 18,778 & **21,384.4** & 20,537 \\ \hline la36 & \((15,15)\) & 675 & 1856.0 & 1711 & **1839.0** & 1599 \\ la37 & \((15,15)\) & 1070 & **1774.2** & 1621 & 1835.8 & 1594 \\ la38 & \((15,15)\) & 489 * & 760.4 & 645 & **745.4** & 676 \\ la39 & \((15,15)\) & 754 & **1573.0** & 1391 & 1850.2 & 1551 \\ la40 & \((15,15)\) & 407 * & **1008.6** & 613 & 1187.6 & 912 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Computational results of Algorithm PSA with \((200,50,0.995)\) applied to the Lawrence instances, cf. [15]. Moreover, it can be observed that the mean and the minimal total tardiness values differ significantly for most of the instances. Especially for problems of larger size, the mean objective function value often exceeds the minimal one by more than 10%. This aspect numerically emphasizes the ruggedness of the search space of the BJSPT, which leads to difficulties in the guidance of any heuristic search method. There seems to be a necessity of developing tailored neighborhood structures to more efficiently solve job shop problems with practically relevant constraints and objective functions.