Machine Criticality Measures and Subproblem Solution Procedures in Shifting Bottleneck Methods: A Computational Study

We examine the effects of different machine criticality measures (MCMs) and subproblem solution procedures (SSPs) on the performance of Shifting Bottleneck (SB) methods for the problem of minimizing maximum lateness in a job shop. Extensive computational experiments show that for problems with balanced workloads and random routeings simple MCMs and SSPs can be used without affecting solution quality. Routeing structure affects the performance of the SB method significantly. We also find that, contrary to some previous studies, the problem of maintaining feasibility in the SB method is significant.