A late acceptance hill-climbing algorithm for balancing two-sided assembly lines with multiple constraints

详细信息    查看全文

• 作者：Biao Yuan (1)
  Chaoyong Zhang (2)
  Xinyu Shao (2)
  
• 关键词：Two ; sided assembly line balancing ; Late acceptance hill ; climbing ; Multiple constraints
• 刊名：Journal of Intelligent Manufacturing
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：26
• 期：1
• 页码：159-168
• 全文大小：636 KB
• 参考文献：1. Abuhamdah, A. (2010). Experimental result of late acceptance randomized descent algorithm for solving course timetabling problems. / International Journal of Computer Science and Network Security, / 10(1), 192鈥?00.
  2. Abuhamdah, A., & Ayob, M. (2010). Average late acceptance randomized descent algorithm for solving course timetabling problems. In / Information Technology (ITSim), 2010 International Symposium (pp. 748鈥?53).
  3. Bartholdi, J. (1993). Balancing two-sided assembly lines: A case study. / International Journal of Production Research, / 31(10), 2447鈥?461. CrossRef
  4. Baykasoglu, A. (2006). Multi-rule multi-objective simulated annealing algorithm for straight and U type assembly line balancing problems. / Journal of Intelligent Manufacturing, / 17(2), 217鈥?32. CrossRef
  5. Baykasoglu, A., & Dereli, T. (2008). Two-sided assembly line balancing using an ant-colony-based heuristic. / International Journal of Advanced Manufacturing Technology, / 36, 582鈥?88. CrossRef
  6. Burke, E. K., & Bykov, Y. (2008). A late acceptance strategy in hill-climbing for exam timetabling problems. In / Conference on the practice and theory of automated timetabling, Montreal, Canada.
  7. Chutima, P., & Chimklai, P. (2012). Multi-objective two-sided mixed-model assembly line balancing using particle swarm optimisation with negative knowledge. / Computers & Industrial Engineering, / 62(1), 39鈥?5. CrossRef
  8. Hu, X. F., Wu, E. F., & Jin, Y. (2008). A station-oriented enumerative algorithm for two-sided assembly line balancing. / European Journal of Operational Research, / 186(1), 435鈥?40. CrossRef
  9. Hu, X. F., Wu, E. F., Bao, J. S., & Jin, Y. (2010). A branch-and-bound algorithm to minimize the line length of a two-sided assembly line. / European Journal of Operational Research, / 206(3), 703鈥?07. CrossRef
  10. Kim, Y. K., Kim, Y. H., & Kim, Y. J. (2000). Two-sided assembly line balancing: A genetic algorithm approach. / Production Planning & Control, / 11(1), 44鈥?3. CrossRef
  11. Kim, Y. K., Song, W. S., & Kim, J. H. (2009). A mathematical model and a genetic algorithm for two-sided assembly line balancing. / Computers & Operations Research, / 36(3), 853鈥?65. CrossRef
  12. Lee, T. O., Kim, Y., & Kim, Y. K. (2001). Two-sided assembly line balancing to maximize work relatedness and slackness. / Computers & Industrial Engineering, / 40(3), 273鈥?92. CrossRef
  13. Ozbakir, L., & Tapkan, P. (2010). Balancing fuzzy multi-objective two-sided assembly lines via bees algorithm. / Journal of Intelligent & Fuzzy Systems, / 21(5), 317鈥?29.
  14. Ozbakir, L., & Tapkan, P. (2011). Bee colony intelligence in zone constrained two-sided assembly line balancing problem. / Expert Systems with Applications, / 38(9), 11947鈥?1957. CrossRef
  15. Ozcan, U. (2010). Balancing stochastic two-sided assembly lines: A chance-constrained, piecewise-linear, mixed integer program and a simulated annealing algorithm. / European Journal of Operational Research, / 205(1), 81鈥?7. CrossRef
  16. Ozcan, U., & Toklu, B. (2009a). A new hybrid improvement heuristic approach to simple straight and U-type assembly line balancing problems. / Journal of Intelligent Manufacturing, / 20(1), 123鈥?36. CrossRef
  17. Ozcan, U., & Toklu, B. (2009b). Multiple-criteria decision-making in two-sided assembly line balancing: A goal programming and a fuzzy goal programming models. / Computers & Operations Research, / 36(6), 1955鈥?965. CrossRef
  18. Ozcan, U., & Toklu, B. (2009c). A tabu search algorithm for two-sided assembly line balancing. / International Journal of Advanced Manufacturing Technology, / 43, 822鈥?29. CrossRef
  19. Ozcan, U., & Toklu, B. (2009d). Balancing of mixed-model two-sided assembly lines. / Computers & Industrial Engineering, / 57(1), 217鈥?27. CrossRef
  20. Sabuncuoglu, I., Erel, E., & Tanyer, M. (2000). Assembly line balancing using genetic algorithms. / Journal of Intelligent Manufacturing, / 11(3), 295鈥?10.
  21. Simaria, A. S., & Vilarinho, P. M. (2009). 2-ANTBAL: An ant colony optimisation algorithm for balancing two-sided assembly lines. / Computers & Industrial Engineering, / 56(2), 489鈥?06. CrossRef
  22. Tasan, S. O., & Tunali, S. (2008). A review of the current applications of genetic algorithms in assembly line balancing. / Journal of Intelligent Manufacturing, / 19(1), 49鈥?9. CrossRef
  23. Tapkan, P., Ozbakir, L., & Baykasoglu, A. (2012). Bees algorithm for constrained fuzzy multi-objective two-sided assembly line balancing problem. / Optimization Letters, / 6(6), 1039鈥?049. CrossRef
  24. Verstichel, J., & Berghe, G. V. (2009). A late acceptance algorithm for the lock scheduling problem. / Logistic Management, / 5, 457鈥?78. CrossRef
  25. Wu, E. F., Jin, Y., Bao, J. S., & Hu, X. F. (2008). A branch-and-bound algorithm for two-sided assembly line balancing. / International Journal of Advanced Manufacturing Technology, / 39, 1009鈥?015. CrossRef
  
• 作者单位：Biao Yuan (1)
  Chaoyong Zhang (2)
  Xinyu Shao (2)
  
  1. Department of Industrial Engineering and Logistics Management, School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai, China
  2. State Key Laboratory of Digital Manufacturing Equipment and Technology, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan, Hubei, China
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Production and Logistics
  Manufacturing, Machines and Tools
  Automation and Robotics
  
• 出版者：Springer Netherlands
• ISSN：1572-8145

文摘

Two-sided assembly lines are widely applied to produce the large-sized high-volume products, such as buses and trucks. Balancing the lines is a vital design problem for the industries, and the problem is NP-hard. Besides the fundamental constraints of the conventional line balancing problem, some specific constraints may occur in the two-sided assembly line problem, including the zoning constraints, the positional constraints, and the synchronism constraints, which make the problem more complex. In this paper, an integer programming (IP) model is constructed and solved for the two-sided assembly line balancing problem which contains the above three constraints. A novel metaheuristic named late acceptance hill-climbing (LAHC) is also proposed to solve the problem effectively. The proposed algorithm is tested on several sets of instances. The computational results of the LAHC algorithm are compared with those of IP and the lower bounds of the instances. The experiment validates the effectiveness of the LAHC algorithm.