# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 6 Computational Experiments and Results
### Numerical Results  
The computational experiments are conducted on a notebook featuring an Intel Dual Core i5 processor (2.20 GHz) with 8 GB RAM. Algorithm PSA is implemented in Python 3. Tables 2-4 summarize the numerical results of five independent runs operated for each instance, parameter setting, and neighborhood structure. The first two columns of each table display the instance and the corresponding size \((m,n)\). For reasons of comparison, the third column contains the best total tardiness value obtained by solving the considered problem with the help of IBM ILOG CPLEX 12.8 using a mixed-integer programming (MIP) formulation with pairwise precedence variables, see [15] for detailed explanations on the model. Objective function values with proven optimality are denoted by an asterisk. The next pairs of columns show the average total tardiness \(\overline{\sum T_{i}}\) and the minimal total tardiness \(\min(\sum T_{i})\) obtained for each instance by Algorithm PSA based on the API and the TAPI neighborhood, respectively. Contrasting the mean total tardiness values reached, the smaller measure is highlighted by boldface printing. Generally, it can be stated that Algorithm PSA yields satisfactory results for instances with and without inner structure especially when being compared to the MIP approach. For instances of small size and an equivalent number of jobs and machines, such as ts01 to ts05, la02 to la05, la07 and la08, la17, la19 and la20, the method is capable of finding an optimal solution. Even more important, the algorithm is able to generate medium quality solutions for large problems like la31 to la35, for which a general-purpose method might even struggle in generating feasible schedules. This gives evidence for the advantageousness of the proposed heuristic approach in solving real-world production planning instances of critical size. Nonetheless, the complex repairing schemes constitute a drawback of the heuristic algorithm with regard to computation time. PSA requires 2 to 70 min of runtime dependent on the size of the instances, while the MIP technique is able to solve small instances to optimality in a few seconds, cf. [15]. As indicated by the statistical analysis of the neighborhoods in the previous section, the runtime of PSA can be improved by implementing APIs by a right shift transformation only. To further overcome these difficulties, a hybrid method combining heuristic and MIP mechanisms seems promising. Heuristic methods can be used to generate feasible schedules for large instances quickly, while solving smaller subproblems by MIP may be a superior improvement strategy towards locally optimal solutions. First, results following this research direction are presented in [15; 18]. Comparing the API and TAPI neighborhood with regard to solution quality over all instances, no transition scheme clearly dominates. An advantageous of guiding the search by current  
\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline \multirow{2}{*}{**Inst. **} & \multirow{2}{*}{\(\boldsymbol{(m,n)}\)} & \multirow{2}{*}{**MIP**} & \multicolumn{3}{c}{**API**} & \multicolumn{3}{c}{**TAPI**} \\ \cline{4-7}  & & & \(\overline{\sum T_{i}}\) & \(\min(\overline{\sum T_{i}})\) & \(  
total tardiness values cannot be observed. A preliminary performance testing might be beneficial for every individual application of the API-based neighborhood structures to other BJSPT instances, since the solution quality reached may dependent on the problems size and structure as well as on the setting of the metaheuristic framework. It can be remarked that, based on the experiments on the ts instances with two different parameter settings, the API neighborhood performs better with lower temperature levels between 20 and 0.5, while the TAPI neighborhood is favorable combined with higher temperature levels between 20 and 10.