Iterative beam search for car sequencing

详细信息    查看全文

• 作者：Uli Golle (1)
  Franz Rothlauf (1)
  Nils Boysen (2)
  
• 关键词：Car sequencing ; Iterative beam search ; Mixed ; model assembly lines
• 刊名：Annals of Operations Research
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：226
• 期：1
• 页码：239-254
• 全文大小：297 KB
• 参考文献：1. Bautista, J., Pereira, J., & Adenso-Diaz, B. (2008). A beam search approach for the optimization version of the car sequencing problem. / Annals of Operations Research, / 159, 233鈥?44. CrossRef
  2. Benoist, T. (2008). Soft car sequencing with colors: Lower bounds and optimality proofs. / European Journal of Operational Research, / 191(3), 957鈥?71. CrossRef
  3. Boysen, N., Fliedner, M., & Scholl, A. (2009). Sequencing mixed-model assembly lines: Survey, classification and model critique. / European Journal of Operational Research, / 192(2), 349鈥?73. CrossRef
  4. Boysen, N., Golle, U., & Rothlauf, F. (2011). The car resequencing problem with pull-off tables. / BuR - Business Research, / 4(2), 1鈥?7. CrossRef
  5. Estellon, B., Gardi, F., & Nouioua, K. (2008). Two local search approaches for solving real-life car sequencing problems. / European Journal of Operational Research, / 191(3), 928鈥?44. CrossRef
  6. Fliedner, M., & Boysen, N. (2008). Solving the car sequencing problem via branch & bound. / European Journal of Operational Research, / 191(3), 1023鈥?042. CrossRef
  7. Gagne, C., Gravel, M., & Price, W. (2006). Solving real car sequencing problems with ant colony optimization. / European Journal of Operational Research, / 174(3), 1427鈥?448. CrossRef
  8. Gent, I. P. (1998). / Two results on car-sequencing problems. APES research report 02鈥?998. Glasgow: Department of Computer Science, University of Strathclyde.
  9. Gottlieb, J., Puchta, M., & Solnon, C. (2003). A study of greedy, local search, and ant colony optimization approaches for car sequencing problems. In S. Cagnoni, C. Johnson, J. Cardalda, E. Marchiori, D. Corne, J. A. Meyer, J. Gottlieb, M. Middendorf, A. Guillot, G. Raidl, & E. Hart (Eds.), / EvoWorkshops 2003, LNCS 2611 (pp. 246鈥?57). Berlin Heidelberg: Springer.
  10. Gravel, M., Gagne, C., & Price, W. L. (2005). Review and comparison of three methods for the solution of the car sequencing problem. / Journal of the Operational Research Society, / 56(11), 1287鈥?295. CrossRef
  11. Jaszkiewicz, A., Kominek, P., & Kubiak, M. (2004). Adaptation of the genetic local search algorithm to a car sequencing problem. In / 7th National conference on evolutionary algorithms and global optimization. Kazimierz Dolny, Poland, pp. 67鈥?4.
  12. Kis, T. (2004). On the complexity of the car sequencing problem. / Operations Research Letters, / 32(4), 331鈥?35. CrossRef
  13. Klein, R., & Scholl, A. (1999). Scattered branch and bound: An adaptive search strategy applied to resource-constrained project scheduling. / Central European Journal of Operations Research, / 7, 177鈥?01.
  14. Lowerre, B. (1976). / The harpy speech recognition system. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, USA.
  15. Parrello, B. D., Kabat, W. C., & Wos, L. (1986). Job-shop scheduling using automated reasoning: A case study of the car-sequencing problem. / Journal of Automated Reasoning, / 2(1), 1鈥?2. CrossRef
  16. Perron, L., & Shaw, P. (2004). Combining forces to solve the car sequencing problem. In J. C. Regin & M. Rueher (Eds.), / Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, LNCS 3011 (pp. 225鈥?39). Berlin Heidelberg: Springer. CrossRef
  17. Prandtstetter, M., & Raidl, G. (2008). An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem. / European Journal of Operational Research, / 191(3), 1004鈥?022. CrossRef
  18. Puchta, M. & Gottlieb, J. (2002). Solving car sequencing problems by local optimization. In / Proceedings of the applications of evolutionary computing on evoworkshops 2002, LNCS, Vol. 2279 (pp. 132鈥?42). Berlin, Heidelberg: Springer.
  19. Solnon, C., Cung, V., Nguyen, A., & Artigues, C. (2008). The car sequencing problem: Overview of state-of-the-art methods and industrial case-study of the ROADEF鈥?005 challenge problem. / European Journal of Operational Research, / 191(3), 912鈥?27. CrossRef
  20. Warwick, T., & Tsang, E. (1995). Tackling car sequencing problems using a generic genetic algorithm. / Evolutionary Computation, / 3(3), 267鈥?98. CrossRef
  21. Wester, L. & Kilbridge, M. D. (1964). The assembly line model-mix sequencing problem. In / Proceedings of the Third International Conference on Operations Research.
  22. Zinflou, A., Gagne, C., & Gravel, M. (2007). Crossover operators for the car sequencing problem. In C. Cotta & J. van Hemert (Eds.), / Proceedings of the 7th European conference on evolutionary computation in combinatorial optimization, EvoCOP 2007, LNCS (Vol. 4446, pp. 229鈥?39). Valencia, Spain.
  
• 作者单位：Uli Golle (1)
  Franz Rothlauf (1)
  Nils Boysen (2)
  
  1. Lehrstuhl f眉r Wirtschaftsinformatik und BWL, Johannes Gutenberg-Universit盲t Mainz, Jakob-Welder-Weg 9, 55128, Mainz, Germany
  2. Lehrstuhl f眉r Operations Management, Friedrich-Schiller-Universit盲t Jena, Carl-Zei脽-Stra脽e 3, 07743, Jena, Germany
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Operation Research and Decision Theory
  Combinatorics
  Theory of Computation
  
• 出版者：Springer Netherlands
• ISSN：1572-9338

文摘

The car sequencing (CS) problem seeks a production sequence of different car models launched down a mixed-model assembly line. The models can be distinguished by selected options, e.g., sun roof yes/no. For every option, CS applies a so-called sequencing rule to avoid that consecutive models requiring this option lead to a work overload of the respective assembly operators. The aim is to find a sequence with minimum number of sequencing rule violations. This paper presents a graph representation of the problem and develops an exact solution approach based on iterative beam search. Furthermore, existing lower bounds are improved and applied. The experimental results reveal, that our solution approach is superior compared to the currently best known exact solution procedure. Our algorithm can even be applied as an efficient heuristic on problems of real-world size with up to 400 cars, where it shows competitive results compared to the current best known solutions.