Study on constraint scheduling algorithm for job shop problems with multiple constraint machines

Abstract

This paper focuses on a job-shop scheduling problem with multiple constraint machines (JSPMC). A constraint scheduling method for the JSPMC is proposed. It divides the machines in the shop into constraint and non-constraint machines based on a new identification method, and formulates a reduced problem only for constraint machines while replacing the operations of non-constraint machines with time lags. The constraint machines are scheduled explicitly by solving the reduced problem with an efficient heuristic, while the non-constraint machines are scheduled by the earliest operation due date (EODD) dispatching rule. Extensive computational results indicate that the proposed constraint scheduling algorithm can obtain a better trade-off between solution quality and computation time compared with various versions of the shifting bottleneck (SB) methods for the JSPMC.

Keywords:

• Scheduling
• Job shop
• Constraint machine
• Shifting bottle neck

Acknowledgments

This research was supported by the National Natural Science Foundation of China (Grant No. 60474002, 60504026) and the National High Tech. Project (Grant No. 2006AA04Z173).