# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 4 Representations of a Schedule
### Feasibility Guarantee
At this point, the BRT proceeds according to one of three different paths indicated in Figure 2.  
**Case 1:** If the operation \(O_{a,b}\) is not involved in the queue and its required machine \(Ma(O_{a,b})\) is idle, operation \(O_{a,b}\) and all operations in the queue are scheduled following a last in-first out strategy. Note that, when Case 1 is singly executed, exactly two operations are transferred from \(perm\) to the new operation-based representation \(s^{op}\). **Case 2 \(\rightarrow\) Case 1:** If operation \(O_{a,b}\) is not involved in the queue but its required machine \(Ma(O_{a,b})\) is not idle, operation \(O_{a,b}\) is added to the queue and the next required operation to fulfill the occurring blocking constraint is determined. Operations are added to the queue according to Case 2 until a required operation with an idle machine is found. Then, Case 1 is executed and all queuing operations are scheduled. Note that following this path, at least three operations are transferred from \(perm\) to \(s^{op}\). **Case 2 \(\rightarrow\) Case 3:** Equivalent to the previous path, the operation \(O_{a,b}\) is added to the queue and the next required operation is determined. Case 2 is executed until an operation already present in the queue is found. This refers to the situation where a cyclic dependency of blocking constraints exists and a swap needs to be performed in the schedule. The swap group is defined by all operations in the queue added in between the two occurrences of the currently considered operation. Following case 3, all operations of the swap group are scheduled with equivalent starting times and potentially  
Figure 2: Schematic outline of the Basic Repair Technique (BRT), cf. [15]. remaining operations in the queue are scheduled correspondingly after. Since the smallest possible swap cycle is formed by two operations, at least two operations are transferred from _perm_ to \(s^{op}\) when this path is executed. With this, the BRT captures all occurring dependencies in arbitrary permutation-based encodings of BJSP schedules. The method assures that all blocking constraints are fulfilled by shifting required operations to positions with smaller list indices and by forming and modifying swap groups. Given that the number of operations in the problem is finite and the initially given permutation is feasible with respect to the processing sequences of the jobs, the following proposition holds, cf. [15]. The Basic Repair Technique (BRT) terminates and constructs an operation-based representation \(s^{op}\) of a feasible schedule for the BJSP. It has to be shown that  
1. the resulting permutation \(s^{op}\) is feasible with regard to the processing sequences of all jobs \(J_{i}\in\mathcal{J}\),
2. the resulting permutation \(s^{op}\) is feasible with regard to blocking constraints and
3. every operation \(O_{i,j}\in\mathcal{O}\) is assigned to a position in the feasible permutation \(s^{op}\) exactly once. An unsatisfied blocking constraint \(s_{i^{\prime},j^{\prime}}\leq s_{i,j}\) is detected in the BRT while an operation \(O_{i^{\prime},j^{\prime}-1}\) is already scheduled in the feasible partial permutation \(s^{op}\) and operation \(O_{i,j}\) is the currently considered operation, for which \(Ma(O_{i,j})\) is not idle. The BRT shifts required operation(s), here only operation \(O_{i^{\prime},j^{\prime}}\), to the next idle position \(lidx^{\prime}(*)>lidx^{\prime}(O_{i^{\prime},j^{\prime}-1})\) and will never affect list indices prior to or equal to \(lidx^{\prime}(O_{i^{\prime},j^{\prime}-1})\). Hence, a given feasible ordering accounting for processing sequences and technological routes, such as \(lidx(O_{i^{\prime},j^{\prime}-1})<lidx(O_{i^{\prime},j^{\prime}})\), can never be violated by changes in the operation sequences made to fulfill blocking constraints. (1) is true. The initially empty permutation \(s^{op}\) is expanded iteratively in the BRT.