A note on the shifting bottleneck procedure for job shop scheduling

Abstract

We prove a result for the head-body-tail problem that has several consequences regarding the shifting bottleneck procedure described by Adams (Manag Sci 34:391-401, 1988). In particular, we show that for a machine with exactly two operations, the one-machine subproblem without precedence constraints cannot lead to a cycle. This provides insight on an erroneous example given in the renowned scheduling textbook of Pinedo (Scheduling: theory, algorithms, and systems, Springer, New York, 2016).