Title: The shifting bottleneck procedure for job-shops with parallel machines

Authors: Kai-Pei Chen, Marvin S. Lee, P. Simin Pulat, Scott A. Moses

Addresses: School of Industrial Engineering, University of Oklahoma, 202 West Boyd, Room 124, Norman, OK 73019, USA. ' School of Industrial Engineering, University of Oklahoma, 202 West Boyd, Room 124, Norman, OK 73019, USA. ' School of Industrial Engineering, University of Oklahoma, 202 West Boyd, Room 124, Norman, OK 73019, USA. ' School of Industrial Engineering, University of Oklahoma, 202 West Boyd, Room 124, Norman, OK 73019, USA

Abstract: 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.

Keywords: job shop scheduling; heuristics; shifting bottleneck procedure; parallel machine scheduling; machine selection; reoptimisation; dispatching rules; makespan.

DOI: 10.1504/IJISE.2006.009059

International Journal of Industrial and Systems Engineering, 2006 Vol.1 No.1/2, pp.244 - 262

Published online: 21 Feb 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article