A divide-and-conquer strategy with particle swarm optimization for the job shop scheduling problem

References

• Adams , J. , Balas , E. and Zawack , D. 1988 . The shifting bottleneck procedure for job shop scheduling . Management Science , 34 ( 3 ) : 391 – 401 .
   Web of Science ®Google Scholar
• Amaral Armentano , V. and Rigão Scrich , C. 2000 . Tabu search for minimizing total tardiness in a job shop . International Journal of Production Economics , 63 ( 2 ) : 131 – 140 .
   Web of Science ®Google Scholar
• Anderson , E. J. and Nyirenda , J. C. 1990 . Two new rules to minimize tardiness in a job shop . International Journal of Production Research , 28 ( 12 ) : 2277 – 2292 .
   Web of Science ®Google Scholar
• Banks , A. , Vincent , J. and Anyakoha , C. 2007 . A review of particle swarm optimization – Part I: Background and development . Natural Computing , 6 ( 4 ) : 467 – 484 .
   Google Scholar
• Banks , A. , Vincent , J. and Anyakoha , C. 2008 . A review of particle swarm optimization – Part II: Hybridisation, combinatorial, multicriteria and constrained optimization, and indicative applications . Natural Computing , 7 ( 1 ) : 109 – 124 .
   Google Scholar
• Barnes , J. W. and Chambers , J. B. 1995 . Solving the job shop scheduling problem with tabu search . Transactions of the Institute of Industrial Engineers , 27 ( 2 ) : 257 – 263 .
   Web of Science ®Google Scholar
• Bassett , M. H. 1996a . Perspectives on model based integration of process operations . Computers & Chemical Engineering , 20 ( 6–7 ) : 821 – 844 .
   Web of Science ®Google Scholar
• Bassett , M. H. , Pekny , J. F. and Reklaitis , G. V. 1996b . Decomposition techniques for the solution of large-scale scheduling problems . AIChE Journal , 42 ( 12 ) : 3373 – 3387 .
   Web of Science ®Google Scholar
• Bitran , G. R. , Haas , E. A. and Hax , A. C. 1981 . Hierarchical production planning: a single system . Operations Research , 29 ( 4 ) : 717 – 743 .
   Web of Science ®Google Scholar
• Bożejko , W. and Makuchowski , M. 2008 . A fast hybrid tabu search algorithm for the no-wait job shop problem . Computers & Industrial Engineering , 56 ( 4 ) : 1502 – 1509 .
   Web of Science ®Google Scholar
• Braune , R. , Wagner , S. and Affenzeller , M. Optimization methods for large-scale production scheduling problems . Proceedings of the 11th international conference on computer aided systems theory (EUROCAST 2007) . February 12–16 2007 , Berlin:, Spain. Edited by: Moreno-Díaz , R. , Pichler , F. and Quesada-Arencibia , A. pp. 812 – 819 . Springer-Verlag . Lecture Notes in Computer Science 4739
   Google Scholar
• Brucker , P. 2004 . Scheduling algorithms , Berlin : Springer-Verlag .
   Google Scholar
• Byeon , E. S. , Wu , S. D. and Storer , R. H. 1998 . Decomposition heuristics for robust job-shop scheduling . IEEE Transactions on Robotics and Automation , 14 ( 2 ) : 303 – 313 .
   Google Scholar
• Chen , Z. L. and Powell , W. B. 1999 . A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem . European Journal of Operational Research , 116 ( 1 ) : 220 – 232 .
   Web of Science ®Google Scholar
• Chong , C. S. A bee colony optimization algorithm to job shop scheduling . Proceedings of the 38th conference on winter simulation (WSC’06), Monterey . December 3–6 , Monterey, CA. Edited by: Perrone , L. F. pp. 1954 – 1961 . Monterey Press .
   Google Scholar
• Chu , C. , Portmann , M. C. and Proth , J. M. 1992 . Splitting-up approach to simplify job-shop scheduling problems . International Journal of Production Research , 30 ( 4 ) : 859 – 870 .
   Web of Science ®Google Scholar
• Dell'Amico , M. and Trubian , M. 1993 . Applying tabu search to the job-shop scheduling problem . Annals of Operations Research , 41 ( 3 ) : 231 – 252 .
   Google Scholar
• Demirkol , E. , Mehta , S. and Uzsoy , R. 1997 . A computational study of shifting bottleneck procedures for shop scheduling problems . Journal of Heuristics , 3 ( 2 ) : 111 – 137 .
   Google Scholar
