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

Publisher:
Taylor & Francis Ltd
Publication Type:
Journal Article
Citation:
International Journal Of Production Research, 2008, 46 (17), pp. 4785 - 4801
Issue Date:
2008-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2012007931OK.pdf191.63 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: