# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 2 Literature Review
\begin{table}
\begin{tabular}{l l l l l} \hline \hline
**Reference** & **Problem** & **Objective \({}^{*}\)** & **Max. Size (\(m,n\))** & **Solution Approach** \\ \hline [PERSON] and Smutnicki 2005 [19] & JSP & \(C_{max}\) & \((10,50)\), \((20,100)\) & Tabu Search \\ [PERSON] et al. 2008 [20] & JSP & \(C_{max}\) & \((22,75)\) & Shifting Bottleneck Procedure \\ \hline [PERSON] and [PERSON] 1999 [22] & JSP & \(\sum w_{i}T_{i}\) & \((10,10)\) & Shifting Bottleneck Algorithm \\ [PERSON] and [PERSON] 2000 [23] & JSP & \(\sum T_{i}\) & \((30,90)\) & Simulated Annealing \\ Matfield and Biverthoff 2004 [14] & JSP & tardiness-based & \((8,50)\) & Genetic Algorithm \\ [PERSON] 2005 [24] & JSP & \(\sum w_{i}T_{i}\) & \((10,10)\) & Tabu Search \\ [PERSON] et al. 2008 [25] & JSP & \(\sum w_{i}T_{i}\) & \((10,30)\), \((15,15)\) & Hybrid Genetic Algorithm with Iterated Local Search \\ [PERSON] 2011 [26] & JSP & \(\sum w_{i}T_{i}\) & \((10,30)\), \((15,15)\) & Hybrid Shifting Bottleneck Procedure with Tabu Search \\ [PERSON] et al. 2011 [27] & JSP & regular & \((20,30)\), \((8,50)\) & Local Search Heuristic \\ [PERSON] and Wu 2011 [28] & JSP & \(\sum w_{i}T_{i}\) & \((15,20)\), \((10,50)\) & Simulated Annealing \\ [PERSON] et al. 2012 [29] & JSP & \(\sum w_{i}T_{i}\) & \((10,30)\), \((15,20)\) & Hybrid Genetic Algorithm with Tabu Search \\ [PERSON] and [PERSON] 2016 [30] & JSP & \(\sum w_{i}T_{i}\) & \((10,30)\), \((15,15)\) & Local Descent Scheme, Simulated Annealing \\ [PERSON] 2017 [21] & JSP & \(\sum w_{i}T_{i}\) & \((10,30)\), \((15,15)\) & Greedy Randomized Adaptive Search Procedure \\ [PERSON] et al. 2001 [12] & BISP & \(C_{max}\) & \((20,20)\) & Genetic Algorithm \\ [PERSON] et al. 2001 [8] & BISP & \(C_{max}\) & \((10,30)\) & Tabu Search \\ Mascids and Pacciarelli 2002 [17] & BISP & \(C_{max}\) & \((10,30)\), \((15,20)\) & Greedy Heuristics \\ [PERSON] et al. 2004 [31] & BISP & \(C_{max}\) & \((10,10)\) & Rollout Metaheuristic \\ [PERSON] 2009 [13] & BISP & \(C_{max}\) & \((10,50)\), \((15,20)\), \((20,20)\) & Tabu Search \\ [PERSON] et al. 2012 [32] & BISP & \(C_{max}\) & \((10,30)\), \((15,15)\) & Iterative Improvement Scheme \\ [PERSON] 2013 [33] & BISP & \(C_{max}\) & \((10,30)\), \((15,15)\) & Particle Swarm Optimization \\ [PERSON] and Pacciarelli 2016 [34] & BISP & \(C_{max}\) & \((10,30)\), \((15,20)\) & Iterative Greedy Algorithm \\ [PERSON] 2017 [19] & BISP & regular & \((10,30)\), \((15,20)\), \((20,30)\) & Tabu Search \\ [PERSON] et al. 2019 [35] & BISP & \(C_{max}\) & \((10,30)\), \((15,15)\) & Parallel Tabu Search \\ \hline \hline \end{tabular}  
* Objective Functions: makespan \(C_{max}\), total tardiness \(\sum T_{i}\), total weighted tardiness \(\sum w_{i}T_{i}\), various _regular_ or _tardiness-based_ objectives.  
\end{table} 
Table 1: Overview of existing heuristic solution approaches related to the BISPT. A JSP with setup times and total weighted tardiness minimization is tackled by a hybrid heuristic technique in [29]. A TS method is integrated into a GA to balance intensification and diversification in the search process. Furthermore, an improvement potential evaluation is applied to guide the selection of neighboring solutions in the TS. Promising results are found on a widely used set of benchmark instances. Different neighborhood structures are discussed and analyzed according to their capability of constructing schedules for a JSP with release dates and total weighted tardiness minimization in [30]. The experimental results show that the choice of the main metaheuristic method and the initial solution influence the performance significantly. Complex neighborhood structures involving several partially critical path-based components yield convincing results for instances with up to 15 machines and 30 jobs. In [21], an enhanced Greedy Randomized Adaptive Search Procedure (GRASP) is proposed and tested on the same set of benchmark instances. The applied method involves a neighborhood structure based on a critical tree, a move evaluation scheme as well as an amplifying and a path relinking strategy.