• Eberhart , R. and Kennedy , J. 1995 . A new optimizer using particle swarm theory . Proceedings of the sixth international symposium on micro machine and human science (MHS’95) . 4–6 1995 , New York:, Japan. October . pp. 39 – 43 . IEEE Press .
   Google Scholar
• Essafi , I. , Mati , Y. and Dauzère-Pérès , S. 2008 . A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem . Computers & Operational Research , 35 ( 8 ) : 2599 – 2616 .
   Web of Science ®Google Scholar
• Fox , B. , Xiang , W. and Lee , H. P. 2007 . Industrial applications of the ant colony optimization algorithm . International Journal of Advanced Manufacturing Technology , 31 ( 7–8 ) : 805 – 814 .
   Web of Science ®Google Scholar
• Gao , J. , Sun , L. and Gen , M. 2008 . A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems . Computers & Operations Research , 35 ( 9 ) : 2892 – 2907 .
   Web of Science ®Google Scholar
• Gélinas , S. and Soumis , F. 2005 . “ Dantzig–Wolfe decomposition for job shop scheduling ” . In Column generation , 271 – 302 . New York : Springer Science .
   Google Scholar
• Glover , F. 1986 . Future paths for integer programming and links to artificial intelligence . Computers & Operations Research , 13 ( 5 ) : 533 – 549 .
   Web of Science ®Google Scholar
• Glover , F. 1989 . Tabu search – Part I . ORSA Journal on Computing , 1 ( 3 ) : 190 – 206 .
   Google Scholar
• Glover , F. 1990 . Tabu search – Part II . ORSA Journal on Computing , 2 ( 1 ) : 4 – 32 .
   Google Scholar
• Grabowski , J. and Wodecki , M. 2005 . “ A very fast tabu search algorithm for job shop problem ” . In Metaheuristic optimization via memory and evolution: tabu search and scatter search , 117 – 144 . New York : Springer-Verlag .
   Google Scholar
• Graham , R. L. 1979 . Optimisation and approximation in deterministic sequencing and scheduling: a survey . Annals of Discrete Mathematics , 5 : 287 – 326 .
   Google Scholar
• Harjunkoski , I. and Grossmann , I. E. 2001 . A decomposition approach for the scheduling of a steel plant production . Computers & Chemical Engineering , 25 ( 11–12 ) : 1647 – 1660 .
   Web of Science ®Google Scholar
• Harjunkoski , I. and Grossmann , I. E. 2002 . Decomposition techniques for multistage scheduling problems using mixed-integer and constraint programming methods . Computers & Chemical Engineering , 26 ( 11 ) : 1533 – 1552 .
   Web of Science ®Google Scholar
• Huang , K. L. and Liao , C. J. 2008 . Ant colony optimization combined with taboo search for the job shop scheduling problem . Computers & Operations Research , 35 ( 4 ) : 1030 – 1046 .
   Web of Science ®Google Scholar
• Jensen , J. B. , Philipoom , P. R. and Malhotra , M. K. 1995 . Evaluation of scheduling rules with commensurate customer priorities in job shops . Journal of Operations Management , 13 ( 3 ) : 213 – 228 .
   Google Scholar
• Kennedy , J. and Eberhart , R. 1995 . Particle swarm optimization . Proceedings of the IEEE international conference on neural networks (ICNN’95) . November–December 27–1 1995 , New York:, Australia. Vol. 4 , IEEE Press . 1942–1948
   Google Scholar
• Kolonko , M. 1999 . Some new results on simulated annealing applied to the job shop scheduling problem . European Journal of Operational Research , 113 ( 1 ) : 123 – 136 .
   Web of Science ®Google Scholar
• Krishna , K. , Ganeshan , K. and Ram , D. J. 1995 . Distributed simulated annealing algorithms for job shop scheduling . IEEE Transactions on Systems, Man and Cybernetics , 25 ( 7 ) : 1102 – 1109 .
   Web of Science ®Google Scholar
• Krüger , K. 1995 . A heuristic decomposition algorithm for scheduling problems on mixed graphs . Journal of the Operational Research Society , 46 ( 12 ) : 1481 – 1497 .
   Web of Science ®Google Scholar
• Lenstra , J. K. , Kan , A. H.G.R. and Brucker , P. 1977 . Complexity of machine scheduling problems . Annals of Discrete Mathematics , 1 : 343 – 362 .
   Google Scholar
