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.
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).