# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 5 Neighborhood Structures
### Introducing Interchange- and Shift-Based Neighborhoods
#### 5.1.2 Generating Feasible API-Based Neighbors
Therefore, the machine predecessor list of \(O_{a,b}\) excluding operations of job \(J_{a}\) is determined, see Figure 6, and the adaptation of the initial permutation is conducted according to one the following cases:  
**Case 1:** If there exists a machine predecessor \(\alpha(O_{a,b})\), an additional API move is performed and the ordering \(O_{a,b}\to\alpha(O_{a,b})\) is defined to be fixed additionally, see part (a) of Figure 7. The API is implemented in the list \(perm\) by a left shift of operation \(O_{a,b}\). **Case 2:** If there exists no machine predecessor of operation \(O_{a,b}\) and there exists no other operation associated with operation \(O_{i^{\prime},i^{\prime}}\), the currently considered operation \(O_{i,j}\) might itself be a job predecessor \(O_{a,b^{\prime}}\) of the associated operation \(O_{a,b}\). If this is true, an API move is performed with its machine predecessor \(O_{i^{\prime},i^{\prime}-1}\), see part (b) of Figure 7. Note that, for this situation to occur, the machine predecessor necessarily needs to exist and belong to job \(j_{i^{\prime}}\). **Case 3:** Assume that there exists no machine predecessor of operation \(O_{a,b}\) and no other operation associated with operation \(O_{i^{\prime},i^{\prime}}\), and, furthermore, the currently considered operation is not a job predecessor of operation \(O_{a,b}\). Then, the associated operation is shifted leftward in the permutation \(perm\) to the position prior to the currently considered operation \(O_{i,j}\), see part (c) of Figure 7. This shift does not implement an API move but is sufficient to satisfy the given blocking constraint. **Case 4:** This situation differs structurally from the other three cases. It involves at least three machines, and it can only appear with operations of recirculating jobs after one or more additional APIs  
Figure 6: Schematic outline of the Advanced Repair Technique (ART), cf. [15]. have already been performed. In part (d) of Figure 7, besides the initially given ordering, the pairwise sequences \(O_{a,b^{\prime}}\to O_{i^{\prime},i^{\prime}-1}\) and \(O_{a,b^{\prime\prime}}\to O_{i^{\prime},i^{\prime}-1}\) are exemplarily fixed. After the machine predecessor list of the associated operation \(O_{a,b^{\prime}}\) has been determined as empty, a second operation associated with the fixed operation \(O_{i^{\prime},i^{\prime}-1}\) can be found, namely operation \(O_{a,b^{\prime\prime}}\). Dependent on the existence of a machine predecessor \(\alpha(O_{a,b^{\prime\prime}})\), the ART proceeds according to Cases 1, 2, or 3 with an adaptation of the list \(perm\). In the depicted Gantt chart, a shift following Case 1 is shown as an example. After the permutation is adapted according to one of the four cases, the ART is restarted involving one additionally fixed pairwise sequence. The following observation can be made regarding the operations moved during adaptation. **Observation 1**. : _While executing the ART, the operation interchanged or shifted leftwards when adapting the permutation is always the associated operation \(O_{a,b}\) defined by the initially given fixed sequence \(O_{a,b}\to O_{i^{\prime},i^{\prime}}\) or one of its job predecessors._  
Based on this, arguments indicating the correctness of the ART can be derived as follows, cf. [15]:  
**Proposition 2**. : _The ART terminates and returns a permutation \(s^{\mathit{op}}\) encoding a feasible schedule for the BJSP involving a predefined ordering \(O_{a,b}\to O_{i^{\prime},i^{\prime}}\) of two operations of different jobs requiring the same machine._  
Proof. : It is equivalently assumed here that the initially given list \(perm\) is feasible with regard to the processing sequences of all jobs \(J_{i}\in\mathcal{J}\). The ART proceeds like the BRT until there is a fixed operation \(O_{i^{\prime},i^{\prime}}\) to be scheduled prior to its associated operation \(O_{a,b}\). According to Proposition 1, the BRT terminates and returns a feasible encoding \(s^{\mathit{op}}\) of a BJSP schedule from a given permutation.