# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 4 Representations of a Schedule
### Feasibility Guarantee  
In the following, the feasibility of a schedule given by its operation-based representation shall be examined more closely. As mentioned before, the processing sequences of the jobs and the blocking constraints can be translated to required list index relations of pairs of operations in the permutation. For two consecutive operations \(O_{1,j}\) and \(O_{1,i^{\prime}}\) of a job \(J_{1}\) with \(j<j^{\prime}\), the starting time constraint \(s_{1,j}+p_{1,j}\leq s_{1,j^{\prime}}\) has to be fulfilled by a feasible schedule. Since these starting times are derived from the ordering of the operations in the permutation-based encoding, the required processing sequence can easily be implemented by assuring \(lidx(O_{1,j})+1\leq lidx(O_{1,i^{\prime}})\). Blocking constraints can be described using list indices following the same pattern. Assume that, besides the operations \(O_{1,j}\) and \(O_{1,i^{\prime}}\) requiring two machines \(M_{k}\) and \(M_{k^{\prime}}\), respectively, there is another operation \(O_{2,i^{\prime\prime}}\) requiring machine \(M_{k}\). If \(O_{1,j}\to O_{2,i^{\prime\prime}}\) is determined as the operation sequence on this machine, the absence of intermediate buffers causes the starting time constraint \(s_{1,j+1}\leq s_{2,i^{\prime\prime}}\). Translating this blocking restriction to a list index constraint implies that the list index of the job successor of the machine predecessor of an operation needs to be smaller than the list index of the operation. Formally, for two operations \(O_{i,j}\) and \(O_{i^{\prime},j^{\prime}}\) of different jobs requiring the same machine and a given operation sequence \(O_{i,j}\to O_{i^{\prime},j^{\prime}}\), the following list index relation has to be fulfilled by a feasible permutation:  
\[lidx(O_{i,j+1})+1\leq lidx(O_{i^{\prime},i^{\prime}}), \tag{3}\]  
provided that the operation \(O_{i,j+1}\) exists. This type of list index constraints constitutes the basis of checking and retrieving the feasibility of a BJSP schedule given by a single list of operations. The proposed method, called the _Basic Repair Technique (BRT)_, takes any permutation _perm_, which is feasible with regard to the processing sequences of the jobs, as input and constructs the operation-based representation \(s^{op}\) of a feasible schedule for the BJSP, cf. [15; 16]. Note that the different terms _perm_ and \(s^{op}\) both describing an operation-based encoding of the schedule are only used for reasons of clarification here. Figure 2 outlines the algorithm. A permutation \(perm\), from which a feasible schedule is to be constructed, is initially given. The return permutation \(s^{op}\) is initialized with an empty list. The basic strategy of the BRT is to iterate over the list \(perm\), take at least one operation from this list in each iteration and place it in the list \(s^{op}\), so that all BJSP constraints are satisfied. As long as \(perm\) is not empty, the operation \(O_{i,j}\) at the first list index is considered in the current iteration. If the required machine \(Ma(O_{i,j})\) is idle, meaning that there is no other operation blocking it, the function ScheduleOp is called on operation \(O_{i,j}\). This function
* determines and stores the earliest possible starting time of the considered operation,
* removes the operation from \(perm\),
* adds the operation to the next idle list index in \(s^{op}\), and
* sets the status of \(Ma(O_{i,j})\) to blocked provided that a job successor \(O_{i,j+1}\) exists. With this, operation \(O_{i,j}\) is said to be scheduled and the algorithm continues with the next iteration. In case the required machine \(Ma(O_{i,j})\) is not idle, meaning that it is blocked by another operation, the currently considered operation is involved on the right-hand side of a blocking constraint as given in (3). The operation \(O_{i,j}\) is added to a queue and the operation required at a smaller list index to satisfy the blocking constraint is determined. The required operation is denoted as \(O_{a,b}\) in the following.