# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 4 Representations of a Schedule
### Permutation-Based Encodings
After transferring all operations given in the permutation \(s^{op}\), the machine-based encoding exactly corresponds to the nested list shown above. While performing the transformation \(s^{ma}\to s^{op}\), the redundancy of operation-based encodings needs to be taken into account. If the machine-based representation \(s^{ma}\) is constructed from an operation-based representation \(s^{op}\) of a specific schedule, it will be desirable that the reverse transformation yields exactly the initially given permutation \(s^{op}\) instead of a redundant equivalent. To assure that the resulting list of operations is equivalent or closest possible to an initially given operation-based representation, the following method is proposed. **Priority-Guided Transformation Scheme \(s^{ma}\to s^{op}\), cf. [15]:** In transferring a machine-based representation \(s^{ma}\) to a permutation \(s^{op^{\prime}}\), the set of candidate operations to be added to the permutation \(s^{op^{\prime}}\) next consists of all operations \(O_{i,j}\) in \(s^{ma}\), for which the job predecessor \(O_{i,j-1}\) and the machine predecessor given in \(s^{ma}\) either do not exist or are already present in \(s^{op^{\prime}}\). Considering the machine-based representation \(s^{ma}\) given above and an empty permutation \(s^{op^{\prime}}\), the set of candidate operations to be assigned to the first list index in \(s^{op^{\prime}}\) contains the operations \(O_{i,1}\) and \(O_{i^{\prime},1}\). To guarantee the recreation of the initially given permutation \(s^{op}\), the operation \(O_{i,j}\) with the maximum priority \(prio(O_{i,j})\) is chosen among all candidate solutions, whereby  
\[prio(O_{i,j})= \begin{cases}\frac{1}{lidx(O_{i,j})-lidx^{\prime}(*)}&\text{ if }lidx^{\prime}(*)<lidx(O_{i,j}),\\ 2&\text{if }lidx^{\prime}(*)=lidx(O_{i,j}),\\ lidx^{\prime}(*)-lidx(O_{i,j})+2&\text{if }lidx(O_{i,j})<lidx^{\prime}(*), \end{cases}  \tag{2}\]  
with \(lidx(O_{i,j})\) being the list index of the operation in the initially given permutation \(s^{op}\) and \(lidx^{\prime}(*)\) being the currently considered, idle list index in the newly created list \(s^{op^{\prime}}\). Recalling the example described above, the currently considered index features \(lidx^{\prime}(*)=1\), while \(prio(O_{i,1})=2\) due to \(lidx^{\prime}(*)=lidx(O_{i,1})=1\) and \(prio(O_{i^{\prime},1})=\frac{1}{2-1}=1\) due to \(lidx^{\prime}(*)=1<2=lidx(O_{i^{\prime},1})\). Thus, \(s^{op^{\prime}}=[O_{i,1}]\) holds after the first iteration, and the set of candidate operations to be assigned to the next idle list index \(lidx^{\prime}(*)=2\) consists of the operations \(O_{i^{\prime\prime},1}\) and \(O_{i^{\prime},1}\). Following this method iteratively, the newly constructed permutation \(s^{op^{\prime}}\) will be equivalent to the initially given permutation \(s^{op}\) from which \(s^{ma}\) has been derived. Given that the considered machine-based representation is feasible with regard to the processing sequences and the technological routes of the jobs, the priority-guided transformation scheme will assign exactly one operation to the next idle list index of the new permutation in every iteration and can never treat an operation more than once. Thus, the method constructs a unique operation-based representation from a given machine-based representation in a finite number of \(O(n_{op}\cdot m)\) steps, see [15] for detailed explanations.