• Lian , Z. , Jiao , B. and Gu , X. 2006 . A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespan . Applied Mathematics and Computation , 183 ( 2 ) : 1008 – 1017 .
   Web of Science ®Google Scholar
• Liu , B. , Wang , L. and Jin , Y. H. 2007 . An effective PSO-based memetic algorithm for flow shop scheduling . IEEE Transactions on Systems, Man and Cybernetics – Part B: Cybernetics , 37 ( 1 ) : 18 – 27 .
   PubMed Web of Science ®Google Scholar
• Luh , P. B. 1998 . Job shop scheduling with group-dependent setups, finite buffers and long time horizon . Annals of Operations Research , 76 : 233 – 259 .
   Web of Science ®Google Scholar
• Luh , P. B. and Hoitomt , D. J. 1993 . Scheduling of manufacturing systems using the Lagrangian relaxation technique . IEEE Transactions on Automatic Control , 38 ( 7 ) : 1066 – 1080 .
   Web of Science ®Google Scholar
• Manikas , A. and Chang , Y. L. 2009 . A scatter search approach to sequence-dependent setup times job shop scheduling . International Journal of Production Research , 47 ( 18 ) : 5217 – 5236 .
   Web of Science ®Google Scholar
• Mason , S. J. , Fowler , J. W. and Carlyle , W. M. 2002 . A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops . Journal of Scheduling , 5 ( 3 ) : 247 – 262 .
   Web of Science ®Google Scholar
• Mönch , L. and Drießel , R. 2005 . A distributed shifting bottleneck heuristic for complex job shops . Computers & Industrial Engineering , 49 ( 3 ) : 363 – 380 .
   Web of Science ®Google Scholar
• Mönch , L. 2007 . Genetic algorithm-based subproblem solution procedures for a modified shifting bottleneck heuristic for complex job shops . European Journal of Operational Research , 177 ( 3 ) : 2100 – 2118 .
   Web of Science ®Google Scholar
• Nowicki , E. and Smutnicki , C. 1996 . A fast taboo search algorithm for the job shop problem . Management Science , 42 ( 6 ) : 797 – 813 .
   Web of Science ®Google Scholar
• Nowicki , E. and Smutnicki , C. 2005 . An advanced tabu search algorithm for the job shop problem . Journal of Scheduling , 8 ( 2 ) : 145 – 159 .
   Web of Science ®Google Scholar
• Ovacik , I. M. and Uzsoy , R. 1997 . Decomposition methods for complex factory scheduling problems , Boston, MA : Kluwer Academic .
   Google Scholar
• Panwalkar , S. S. and Iskander , W. 1977 . A survey of scheduling rules . Operations Research , 25 ( 1 ) : 45 – 61 .
   Web of Science ®Google Scholar
• Park , M. W. and Kim , Y. D. 1998 . A systematic procedure for setting parameters in simulated annealing algorithms . Computers & Operations Research , 25 ( 3 ) : 207 – 217 .
   Web of Science ®Google Scholar
• Pinedo , M. and Singer , M. 1999 . A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop . Naval Research Logistics , 46 ( 1 ) : 1 – 17 .
   Web of Science ®Google Scholar
• Ponnambalam , S. G. , Jawahar , N. and Aravindan , P. 1999 . A simulated annealing algorithm for job shop scheduling . Production Planning & Control , 10 ( 8 ) : 767 – 777 .
   Web of Science ®Google Scholar
• Rigão Scrich , C. , Amaral Armentano , V. and Laguna , M. 2004 . Tardiness minimization in a flexible job shop: a tabu search approach . Journal of Intelligent Manufacturing , 15 ( 1 ) : 103 – 115 .
   Web of Science ®Google Scholar
• Rivera , D. C. , Becerra , R. L. and Coello , C. A.C. 2007 . Cultural algorithms, an alternative heuristic to solve the job shop scheduling problem . Engineering Optimization , 39 ( 1 ) : 69 – 85 .
   Web of Science ®Google Scholar
• Sannomiya , N. and Iima , H. Genetic algorithm approach to an optimal scheduling problem for a large-scale complex manufacturing system . Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC’99) . October 12–15 1999 , New York:, Japan. Vol. 3 , pp. 622 – 627 . IEEE Press .
   Google Scholar
