The shifting bottleneck procedure for job-shops with parallel machines

The shifting bottleneck (SB) heuristic has been successfully applied to the job-shop scheduling problem. In this paper, the shifting bottleneck heuristic has been extended to solve job-shop problems with parallel machine workcentres. The efficient shifting bottleneck heuristic was developed to reduce the number of subproblems and provide tradeoff results between the computation time and the solution quality. The effect of bottleneck machine selection and reoptimisation procedures on the computational time is discussed. Moreover, a procedure is developed to achieve the desired makespan with near optimal number of machines of each machine type. The tradeoff between the makespan and the minimal number of machines required to achieve the makespan is also illustrated on few job-shop problems.