# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 2 Literature Review  
A variety of exact and heuristic solution approaches to complex scheduling problems reported in the literature exist. This section will focus on observations and findings on job shop problems featuring constraints and optimization criteria similar to the BJSPT. Exact solution methods are only sparsely applied to job shop problems with blocking constraints or tardiness-based objective functions. In 2002, [PERSON] and [PERSON] [17] present a Branch & Bound procedure that is enhanced by scheduling-tailored bounds and a special branching technique. The approach is tested on complex instances with ten machines and ten jobs involving blocking constraints and makespan minimization. Obtaining proven optimal solutions for the benchmark problems takes between 20 min and four hours of computation time. Even if technical enhancements have been achieved and general-purpose mixed-integer programming solvers became more powerful, the job shop scheduling problem remains one of the hardest combinatorial optimization models. It is recently shown in [9; 11; 15; 18] that even sophisticated mixed-integer programming solvers, such as IBM ILOG CPLEX and Gurobi, struggle with finding optimal and even feasible solutions to BJSPT instances with up to 15 machines processing up to 20 jobs in reasonable computation time. Table 1 summarizes the heuristic approaches presented for job shop problems involving blocking constraints and tardiness-based objectives. A reference is stated in the first column, while the second  
column specifies whether a job shop problem with blocking constraints (BJSP) or without such restrictions (JSP) is examined. Column three contains the objective function regarded and the fourth column displays the maximal size \((m,n)\) of the considered instances, where \(m\) denotes the number of machines and \(n\) defines the number of jobs. The last column presents the applied heuristic technique. For reasons of comparison, the first two works [19; 20] mentioned in Table 1 deal with a classical variant of the problem, namely the job shop problem with makespan minimization. The applied solution approaches constitute fundamental heuristic methods and the best-known algorithms to solve instances of the standard job shop setting until today. With the popular \((10,10)\) instance of Fisher and Thompson having been open for decades, the size of standard job shop problems, for which good solutions can be obtained, has grown. However, most of the large instances have never been solved to optimality, which highlights the significant intricacy of the combinatorial optimization problems under study. The following set of studies on JSPs with tardiness-based optimization criteria is intended to show the variety and the evolution of heuristic solution approaches applied together with the limitations in solvable problem size. A more comprehensive literature review including details on the types of instances solved can be found in [21]. In [22], a shifting bottleneck procedure is presented to generate schedules with minimal total tardiness for JSPs with release dates. The method is tested on a set of benchmark instances of size \((10,10)\). A well-known critical path-oriented neighborhood, cf. [2], is discussed with regard to its applicability to pursue tardiness-based objectives in [23]. The authors tackle JSPs with total tardiness minimization by Simulated Annealing (SA) and show that a general neighborhood based on interchanges of adjacent operations on machines leads to better results. A hybrid genetic algorithm (GA) is proposed for JSPs with recirculation, release dates and various tardiness-based objective functions in [14]. Even if the procedure is enhanced by a flexible encoding scheme and a decomposition approach, the results do not significantly support GAs as a favorable solution method. The computational experiments are conducted on a set of twelve instances with maximum size \((8,50)\).