# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 4 Representations of a Schedule
### Involving Swaps  
When considering a lack of intermediate buffers in the job shop setting, the moments in which jobs are transferred from one machine to the next require special attention. The situation where two or more jobs interchange their occupied machines at the same point in time is called a swap of jobs. Figure 1 shows an excerpt of a general BJSP instance involving operations of three jobs with unit processing times on two machines. The Gantt chart in part (a) of the figure illustrates a swap of the jobs \(J_{i}\) and \(J_{i^{\prime}}\) on the machines \(M_{k}\) and \(M_{k^{\prime}}\) at time point \(\bar{t}\). Dependent on the type of real-world application, swaps are treated as feasible or infeasible in a BJSP schedule; see, for instance [17; 8]. In particular, the implementation of rail-bound systems and the existence of setup times require their exclusion, cf. [5; 6; 13; 34]. In this work, it is assumed that, even if jobs cannot be stored between consecutive processing steps, it is possible to move several jobs simultaneously on the production site. Thus, swaps are treated as feasible here. Considering the alternative graph representation of a BJSP, initially proposed in [42], reveals an upcoming issue related to swaps and feasibility. In Figure 1, the corresponding excerpt of the alternative graph implementing the given operations as nodes and the implied ordering constraints as arcs is shown on the right next to the Gantt chart. The gray arcs represent the processing sequences of the jobs, while the black arcs indicate the existing operation sequence and blocking constraints. Taking the swap situation in part (a) of Figure 1 as an example again and assuming that the operation \(O_{i^{\prime},2}\) is the last processing step of job \(J_{i^{\prime}}\), the operation sequence \(O_{i,1}\to O_{i^{\prime},2}\to O_{i^{\prime\prime},1}\) on machine \(M_{k}\) implies the solid arcs \((O_{i,2},O_{i^{\prime},2})\) and \((O_{i^{\prime},2},O_{i^{\prime\prime},1})\) in the alternative graph. Equivalently, the operation sequence \(O_{i^{\prime},1}\to O_{i,2}\) on machine \(M_{k^{\prime}}\) causes a blocking constraint, which is represented by the dashed arc \((O_{i^{\prime},2},O_{i,2})\). The resulting structure of arcs shows that swaps appear as cycles in the alternative graph representation of the schedule. These cycles refer to feasible situations, since the underlying blocking inequalities can simultaneously be fulfilled by an equivalent starting time of all involved operations. In part (b) of Figure 1, a Gantt chart and the corresponding graph-based representation of infeasible operation sequences are shown as a contrasting example. When trying to determine the starting times of the operations according to the operation sequences on the machines, an infeasible cyclic dependency of ordering and blocking constraints occurs at point \(\bar{t}\) as follows:  
\[s_{i^{\prime\prime},1}+p_{i^{\prime\prime},1}\leq s_{i^{\prime},2}\leq s_{i,2} \leq s_{i^{\prime\prime},1}.\]  
Figure 1: Illustration of feasible and infeasible cycles in BJSP schedules. It can be observed that such infeasible operation sequences similarly appear as cycles in the alternative graph representation. Thus, treating swaps as feasible results in a need to differentiate feasible and infeasible cycles when encoding BJSP schedules by an alternative graph. Following findings presented in [39] on a weighted graph representation, a simple structural property to contrast feasible swap cycles from infeasible sequencing cycles can be proposed. An alternative graph represents a feasible schedule for the BJSP, if all cycles involved do only consist of operations of different jobs requiring different machines, cf. [15]. The operations forming the cycle and featuring their start of processing at the same point in time are called a swap group.