# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 5 Neighborhood Structures
### Introducing Interchange- and Shift-Based Neighborhoods
#### 5.1.1 Transition Schemes and Their Implementation
First, consider the API move \(O_{1,1}\leftrightarrow O_{3,2}\) in the schedule given in Figure 3 and the following permutation encoding this schedule:  
\[s^{op}=[\underline{O_{1,1}},O_{3,1},O_{1,2},\underline{O_{3,2}},O_{1,3},O_{ 3,3},O_{2,1},O_{2,2}].\]  
The API move can be implemented either by shifting operation \(O_{1,1}\) to the right together with its job successor \(O_{1,2}\) to preserve the processing sequence or by shifting operation \(O_{3,2}\) to the left together with its job predecessor \(O_{3,1}\). In both cases, the following permutation _perm_ is generated:  
\[perm=[O_{3,1},\underline{O_{3,2}},\underline{O_{1,1}},O_{1,2},O_{1,3},O_{3,3 },O_{2,1},O_{2,2}].\]  
It appears that the permutations generated by implementing API moves are infeasible with regard to blocking constraints. Here, operation \(O_{1,1}\) cannot be scheduled on machine \(M_{2}\), since this machine is blocked by operation \(O_{3,2}\). Thus, the given list needs to be repaired. After applying the BRT to  
Figure 3: Illustration of applicable API and TAPI moves in a given schedule for the BJSPT  
_perm_, the following feasible neighboring schedule \(s^{op^{\prime}}\), which incidentally turns out as a permutation schedule, is constructed:  
\[s^{op^{\prime}}=[O_{3,1},O_{3,2},O_{3,3},O_{\underline{0,1,1}},O_{1,2},O_{1,3}, O_{2,1},O_{2,2}].\]  
Considering the second applicable API move \(O_{3,2}\leftrightarrow O_{2,1}\) in the schedule of the \((3,3)\)-instance in Figure 3, the left shift of operation \(O_{2,1}\) and the right shift of operation \(O_{3,2}\) in \(s^{op}\) generate two different permutations \(perm_{1}\) and \(perm_{2}\), respectively:  
\[perm_{1}=[O_{1,1},O_{3,1},O_{1,2},O_{\underline{2,1}},O_{\underline{3,2}}, O_{1,3},O_{3,3},O_{2,2}],\]  
\[perm_{2}=[O_{1,1},O_{3,1},O_{1,2},O_{\underline{1,3}},O_{\underline{2,1}}, O_{\underline{3,2}},O_{3,3},O_{2,2}].\]  
Applying the BRT to \(perm_{1}\) constructs a feasible neighboring schedule  
\[s^{op^{\prime}}_{1}=[O_{1,1},O_{3,1},O_{1,2},O_{\underline{2,1}},(O_{2,2}, \underline{O_{3,2}}),O_{1,3},O_{3,3}],\]  
which is displayed in Figure 4. This schedule features a swap of the jobs \(J_{2}\) and \(J_{3}\) on the machine \(M_{1}\) and \(M_{3}\) and two periods of blocking time on the machines \(M_{2}\) and \(M_{3}\) indicated by the curved lines. Applying the BRT to \(perm_{2}\) reveals a major difficulty of using permutations, interchange-based operators, and repairing schemes in solution approaches for BJSPs. After the first three operations have been added to the partial permutation \(s^{op^{\prime}}_{2}=[O_{1,1},O_{3,1},O_{1,2}]\), the operation \(O_{1,3}\) is considered. It requires machine \(M_{3}\), which is blocked by operation \(O_{3,1}\). Thus, the job successor \(O_{3,2}\) must be scheduled prior to operation \(O_{1,3}\), and the BRT reverts the given API to regain the feasibility of the schedule. A graphical representation of the critical step is given in Figure 5.  
It can easily be seen that the operation sequence given in the first part of the permutation \(perm_{2}\) and the operation sequence resulting from the API cannot be implemented together. Additional changes in the schedule are necessary to construct a feasible solution involving the desired ordering \(O_{2,1}\to O_{3,2}\). Preliminary experiments have shown that a reversion occurs in 80 to 90% of all generated and repaired neighboring schedules. Therefore, an enhanced repairing scheme is required to find feasible solutions that contain given orderings while featuring as few changes as possible compared to the initially given ones. The desired operation sequence can be interpreted as a partial schedule with exactly two elements. While the decision problem on the existence of a completion of an arbitrarily large partial schedule is NP-complete for the BJSP, cf. [17], the generation of a feasible schedule with a given ordering of  
Figure 4: Illustration of the feasible neighboring schedule \(s^{op^{\prime}}_{1}\) resulting from an API move.