# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 1 Introduction  
Complex scheduling problems appear in customer-oriented production environments, automated logistics systems, and railbound transportation as an everyday challenge. The corresponding job shop setting, where a set of jobs is to be processed by a set of machines according to individual technological routes, constitutes one of the non-trivial standard models in scheduling research. Even -simple variants of this discrete optimization problem are proven to be NP-hard, see [1]. While the classical job shop scheduling problem with infinite buffers and makespan minimization has been a subject of extensive studies for many decades, see, for instance [2; 3; 4], solving instances with additional real-world conditions, such as the absence of intermediate buffers, given release and due dates of the jobs and recirculation, newly receives increasing attention. The blocking job shop problem with total tardiness minimization (BJSPT) is regarded as an exemplary complex planning situation in this paper. Blocking constraints refer to a lack of intermediate buffers in the considered system. A job needs to wait on its current machine after processing, and thus blocks it, until the next required machine is idle. Such situations occur, for instance, in the manufacturing of huge items, in railbound or pipeline-based production and logistics as well as in train scheduling environments; see, for instance [5; 6; 7; 8]. The consideration of a tardiness-based objectiveimplements efficient economic goals like customer satisfaction and schedule reliability as they appear in most enterprises. On the one hand, existing computational experiments indicate that exact general-purpose solution methods have significant difficulties in finding optimal and even feasible solutions for non-classical job shop instances of practically relevant size; see, for instance [9; 10; 11]. On the other hand, the application of special-purpose heuristics shows a necessity of complicated construction, repairing and guiding schemes to obtain good solutions; see [12; 13; 14]. This work is intended to analyze the capability of well-known scheduling-tailored heuristic search methods in determining high quality solutions for complex job shop scheduling problems. Structural reasons for the appearing complexity are detected and algorithms, which assure the applicability of basic strategies, are proposed. As a natural foundation, permutations shall be used to represent feasible schedules of BJSPT instances. Widely applied interchange- and shift-based operators are chosen as transition schemes to set up neighboring solutions. Combining these ideas causes considerable redundancy and feasibility issues. A _Basic Repair Technique_ (BRT) is proposed to construct a feasible schedule from any given permutation, cf. [15; 16]. To fit the requirements in generating neighboring solutions, it is extended to an _Advanced Repair Technique_ (ART), which defines a feasible neighboring schedule from an initial permutation and a desired interchange, see [15; 16]. The resulting distances of solutions in a neighborhood are discussed to shed light onto the nature of the search space. In addition, different shifting strategies are analyzed with regard to their advantageousness in the search process. The presented neighborhood structures are embedded in a simulated annealing (SA) metaheuristic, which is applied to solve a diverse set of benchmark instances. Beneficial and critical aspects regarding the quality of the schedules found and the search guidance are pointed out by the computational results. The remainder of the article is organized as follows. Section 2 summarizes existing work on complex job shop scheduling problems related to the BJSPT. A theoretical description of the problem and its notation are given in Section 3. Two variants of permutation-based encodings of schedules are discussed with regard to redundancy and feasibility in Section 4. Therein, the BRT is introduced and the distance of two schedules is defined.