Title :
A multistage algorithm for the job shop scheduling problem
Author :
Cui, Jianshuang ; Cheng, Liang ; Li, Tieke
Author_Institution :
Sch. of Econ. & Manage., Univ. of Sci. & Technol. Beijing, Beijing, China
Abstract :
This paper presents a multistage algorithm for the job shop scheduling problem (JSP). A theorem is proved that the calculability of a solution is the sufficient and necessary condition for its feasibility. Therefore, an infeasible solution will be discarded immediately and the improved critical path algorithm is applied to perform the local search for a feasible solution. The computational results of the standard benchmark problems achieved by the new multistage algorithm demonstrate that the algorithm obtains high-quality solutions within reasonable time.
Keywords :
critical path analysis; job shop scheduling; critical path algorithm; job shop scheduling; local search; multistage algorithm; Approximation algorithms; Approximation methods; Computer science; Engineering management; Flowcharts; Job shop scheduling; Large-scale systems; Optimization methods; Scheduling algorithm; Technology management; Job shop scheduling; improved critical path; makespan; neighborhood swapping;
Conference_Titel :
Industrial Engineering and Engineering Management, 2009. IEEM 2009. IEEE International Conference on
Conference_Location :
Hong Kong
Print_ISBN :
978-1-4244-4869-2
Electronic_ISBN :
978-1-4244-4870-8
DOI :
10.1109/IEEM.2009.5372908
