# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 3 Problem Description and Benchmark Instances  
The BJSPT is defined by a set of machines \(\mathcal{M}=\{M_{k}\mid k=1,\ldots,m\}\) which are required to process a set of jobs \(\mathcal{J}=\{J_{i}\mid i=1,\ldots,n\}\) with individual technological routes. Each job consists of a set of operations \(\mathcal{O}^{i}=\{O_{i,j}\mid j=1,\ldots,n_{i}\}\), where operation \(O_{i,j}\) describes the \(j\)-th non-preemptive processing step of job \(J_{i}\). The overall set of operations is defined by \(\mathcal{O}=\bigcup_{j\in\mathcal{J}}\mathcal{O}^{i}\) containing \(n_{op}\) elements. Each operation \(O_{i,j}\) requires a specific machine \(Ma(O_{i,j})\) for a fixed processing time \(p_{i,j}\in\mathbb{Z}_{>0}\). The recirculation of jobs is allowed. Furthermore, a release date \(r_{i}\in\mathbb{Z}_{\geq 0}\) and a due date \(d_{i}\in\mathbb{Z}_{>0}\) are given for every job \(J_{i}\in\mathcal{J}\). Blocking constraints are introduced for every pair of operations \(O_{i,j}\) and \(O_{i^{\prime},j^{\prime}}\) of different jobs requiring the same machine. Given that \(O_{i,j}\to O_{i^{\prime},j^{\prime}}\) determines the operation sequence on the corresponding machine \(M_{k}\) and \(j\
eq n_{i}\) holds, the processing of operation \(O_{i^{\prime},j^{\prime}}\) cannot start before job \(J_{i}\) has left machine \(M_{k}\), in other words, the processing of operation \(O_{i,j+1}\) has started. To account for the optimization criterion, a tardiness value is determined for every job with \(T_{i}=max\{0,\;C_{i}-d_{i}\}\), where \(C_{i}\) describes the completion time of the job. There exist different mathematical formulations of the described problem as a mixed-integer optimization program. For an overview of applicable sequence-defining variables and comprehensive studies on advantages and disadvantages of the corresponding models, the reader is referred to [11; 15]. According to the well-known three-field notation, cf. for instance [37; 38], the BJSPT can be described by  
\[Jm\mid block,recrc,r_{i}\mid\sum T_{i}.\]  
A feasible schedule is defined by the starting times \(s_{i,j}\) of all operations \(O_{i,j}\in\mathcal{O}\), which fulfill the processing sequences, the technological routes and the release dates of all jobs as well as the blocking constraints. Since the minimization of total tardiness constitutes a regular optimization criterion, it is sufficient to consider semi-active schedules where no operation can be finished earlier without modifying the order of processing of the operations on the machines, see e.g., [38; 39]. Thus, the starting times of the operations and the operation sequences on the machines constitute uniquely transformable descriptions of a schedule. If a minimal value of the total tardiness of all jobs \(\sum_{j\in\mathcal{J}}T_{i}\) is realized, a feasible schedule is denoted as optimal. Note that, regarding the complexity hierarchies of shop scheduling problems, see for instance [38; 40] for detailed explanations, the BJSPT is harder than the BJSP with the minimization of the makespan \(C_{max}\). To discuss the characteristics of neighborhood structures and to evaluate their performance, a diverse set of benchmark instances is used. It is intended to involve instances of different sizes \((m,n)\) featuring different degrees of inner structure. The set of problems contains train scheduling-inspired (ts) instances that are generated based on a railway network, distinct train types, routes and speeds, cf. [11; 15], as well as the Lawrence (la) instances which are set up entirely random with \(n_{i}=m\) for \(J_{i}\in\mathcal{J}\), cf. [41]. The problems include 5 to 15 machines and 10 to 30 jobs. The precise instance sizes can be found in Tables 2-4. For all instances, job release dates and due dates are generated according to the following terms in order to create computationally challenging problems.