# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 4 Representations of a Schedule
### Permutation-Based Encodings  
An _operation-based representation_\(s^{op}\) of a schedule, also called permutation, is given as a single list of all operations. Consider exemplarily  
\[s^{op}=[O_{i,1},O_{i^{\prime},1},O_{i,2},O_{i^{\prime\prime},1},O_{i,3},O_{i^ {\prime},2},\ldots].\]  
The permutation defines the operation sequences on the machines, and the corresponding starting times of all operation can be determined by a list scheduling algorithm. Note that the processing sequences of the jobs are easily satisfiable with every operation \(O_{i,j}\) having a higher list index than its job predecessor \(O_{i,j-1}\). Furthermore, blocking restrictions can be implemented by list index relations so that the feasibility of a schedule can be assured with the operation-based representation. However, when applying the permutation encoding in a heuristic search procedure, redundancy issues need to be taken into account. Regarding the list \(s^{op}\) shown above and assuming that the first two operations \(O_{i,1}\) and \(O_{i^{\prime},1}\) require different machines, the given ordering \(O_{i,1}\to O_{i^{\prime},1}\) and the reverse ordering \(O_{i^{\prime},1}\to O_{i,1}\) imply exactly the same schedule. Generally, the following conditions can be identified for two adjacent operations in the permutation being interchangeable without any effects on the schedule encoded, cf. [15]:  
* The operations belong to different jobs. * The operations require different machines. * The operations are not connected by a blocking constraint. * None of the operations is involved in a swap. Details on the relation of two operations due to a blocking constraint and the implementation of swaps are given in the subsequent Sections 4.2 and 4.3. To avoid unnecessary computational effort caused by treating redundant permutations as different schedules, the application of a unique representation is desirable. A second permutation-based encoding of a schedule, namely the _machine-based representation_\(s^{ma}\), describes the operation sequences on the machines as a nested list of all operations. Consider  
\[s^{ma}=[[O_{i,1},O_{i^{\prime\prime},1},\ldots],[O_{i^{\prime},1},O_{i,2}], \ldots],[O_{i,3},\ldots],[O_{i^{\prime},2},\ldots],\ldots]\]  
as a general example, where the \(k\)-th sublist indicates the operation sequence on machine \(M_{k}\). It can be observed that the machine-based representation uniquely encodes these operation sequences and any modification leads to the creation of a different schedule. However, since the machine-based encoding does not incorporate any ordering of operations requiring different machines, the given schedule may be infeasible with regard to blocking constraints. Preliminary computational experiments have shown that this blocking-related feasibility issue frequently appears when constructing BJSP schedules in heuristic search methods. Therefore, both representations are simultaneously used here to assure the uniqueness and the feasibility of the considered schedules. As a consequence, the applied permutation-based encodings need to be transformed efficiently into one another. Taking the general representations given above as examples, the operation-based encoding features list indices \(lidx(O_{i,j})\) and required machines \(Ma(O_{i,j})\) as follows:  
\[ \begin{array}{cccccccc}s^{op}=[&O_{i,1},&O_{i^{\prime},1},&O_{i,2},&O_{i^{ \prime\prime},1},&O_{i,3},&O_{i^{\prime},2},&\ldots]\\ lidx(O_{i,j}):&1&2&3&4&5&6&\ldots\\ Ma(O_{i,j}):&M_{1}&M_{2}&M_{2}&M_{1}&M_{3}&M_{4}&\ldots\end{array} \]  
The transformation \(s^{op}\to s^{ma}\) can be performed by considering the operations one by one with increasing list indices in \(s^{op}\) and assigning them to the next idle position in the operation sequence of the required machine in \(s^{ma}\), see [15; 16]. As an example, after transferring the first two operations \(O_{i,1}\) and \(O_{i^{\prime},1}\) from \(s^{op}\) to \(s^{ma}\), the machine-based representation turns out as \(s^{ma}=[[O_{i,1}],[O_{i^{\prime},1}],[],[],\ldots]\).