# 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  
In line with the findings presented in the literature, intensification and diversification shall both be realized in a heuristic search procedure by appropriate moves. When solving general sequencing problems, interchanges and shifts of elements in permutations constitute generic operators which are widely used, cf. [45; 46]. The interchange-based moves applied here to the BJSPT and their implementation in the permutation-based encodings are defined as follows, see [15; 16]. **Definition 1**. : _An **API move** denotes the interchange of two adjacent operations \(O_{i,j}\) and \(O_{i^{\prime},j^{\prime}}\) of different jobs requiring the same machine \(M_{k}\in\mathcal{M}\) in the machine-based representation of the schedule. Adjacency is defined in a strict sense. A pair of operations \(O_{i,j}\) and \(O_{i^{\prime},j^{\prime}}\) is called **adjacent** if there is no idle time on machine \(M_{k}\) between the preceding operation leaving the machine and the start of the processing of the succeeding operation._  
**Definition 2**. : _A **TAPI move** denotes an interchange of two adjacent operations \(O_{i,j}\) and \(O_{i^{\prime},j^{\prime}}\) of different jobs requiring the same machine \(M_{k}\in\mathcal{M}\) with \(O_{i,j}\to O_{i^{\prime},j^{\prime}}\) in the machine-based representation of the schedule, where strict adjacency is given and the job \(J_{i^{\prime}}\) is currently tardy._  
The limitation to pairs of operations, which are strictly adjacent in a schedule, can be made without loss of search capability, cf. [15]. An idle time between two consecutively processed operations of different jobs on a machine may only occur due to 1. the technological routes of the jobs and the corresponding processing sequences on other machines or
2. the release date of the job of the succeeding operation. In the first case, there always exists a sequence of applicable API moves that eliminates the idle time and enables an interchange of the considered pair of operations. In the second case, an interchange of the considered pair of operations will only result in postponing the starting time of the initially preceding operation, since the succeeding operation cannot be processed earlier. If such a postponement is beneficial, this will also be indicated by an applicable API at another point in the schedule. Otherwise, postponing the preceding operation can never be advantageous with regard to total tardiness. These operators are intended to construct close neighboring solutions with a desired distance \(\delta(s,s^{\prime})=1\). Small steps are supposed to intensify the search and make a heuristic search procedure nicely tractable towards locally optimal schedules. The advantageousness of restricting the set of potential API moves based on the objective function value, namely considering only TAPI moves, shall be closely investigated in the computational experiments. Figure 3 shows all applicable API moves (solid arrows) and TAPI moves (dashed arrows) for a small BJSPT instance with three machines and three jobs. It can be observed that, referring to the same schedule, the set of TAPI moves is a subset of the set of API moves. Note that there is an idle time occurring between three pairs of consecutively processed operations on the machines \(M_{2}\) and \(M_{3}\), while there is no blocking time on any machine in the given schedule. To avoid redundancy in the neighborhood structure on the one hand, API moves are applied to the machine-based representation of a schedule. To check the feasibility of the constructed neighboring schedule on the other hand, the applied API move needs to transferred to the operation-based representation of the schedule, cf. [16]. Since the interchanged operations are not necessarily directly adjacent in the permutation, this can be done by a left shift or a right shift transformation, respectively.