# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 2 Literature Review
The comprehensive computational study of [PERSON] and [PERSON] [21] shows that the presented GRASP is able to compete with the most powerful heuristic techniques tackling JSP instances with total tardiness minimization, namely the GA-based schemes proposed by [PERSON] et al. [25] and [PERSON] et al. [29]. Overall, the complexity of the applied methods, which is required to obtain satisfactory results for instances of still limited size, highlights the occurring difficulties in guiding a heuristic search scheme based on tardiness-related objective functions. Considering the second set of studies on BJSPs given in Table 1, an additional feasibility issue arises and repairing or rescheduling schemes become necessary. The inclusion or exclusion of swaps of jobs on machines constitutes a significant structural difference with regard to real-world applications and the applied solution approach, see Section 4.2 for further explanations. Note that almost all existing solution approaches are dedicated to makespan minimization, even if this does not constitute the most practically driven objective. In [12], a BJSP involving up to 20 machines and 20 jobs with swaps is tackled by a GA based on a permutation encoding. The well-known critical path-oriented transition scheme, cf. [2], is applied together with a job insertion-based rescheduling method in a TS algorithm in [8]. The authors consider a real-world application where swaps are not allowed and test their approach on instances with up to 10 machines and 30 jobs. Different greedy construction heuristics are compared in solving BJSP instances with and without swaps in [17]. Even for small instances, the considered methods have significant difficulties in constructing feasible schedules, since the completion of an arbitrary partial schedule is not always possible. The same issue occurs in [31], where a rollout metaheuristic involving a scoring function for potential components is applied to BJSP instances of rather small size with and without swaps. A connected neighborhood relying on interchanges of adjacent operations and job reinsertion is presented for the BJSP in [13]. Instances involving setup and transfer times, and thus excluding swaps, are solved by a TS algorithm with elite solutions storage. Computational experiments are conducted on a large set of benchmark instances with up to 20 machines and 50 jobs. In [32], an iterative improvement algorithm incorporating a constraint-based search procedure with relaxation and reconstruction steps is proposed for the BJSP with swaps. A parallel particle swarm optimization is tested on instances of the BJSP without swaps in [33] but turns out not to be competitive with the method proposed in [13] and the following one. In [34], an iterated greedy algorithm, which loops deconstruction and construction phases, is applied to problems with and without swaps. Computational experiments on well-known benchmark instances with up to 15 machines and 30 jobs imply that forced diversification of considered solutions is favorable to solve the BJSP. A study tackling instances with up to 20 machines and 30 jobs and approaching a wider range of regular objective functions including total tardiness is reported in [9]. The authors embed a job reinsertion technique initially proposed in [36] in a TS and test their method on the BJSP with swaps. A parallel TS including the critical path-oriented neighborhood, cf. [2], and construction heuristics to recover feasibility is presented in [35]. Parallel search trajectories without communication are set up to increase the number of considered solutions. Overall, the most promising approaches to solve BJSP instances proposed by [PERSON] [9], [PERSON] et al. [35], and [PERSON] and [PERSON] [34] give evidence for focusing on the application of sophisticated neighborhood and rescheduling structures instead of increasing the complexity of the search procedure itself. This motivates the following work on evaluating the capability of basic scheduling-tailored techniques.