# 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  
As mentioned in the previous section, the generation of feasible neighboring schedules for BJSPs involving a given API-based ordering is a critical issue. Since potentially required additional changes in the schedule are not contained in the BRT, an _Advanced Repair Technique (ART)_ is proposed, cf. [15; 16]. This method takes the operation-based representation of a schedule \(s\), named _perm_, and a desired sequence of two operations \(O_{a,b}\to O_{i^{\prime},i^{\prime}}\) and returns the operation-based representation \(s^{op}\) of a neighboring schedule \(s^{\prime}\), which involves the given ordering. All additional APIs necessary to transform the schedule \(s\) into \(s^{\prime}\) follow a basic rule. Instead of reverting a given pairwise sequence \(O_{a,b}\to O_{i^{\prime},i^{\prime}}\), the initial permutation is adapted by leftward interchanges of an operation of the job \(J_{a}\) and the repairing scheme is restarted. Figure 6 gives a schematic illustration of the ART in total. It can be observed in the left part of the chart that the BRT constitutes the foundation of the ART. The operations are iteratively taken from the list _perm_, requiring machines are checked for idleness, and blocking operations are determined, if necessary. The first important difference is indicated by the ellipsoid node printed in bold face. An operation is defined to be fixed, if it acts as the successor operation in a given pairwise sequence. The corresponding predecessor is denoted as the associated operation. In the general example stated above, operation \(O_{i^{\prime},i^{\prime}}\) is fixed with the associated operation \(O_{a,b}\). In case a fixed operation shall be added to the queue and its associated operation is already scheduled in the feasible permutation \(s^{op}\), no reversion occurs and the procedure continues in the basic version. In case the associated operation \(O_{a,b}\) is not yet scheduled, the given ordering \(O_{a,b}\to O_{i^{\prime},i^{\prime}}\) would be reverted by adding operation \(O_{i^{\prime},i^{\prime}}\) to the queue. To avoid this, the ART follows one of four modification paths in the gray box, the initial list _perm_ is adapted, and the whole procedure is restarted. Figure 7 illustrates the four possible cases of adaptation by means of Gantt charts. Assume that \(O_{a,b}\to O_{i^{\prime},j^{\prime}}\) is a given ordering and operation \(O_{i,j}\), shown in striped pattern, is the operation currently considered by the ART. Irreversible pairwise sequences are given by bold rightward arrows connecting adjacent operations on a machine, and the required additional APIs are indicated by leftward arrows with case-corresponding line patterns, see Figure 6. Let the feasible partial schedule \(s^{op}\) already contain operation \(O_{i^{\prime},i^{\prime}-1}\) in the cases 1, 2, and 3, and operation \(O_{i^{\prime},i^{\prime}-2}\) in case 4. The consideration of operation \(O_{i,j}\) to be scheduled next requires the following blocking constraint to be fulfilled: \(lidx(O_{i^{\prime},i^{\prime}})<lidx(O_{i,j})\). Since the associated operation \(O_{a,b}\) is not yet included in the list \(s^{op}\), the fixed operation \(O_{i^{\prime},i^{\prime}}\) cannot be positioned at the next idle list index prior to operation \(O_{i,j}\). To resolve the situation, the basic strategy is to shift or interchange the associated operation \(O_{a,b}\) further to the left on its machine, so that it will be scheduled before the required repairing shift of operation \(O_{i^{\prime},i^{\prime}}\) occurs in the next run of the procedure.