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

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.