# On Neighborhood Structures and Repair Techniques for Blocking Job Shop Scheduling Problems +
## 5 Neighborhood Structures
### Characteristics and Evaluation
#### 5.2.2 Observations on the Interchange-Based Transition Scheme  
Besides the general problem solving capability of a metaheuristic involving the proposed neighborhood structures, the API-based transition schemes shall be evaluated with regard to their ability to generate small distance and high quality neighbors. Special attention is given to the differences appearing in using a left shift or a right shift transformation to implement an API in the operation-based encoding of a schedule. For all API and TAPI neighbors constructed during the computational experiments, a specific interchange is chosen, left shift and right shift transformation are performed, and both resulting solutions are evaluated with regard to their distances from the initially given schedule and their total tardiness values.  
Figure 8 displays the distributions of the distances of API-based neighbors with left shift (LS) and right shift (RS) transformation for the benchmark instances by boxplots. The range in which 50% of the distance measures of the neighbors can be found, the so-called interquartile range, is represented by the box. The black horizontal line indicates the median of the sample. The whiskers plot the minimal and the maximal distance value which are not more than one and a half interquartile ranges away from the box.  
Considering all transitions independent of the direction of implementation, it can be stated that the distance of neighboring schedules based on a single API is remarkably large for the BJSP. Evidently, a significant amount of additional adaptations is required to fit a given pairwise sequence to a feasible schedule. Even if it is not guaranteed that the closest neighbor is generated by the ART, these results highlight the complexity of the search space caused by blocking constraints. This may lead to difficulties in the effectiveness and the control of a heuristic search method, since an iterative execution  
Figure 8: Boxplots representing the distribution of the distance measure among neighbors based on API-moves for the benchmark instances of the BJSPT, cf. [15].  
of small changes is desirable to systematically explore the set of feasible schedules. Comparing the directed implementations of APIs, the distances of neighbors constructed using a right shift transformation are significantly smaller than the measures of neighboring schedules generated by a left shift transformation. Thus, it is recommendable to implement APIs by a right shift in the operation-based encoding to support the execution of smaller search steps, cf. [15].  
The chart in Figure 9 shows the proportion of APIs for which the neighbors resulting from a left shift and a right shift transformation are equivalent (EQ). Given that two different schedules arise, it is displayed to which extent the schedule with a smaller total tardiness value is generated by a left shift or by a right shift implementation of the API in the operation-based encoding. It can be observed that the majority of neighboring schedules based on the same API end up to be equivalent after applying the ART. Regarding the cases where different schedules are constructed, the right shift transformation clearly outperforms the left shift transformation by means of total tardiness. Since heuristic methods are intended to require limited computational effort, it is reasonable to implement APIs by right shift transformation only, cf. [15]. The analysis indicates that the proportion of cases in which the best possible neighboring schedule is not generated is less than 13%.