• Sha , D. Y. and Hsu , C. Y. 2006 . A hybrid particle swarm optimization for job shop scheduling problem . Computers & Industrial Engineering , 51 ( 4 ) : 791 – 808 .
   Web of Science ®Google Scholar
• Singer , M. 2001 . Decomposition methods for large job shops . Computers & Operations Research , 28 ( 3 ) : 193 – 207 .
   Web of Science ®Google Scholar
• Sun , D. and Batta , R. 1996 . Scheduling larger job shops: a decomposition approach . International Journal of Production Research , 34 ( 7 ) : 2019 – 2033 .
   Web of Science ®Google Scholar
• Taillard , E. D. 1994 . Parallel taboo search techniques for the job shop scheduling problem . ORSA Journal on Computing , 6 ( 2 ) : 108 – 117 .
   Google Scholar
• Tang , L. 2002 . Steel-making process scheduling using Lagrangian relaxation . International Journal of Production Research , 40 ( 1 ) : 55 – 70 .
   Web of Science ®Google Scholar
• Tasgetiren , M. F. 2006 . Particle swarm optimization and differential evolution for the single machine total weighted tardiness problem . International Journal of Production Research , 44 ( 22 ) : 4737 – 4754 .
   Web of Science ®Google Scholar
• Tasgetiren , M. F. 2007 . A particle swarm optimization algorithm for makespan and total flowtime minimization in the permutation flowshop sequencing problem . European Journal of Operational Research , 177 ( 3 ) : 1930 – 1947 .
   Web of Science ®Google Scholar
• Upasani , A. A. , Uzsoy , R. and Sourirajan , K. 2006 . A problem reduction approach for scheduling semiconductor wafer fabrication facilities . IEEE Transactions on Semiconductor Manufacturing , 19 ( 2 ) : 216 – 225 .
   Web of Science ®Google Scholar
• Van den Akker , M. , Hoogeveen , H. and Van de Velde , S. 2005 . “ Applying column generation to machine scheduling. In ” . In Column generation , 303 – 330 . New York : Springer Science .
   Google Scholar
• Van Laarhoven , P. J.M. , Aarts , E. H.L. and Lenstra , J. K. 1992 . Job shop scheduling by simulated annealing . Operations Research , 40 ( 1 ) : 113 – 125 .
   Web of Science ®Google Scholar
• Vepsalainen , A. P. and Morton , T. E. 1987 . Priority rules for job shops with weighted tardy costs . Management Science , 33 ( 8 ) : 95 – 103 .
   Web of Science ®Google Scholar
• Wang , T. Y. and Wu , K. B. 2000 . A revised simulated annealing algorithm for obtaining the minimum total tardiness in job shop scheduling problems . International Journal of Systems Science , 31 ( 4 ) : 537 – 542 .
   Web of Science ®Google Scholar
• Wu , D. and Ierapetritou , M. G. 2003 . Decomposition approaches for the efficient solution of short-term scheduling problems . Computers & Chemical Engineering , 27 ( 8–9 ) : 1261 – 1276 .
   Web of Science ®Google Scholar
• Wu , S. D. , Byeon , E. S. and Storer , R. H. 1999 . A graph-theoretic decomposition of the job shop scheduling problem to achieve scheduling robustness . Operations Research , 47 ( 1 ) : 113 – 124 .
   Web of Science ®Google Scholar
• Xi , Y. and Fang , J. 1997 . A rolling horizon job shop rescheduling strategy in the dynamic environment . The International Journal of Advanced Manufacturing Technology , 13 ( 3 ) : 227 – 232 .
   Web of Science ®Google Scholar
• Xia , W. and Wu , Z. 2006 . A hybrid particle swarm optimization approach for the job-shop scheduling problem . International Journal of Advanced Manufacturing Technology , 29 ( 3–4 ) : 360 – 366 .
   Web of Science ®Google Scholar
• Zhang , C. Y. 2008 . A very fast TS/SA algorithm for the job shop scheduling problem . Computers & Operations Research , 35 ( 1 ) : 282 – 294 .
   Web of Science ®Google Scholar
• Zhang, R. and Wu, C., 2009. A hybrid approach to large-scale job shop scheduling. Applied Intelligence. Available online, DOI 10.1007/s10489-008-0134-y
   Google Scholar
• Zhou , H. , Cheung , W. and Leung , L. C. 2009 . Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm . European Journal of Operational Research , 194 ( 3 ) : 637 – 649 .
   Web of Science ®Google Scholar