Performance of decomposition procedures for job shop scheduling problems with bottleneck machines

Decomposition procedures for job shop scheduling problems, such as the shifting bottleneck (SB) procedure, have shown promising results for a variety of shop environments. However, they have primarily been tested using problems where all machines are identical in terms of processing time distribution. Many practical scheduling problems involve bottleneck machines which become the focus of scheduling efforts, as suggested by the theory of constraints. In this paper we examine the performance of several variants of SB, some of which can be interpreted as naïve implementations of the TOC approach to scheduling. Our results show that both the solution time and quality of SB methods improve markedly when bottleneck workcentres are present. However, scheduling bottleneck machines optimally and using simple rules at other machines leads to poor performance unless the workload of the bottlenecks significantly exceeds that of the non-bottleneck machines.