본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

Survey of Evolutionary Algorithms in Advanced Planning and Scheduling

Gen, Mitsuo    (Graduated School of Information, Production and Systems, Waseda University   ); Zhang, Wenqiang    (Graduated School of Information, Production and Systems, Waseda University   ); Lin, Lin    (Information, Production and Systems Research Center, Waseda University  );
  • 초록

    Advanced planning and scheduling (APS) refers to a manufacturing management process by which raw materials and production capacity are optimally allocated to meet demand. APS is especially well-suited to environments where simpler planning methods cannot adequately address complex trade-offs between competing priorities. However, most scheduling problems of APS in the real world face both inevitable constraints such as due date, capability, transportation cost, set up cost and available resources. In this survey paper, we address three crucial issues in APS, including basic scheduling model, job-shop scheduling (JSP), assembly line balancing (ALB) model, and integrated scheduling models for manufacturing and logistics. Several evolutionary algorithms which adapt to the problems are surveyed and proposed; some test instances based on the practical problems demonstrate the effectiveness and efficiency of evolutionary approaches.


  • 주제어

    Advanced Planning and Scheduling (APS) .   Evolutionary Algorithm .   Job-Shop Scheduling (JSP) .   Assembly Line Balancing (ALB) .   Integrated Scheduling Models for Manufacturing and Logistics.  

  • 참고문헌 (115)

    1. Altiparmak, F., Gen, M., Lin, L. and Karaoglan, I. (2007), A steady-state genetic algorithm for multi-product supply chain network design, Computers and Industrial Engineering, Available online June 
    2. Amiri, A. (2004), Designing a distribution network in a supply chain system : formulation and efficient solution procedure, European Journal of Operational Research, 171(2), 567-576 
    3. Bean, J. C. (1994), Genetics and random keys for sequencing and optimization, ORSA Journal on Computing, 6, 154-160 
    4. Brucker, P. (1998), Scheduling Algorithms, Springer 
    5. Brudaru, O. and Valmar, B. (2004), Genetic algorithm with embryonic chromosomes for assembly line balancing with fuzzy processing times, The 8th International Research/Expert Conference Trends in the Development of Machinery and Associated Technology, TMT 2004, Neum, Bosnia and Herzegovina 
    6. Bruker, P. and Schlie, R. (1990), Job-shop scheduling with multi-purpose machines, Computing, 45, 369-375 
    7. Cheng, R., Gen, M., and Tsujimura, Y. (1999), A tutorial surveyof job-shop scheduling problems using genetic algorithms, part II : hybrid genetic Search Strategies, Computers and Industrial Engineering, 36(2), 343-364 
    8. Dellaert, N., Jeunet, J., and Jornard, N. (2000), A genetic algorithm to solve the general multi-level lot-sizing problem with time-varying costs, International Journal of Production Economy, 68, 241-257 
    9. Eck, M. (2003), Advanced Planning and Scheduling, BWI paper: http://obp.math.vu.nl/logistics/papers/vaneck.doc. 
    10. Gen, M. and Cheng, R. (1997), Genetic Algorithms and Engineering Design, New York : John Wiley and Sons 
    11. Gen, M. and Cheng, R. (2000), Genetic Algorithms and Engineering Optimization, New York : John Wiley and Sons 
    12. Gen, M. and Zhang, H.(2006) : Effective designing chromosome for optimizing advanced planning and scheduling, C. H. Dagli et al., eds. : Intelligent Engineering Systems Through Artificial Neural Networks, 16, 61-66, ASME Press 
    13. Goncalves, J. F., Magalhaes Mendes, J. J., and Resende, M. G. C. (2005), A hybrid genetic algorithm for the job shop scheduling problem, European Journal of Operational Research, 167(1), 77-95 
    14. Kim, H. and Park, S. (1995), Strong cutting plane algorithm for the robotic assembly line balancing, International Journal of Production Research, 33, 2311-2323 
    15. Krasnogor, N. and Smith, J. (2000), A memetic algorithm with self-adaptive local search : TSP as a case study, Proceedings of Genetic and Evolutionary Computation Conference, July 10-12, Las Vegas, NV, 987-994, 2000 
    16. Mati, Y., Rezg, N., and Xie, X. (2001), An integrated greedy heuristic for a flexible job shop scheduling problem, IEEE International Conference on Systems, Man, and Cybernetics, 4, 2534-2539 
    17. Miltenburg, J. (2002), Balancing and sequencing mixed-model U-shaped production lines, International Journal of Flexible Manufacturing Systems, 14, 119-151 
    18. Moon, C. (2004b), Evolutionary System Approach for Advanced Planning in Multi-Plant Chain, Ph. D. dissertation, Waseda University, Japan 
    19. Moon, C., Kim, J. S., and Gen, M. (2004a), Advanced planning and scheduling based on precedence and resource constraints for e-plant chains, International Journal of Production Research, 42(15), 2941-2955 
    20. Moscato, P. and Norman, M. (1992), A memetic approach for the traveling salesman problem : implementation of a computational ecology for combinatorial optimization on messagepassing systems, Proceedings of the International Conference on Parallel Computing and Transputer Applications, Amsterdam 
    21. Nicosia, G., Paccarelli, D., and Pacifici, A. (2002), Optimally balancing assembly lines with different workstations, Discrete Applied Mathematics, 118, 99-113 
    22. Noorul Haq, A., Jayaprakash, J., and Rengarajan, K. (2006), A hybrid genetic algorithm approach to mixed-model assembly line balancing, International Journal of Advanced Manufacturing Technology, 28, 337-341 
    23. Nowicki, E., and Smutnicki, C. (2005), An advanced tabu search algorithm for the job-shop problem, Journal of Scheduling, 8(2), 145-159 
    24. Okamoto, A. (2007), Study on Integrated Scheduling for Manufacturing and Logistics Information System using Hybrid Genetic Algorithm, Ph. D. dissertation, Waseda University, Japan 
    25. Okamoto, A., Gen, M., and Sugawara, M. (2006b), Integrated Scheduling Problem of Manufacturing and Transportation with Pickup and Delivery', International Journal of Logistics and SCM Systems, 1, 19-27 
    26. PSLX Consortium (2003), PSLX Technical Specifications, Recommendation, Version 1.0, [Online]. Available : http://www.pslx.org/ 
    27. Rekiek, B. and Delchambre, A. (2006), Assembly line design : The balancing of mixed-model hybrid assembly lines with genetic algorithms, Springer Series in Advanced Manufacturing, London 
    28. Salveson, M. E. (1955), The assembly line balancing problem, Journal of Industrial Engineering, 6, 18-25 
    29. Scholl, A. (1999), Balancing and Sequencing of Assembly Lines, Physica-Verlag, Heidelberg 
    30. Syarif, A., Yun, Y., and Gen, M. (2002), Study on multi-stage logistics chain network : a spanning tree-based genetic algorithm approach, Computers and Industrial Engineering, 43, 299-314 
    31. Tan, W. (2000), Integration of process planning and scheduling-a review, Journal of Intelligent Manufacturing, 11(1), 51-63 
    32. Tavakkoli-Moghaddam, R., Jolai, F., Vaziri, F., Ahmed, P. K., and Azaron, A. (2005), A hybrid method for solving stochastic job shop scheduling problems, Applied Mathematics and Computation, 170(1), 185-206 
    33. W3C (2004), Extensible Markup Language (XML) 1.0 (3rd Edition), W3C Recommendation, [Online]. Available : http://www.w3.org/TR/2004/REC-xml-20040204 
    34. Yan, H., Yu Z., and Cheng, T. C. E. (2003), A strategic model for supply chain design with logical constraints: formulation and solution, Computers and Operations Research, 30(14), 2135-2155 
    35. Yang, J. B. (2001), GA-based discrete dynamic programming approach for scheduling in FMS environments, IEEE Transactions on Systems, Man and Cybernetics, Part B, 31(5), 824-835 
    36. Yang, S. and Wang, D. (2000), Constraint satisfaction adaptive neural network and heuristics combined approaches for generalized job-shop scheduling, IEEE Trans. on Neural Networks, 11(2), 474-486 
    37. Erel, E. and Sarin, S. C. (1998), A survey of the assembly line balancing procedures, Production Planning and Control, 9, 414-434 
    38. Scholl, A. (1993), Data of Assembly Line Balancing Problems, Schriften zur Quantitativen Betriebswirtschaftslehre 16/93, Th Darmstadt 
    39. Lee, C. Y. and Chen, Z.-L. (2001), Machine scheduling with transportation considerations, Journal of Scheduling, 4, 3-24 
    40. Lopez, O. and Ramirez, M. (2005), A STEP-based manufacturing information system to share flexible manufacturing resources data, Journal of Intelligent Manufacturing, 16(3), 287-301 
    41. Rubinovitz, J. and Bukchin, J. (1993), RALB-a heuristic algorithm for design and balancing of robotic assembly line, Annals of the CIRP, 42, 497-500 
    42. Chan, F. T. S., Chung, S. H., and Wadhwa, S. (2004), A hybrid genetic algorithm for production and distribution, Omega, 33, 345-355 
    43. Khouja, M., Booth, D. E., Suh, M., and Mahaney, Jr. J. K. (2000), Statistical procedures for task assignment and robot selection in assembly cells, International Journal of Computer Integrated manufacturing, 13, 95-106 
    44. Okamoto, A., Gen, M., and Sugawara, M. (2006a), Integrated data structure and scheduling approach for manufacturing and transportation using hybrid multistage operation-based genetic algorithm, Journal of Intelligent Manufacturing, 17, 411-421 
    45. Ozmehmet Tasan, S. and Tunali, S. (2008), A review of the current applications of genetic algorithms in assembly line balancing, Journal of Intelligent Manufacturing, 19(1), 49-69 
    46. Wu, Z. and Weng, M. X. (2005), Multiagent scheduling method with earliness and tardiness objectives in flexible job shops, IEEE Trans. System, Man, and Cybernetics-Part B, 35(2), 293-301 
    47. Scholl, A. and Voss, S. (1996), Simple assembly line balancing-heuristic approaches, Journal of Heuristics, 2, 217-244 
    48. Zhang, H. P. (2006), Study on Evolutionary Scheduling Problems in Integrated Manufacturing System, Ph. D. dissertation, Waseda University, Japan 
    49. Zhang, H. and Gen, M. (2005), Multistage-based genetic algorithm for flexible job-shop scheduling problem, Journal of Complexity International, 11, 223-232 
    50. Rubinovitz, J. and Bukchin, J. (1991), Design and balancing of robotic assembly lines, Proceedings of the 4th World Conference on Robotics Research, Pittsburgh, PA 
    51. Scholl, A. and Becker, C. (2006), State-of-the-art exact and heuristic solution procedures for simple assembly line balancing, European Journal of Operational Research, 168, 666-693 
    52. Bukchin, J., and Tzur, M. (2000), Design of flexible assembly line to minimize equipment cost, IIE Transactions, 32, 585-598 
    53. Roy, B. and Sussmann, B. (1964), Les problems d’ordonnancement avec contraintes disjonctives, Note D.S. No. 9 bis, SEMA, Paris, France 
    54. Altiparmak, F., Gen, M., Lin, L., and Paksoy, T. (2006), A genetic algorithm approach for multiobjective optimization of supply chain networks, Computers and Industrial Engineering, 51(1), 197-216 
    55. Gen, M. and Syarif, A. (2005), Hybrid genetic algorithm for multi-time period production /distribution planning, Computers and Industrial Engineering, 48(4), 799-809 
    56. Karp, R. M. (1972), Reducibility among combinatorial problems. In Miller R.E and Thatcher J.W. Editors : Complexity of Computer Applications, 85-104, New York : Plenum Press 
    57. Rekiek, B., Dolgui, A., Delchambre, A., and Bratcu, A. (2002), State of art of optimization methods for assembly line design, Annual Reviews in Control, 26, 163-174 
    58. Blazewicz, J., Ecker, K. H., Schmidt, G., and Weglarz, J. (1994), Scheduling in Computer and Manufacturing Systems, Springer 
    59. Raa, B. and Aghezzaf, E. H. (2005), A robust dynamic planning strategy for lot-sizing problems with stochastic demands, Journal of Intelligent Manufacturing, 16(2), 207-213 
    60. Chan, F. T. S. and Chung, S. H. (2004), A multi-criterion genetic algorithm for order distribution in a demand driven supply chain, International Journal of Computer Integrated Manufacturing, 17(4), 339-351 
    61. Grabot, B. and Geneste, L. (1994), Dispatching rules in scheduling: A fuzzy approach, International Journal of Production Research, 32(4), 903-915 
    62. Helgeson, W. B., Salveson, M. E., and Smith, W. W. (1954), How to balance an assembly line, Technical Report, Carr Press, New Caraan, Conn 
    63. Najid, N. M., Dauzere-Peres, S., and Zaidat, A. (2002), A modified simulated annealing method for flexible job shop scheduling problem, IEEE International Conference on Systems, Man and Cybernetics, 5(6) 
    64. Bowman, E. H. (1960), Assembly line balancing by linear programming. Operations Research, 8(3), 385-389 
    65. Guillen, G., Mele, F. D., Bagajewicz, M. J., Espuna, A., and Puigjaner, L. (2005), Multiobjective supply chain design under uncertainty, Chemical Engineering Science, 60, 1535-1553 
    66. Xia, W. and Wu, Z. (2005), An effective hybrid optimization approach for muti-objective flexible job-shop scheduling problem, Computers and Industrial Engineering, 48, 409-425 
    67. Bautista, J. and Pereira, J. (2002), Ant algorithms for assembly line balancing, Lecture Notes in Computer Science, 2463, 65-75 
    68. Bautista, J., Suarez, R., Mateo, M., and Companys, R. (2000), Local search heuristics for the assembly line balancing problem with incompatibilities between tasks, Proceedings of the 2000 IEEE International Conference on Robotics and Automation, San Francisco, CA, 2404- 2409 
    69. Tsai, D. M. and Yao, M. J (1993), A line-balanced-base capacity planning procedure for series type robotic assembly line, International Journal of Production Research, 31, 1901-1920 
    70. Baker, K. (1974), Introduction to sequencing and scheduling, New York, John Wiley and Sons 
    71. Gen, M., Altiparamk, F., and Lin, L. (2006), A genetic algorithm for two-stage transportation problem using priority-based encoding, OR Spectrum, 28(3), 337-354 
    72. Jayaraman, V. and Ross, A. (2003), A simulated annealing methodology to distribution network design and management, European Journal of Operational Research, 144, 629-645 
    73. Okamoto, A., Gen, M., and Sugawara, M. (2005), APS system based on scheduler moGA and XML, Journal of the Society of Plant Engineers Japan, 17(2), 15-24, (in Japanese) 
    74. Adams, J., Balas, E., and Zawack, D. (1987), The shifting bottleneck procedure for job shop scheduling, International Journal of Flexible Manufacturing Systems, 34(3), 391-401 
    75. Erol, I. and Ferrell Jr. W. G. (2004), A methodology to support decision making across the supply chain of an industrial distributor, International Journal of Production Economics, 89, 119-129 
    76. Jackson, J. R. (1956), A Computing Procedure for a Line Balancing Problem, Management Science, 2, 261-272 
    77. Jayaraman, V. and Pirkul, H. (2001), Planning and coordination of production and distribution facilities for multiple commodities, European Journal of Operational Research, 133, 394-408 
    78. Kacem, I., Hammadi, S., and Borne, P. (2002), Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems, IEEE Trans. Systems, Man, and Cybernetics-Part C, 32(1), 1-13 
    79. Runarsson, T. P. and Jonsson, M. T. (1999), Genetic production systems for intelligent problem solving, Journal of Intelligent Manufacturing, 10, 181-186 
    80. Soukhal, A., Oulamara, A., and Martineau, P. (2005), Complexity of flow shop scheduling problems with transportation constraints, European Journal of Operational Research, 161, 32-41 
    81. Tan, W. (2004), A linearized polynomial mixed integer programming model for the integration of process planning and scheduling, Journal of Intelligent Manufacturing, 15(5), 593-605 
    82. Cheng, R., Gen, M., and Tsujimura, Y. (1996), A tutorial survey of job-shop scheduling problems using genetic algorithm, part I : representation, Computers and Industrial Engineering, 30(4), 983-997 
    83. Goncalves, J. F. and De Almedia, J. R. (2002), A hybrid genetic algorithm for assembly line balancing, Journal of Heuristic, 8, 629-642 
    84. Talbot, F. B., Patterson, J. H., and Gehrlein, W. V. (1986), A comparative evaluation of heuristic line balancing techniques, Management Science, 32, 430 - 454 
    85. Truong, T. H. and Azadivar, F. (2005), Optimal design methodologies for configuration of supply chains, International Journal of Production Research, 43(11), 2217-2236 
    86. Okamoto, A., Gen, M., and Sugawara, M. (2005), APS System based on Scheduler moGA and XML, Journal of the Society of Plant Engineers Japan, 17(2), 15-24, (in Japanese) 
    87. Baybars, I. (1986), A survey of exact algorithms for the simple assembly line balancing problem, Management Science, 32, 909-932 
    88. Chen, C. and Lee, W. (2004), Multi-objective optimization of multi-echelon supply chain networks with uncertain product demands and prices, Computers and Chemical Engineering, 28, 1131-1144 
    89. Fisher, H. and Thompson, G. (1963), Probabilistic learning combinations of job-shop scheduling rules, Industrial Scheduling, 15, 1225-1251 
    90. Gen, M., Cheng, R., and Lin, L. (2008), Network Models and Optimization : Multiobjective Genetic Algorithm Approach, Springer, London 
    91. Ida, k. and Osawa, A. (2005), Proposal of algorithm for shortening idle time on job-shop scheduling problem and its numerical experiments, Journal of Japanese Industrial Management Assoc, 56(4), 294-301, (in Japanese) 
    92. Dar-El, E. M. (1973), MALB-A heuristic technique for balancing large single-model assembly lines, AIIE Transactions, 5(4), 343-356 
    93. Kacem, I., Hammadi, S., and Borne, P. (2002), Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems, IEEE Trans. Systems, Man, and Cybernetics-Part C, 32(1), 1-13 
    94. Levitin, G., Rubinovitz, J., and Shnits, B. (2006), A genetic algorithm for robotic assembly line balancing, European Journal of Operational Research, 168, 811-825 
    95. Held, M., Karp, R. M., and Shareshian, R. (1963), Assembly line balancing-Dynamic programming with precedence constraints, Operations Research, 11, 442-459 
    96. Leu, Y. Y., Matheson, L. A., and Rees, L. P. (1994), Assembly line balancing using genetic algorithms with heuristic generated initial populations and multiple criteria, Decision Sciences, 15, 581-606 
    97. Orvosh, D. and Davis, L. (1994), Using a genetic algorithm to optimize problems with Feasibility constrains, Proceedings of the First IEEE Conference on Evolutionary Computation, 548-552 
    98. Balas, E. (1969), Machine Scheduling via disjunctive graphs : An implicit enumeration algorithm, Operation Research, 17, 941-957 
    99. Falkenauer, E. and Delchambre, A. (1992), A genetic algorithm for bin packing and line balancing, Proceedings of the 1992 IEEE International Conference on Robotics and Automation, Nice, France, 1189-1192 
    100. Gao, J., Gen, M., Sun, L., and Zhao, X. (2007), A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems, Computers and Industrial Engineering, 53(1), 149-162 
    101. Kim, Y. K., Kim, Y., and Kim, Y. J. (2000), Two-sided assembly line balancing : a genetic algorithm approach, Production Planning and Control, 11(1), 44-53 
    102. Su, P., Wu, N., and Yu, Z. (2003) Resource selection for distributed manufacturing in agile manufacturing, Proc. of IEEE International Conference on Systems, Man and Cybernetics, 2(1), 1578-1582 
    103. Anderson, E. J. and Ferris, M. C. (1994), Genetic algorithms for combinatorial optimization : the assembly line balancing problem, ORSA Journal on Computing, 6, 161-173 
    104. Brandimarte, P. (1993), Routing and scheduling in a flexible job shop by tabu search, Annals of Operations Research, 41, 157-183 
    105. French, S. (1982), Sequencing and Scheduling. Mathematics and its applications, Ellis Horwood Limited 
    106. Ghosh, S. and Gagnon, R. J. (1989), A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems, International Journal of Production Research, 27, 637-670 
    107. Kim, Y. K., Kim, Y. J., and Kim, Y. H. (1996), Genetic algorithms for assembly line balancing with various objectives, Computers and Industrial Engineering, 30(3), 397-409 
    108. MESX Joint Working Group. (2004), MESX White Paper, [Online]. Available : http://www.mstc.or.jp/faop/doc/informative/MESX-WP.pdf, (in Japanese) 
    109. Suresh, G. and Sahu, S. (1994), Stochastic assembly line balancing using simulated annealing, International Journal of Production Research, 32(8), 1801-1810 
    110. Becker, C. and Scholl, A. (2006), A survey on problems and methods in generalized assembly line balancing, European Journal of Operational Research, 168, 694-715 
    111. Jain A. S. and Meeran S. (1998), A state-of -the-art review of job-shop scheduling techniques, technical report, department of applied physics, Electronics and Mechanical Engineering, University of Dundee, Scotland 
    112. Sabri, E. H. and Beamon, B. M. (2000), A multi-objective approach to simultaneous strategic and operational planning in supply chain design, Omega, 28, 581-598 
    113. Gao, J., Sun, L., and Gen, M. (2008), A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems, Computer and Operations Research, 35(9), 2892-2907 
    114. Sabuncuoglu, I., Erel, E., and Tanyer, M. (2000), Assembly line balancing using genetic algorithms, Journal of Intelligent Manufacturing, 11(3) 295-310 
    115. Syam, S. S. (2002), A model and methodologies for the location problem with logistical components, Computers and Operations Research, 29, 1173-1193 
  • 이 논문을 인용한 문헌 (1)

    1. 2012. "" Industrial engineering & management systems : an international journal, 11(4): 310~330     

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기