Metaheuristics based on Bin Packing for the line balancing problem

Michel Gourgand; Nathalie Grangeon; Sylvie Norre

RAIRO - Operations Research (2007)

  • Volume: 41, Issue: 2, page 193-211
  • ISSN: 0399-0559

Abstract

top
The line balancing problem consits in assigning tasks to stations in order to respect precedence constraints and cycle time constraints. In this paper, the cycle time is fixed and the objective is to minimize the number of stations. We propose to use metaheuristics based on simulated annealing by exploiting the link between the line balancing problem and the bin packing problem. The principle of the method lies in the combination between a metaheuristic and a bin packing heuristic. Two representations of a solution and two neighboring systems are proposed and the methods are compared with results from the literature. They are better or similar to tabu search based algorithm.


How to cite

top

Gourgand, Michel, Grangeon, Nathalie, and Norre, Sylvie. "Metaheuristics based on Bin Packing for the line balancing problem." RAIRO - Operations Research 41.2 (2007): 193-211. <http://eudml.org/doc/250089>.

@article{Gourgand2007,
abstract = { The line balancing problem consits in assigning tasks to stations in order to respect precedence constraints and cycle time constraints. In this paper, the cycle time is fixed and the objective is to minimize the number of stations. We propose to use metaheuristics based on simulated annealing by exploiting the link between the line balancing problem and the bin packing problem. The principle of the method lies in the combination between a metaheuristic and a bin packing heuristic. Two representations of a solution and two neighboring systems are proposed and the methods are compared with results from the literature. They are better or similar to tabu search based algorithm.
},
author = {Gourgand, Michel, Grangeon, Nathalie, Norre, Sylvie},
journal = {RAIRO - Operations Research},
keywords = {Flow-shop; stochastic; Markovian analysis; simulation; metaheuristic; flow-shop},
language = {eng},
month = {6},
number = {2},
pages = {193-211},
publisher = {EDP Sciences},
title = {Metaheuristics based on Bin Packing for the line balancing problem},
url = {http://eudml.org/doc/250089},
volume = {41},
year = {2007},
}

TY - JOUR
AU - Gourgand, Michel
AU - Grangeon, Nathalie
AU - Norre, Sylvie
TI - Metaheuristics based on Bin Packing for the line balancing problem
JO - RAIRO - Operations Research
DA - 2007/6//
PB - EDP Sciences
VL - 41
IS - 2
SP - 193
EP - 211
AB - The line balancing problem consits in assigning tasks to stations in order to respect precedence constraints and cycle time constraints. In this paper, the cycle time is fixed and the objective is to minimize the number of stations. We propose to use metaheuristics based on simulated annealing by exploiting the link between the line balancing problem and the bin packing problem. The principle of the method lies in the combination between a metaheuristic and a bin packing heuristic. Two representations of a solution and two neighboring systems are proposed and the methods are compared with results from the literature. They are better or similar to tabu search based algorithm.

LA - eng
KW - Flow-shop; stochastic; Markovian analysis; simulation; metaheuristic; flow-shop
UR - http://eudml.org/doc/250089
ER -

References

top
  1. E.J. Anderson and M.C. Ferris, Genetic algorithms for combinatorial optimization: The assembly line balancing problem. ORSA J. Comput.6 (1994) 161–174.  
  2. M. Amen, Heuristic method for cost-oriented assembly line balancing: A survey. Inter. J. Prod. Econ.68 (2000) 1–14.  
  3. A.L. Arcus, Comsoal a computer method of sequencing operations for assembly lines. Inter. J. Prod. Res.4 (1966) 259–277.  
  4. I. Baybars, A survey of exact algorithms for the simple assembly line balancing problem. Manage. Sci.32 (1986) 909–932.  
  5. C. Boutevin, L. Deroussi, M. Gourgand and S. Norre, Supply chain Optimisation, chapter Hybrid methods for line balancing problems, edited by A. Dolgui, J. Soldek, O. Zaikin, Kluwer Academic Publishers (2004).  
  6. C. Boutevin, Problème d'Ordonnancement et d'Affectation avec Contraintes de Ressources de type RCPSP et Line Balancing. Ph.D. thesis, Université Blaise Pascal, Clermont-Ferrand (2003).  
  7. J. Bautista and J. Pereira, Ant algorithms for assembly line balancing. In Berlin Springer, editor, Ant algorithms, Third International Workshop, ANTS 2002 Proceedings, Bruxelles (Belgique), edited by M. Dorigo, G. Di Caro, M. Sampels Lect. Notes Comput. Sci.2463 (2002) 65–75.  
  8. T.K. Bhattacharjee and S. Sahu, A critique of some current assembly line balancing techni. Technical report, Indian Institute of Technology, Kharagpur, India (1987).  
  9. W.C. Chiang, The application of a tabu search metaheuristic to the assembly line balancing problem. Ann. Oper. Res.77 (1998) 209–227.  
  10. E.G. Coffman Jr., M.R. Garey and D.S. Johnson, Approximation algorithms for bin packing: A survey, in Approximation Algorithms for NP-Hard Problems, edited by Dorit S. Hochbaum (1997) 46–93.  
  11. A.L. Corcoran and R.L. Wainwright, Using libga to develop genetic algorithms for solving combinatorial optimization problems. Appl. Handbook Genetic Algorithms1 (1995) 144–172.  
  12. L. Deroussi, Heuristiques, métaheuristiques et systèmes de voisinage. Ph.D. thesis, Université Blaise Pascal, Clermont-Ferrand II (2002).  
  13. E. Falkenauer and A. Delchambre, A genetic algorithm for bin packing and line balancing, in Proceedings of IEEE International Conference on Robotics and Automation (ICRA92), Los Alamitos, Californie (1992) 1186–1192.  
  14. G. Fleury, Méthodes stochastiques et déterministes pour les problèmes NP-difficiles. Ph.D. thesis, Université Blaise Pascal, Clermont-Ferrand II (1993).  
  15. W.B. Helgeson and D.P. Birnie, Assembly line balancing using the rank positional weight technique. J. Ind. Eng.12 (1961) 394–398.  
  16. A. Heinrici, A comparison between simulated annealing and tabu search with an example for the production planning, in Operations Research Proceedings, Amsterdam, 1993, edited by Dyckhoff et al. Springer, Berlin (1994) 498–503.  
  17. S.D. Lapierre, A. Ruiz and P. Soriano, Balancing assembly lines with tabu search. Eur. J. Oper. Res. (2004) in press.  
  18. P.R. McMullen and G.V. Frazier, Using simulated annealing to solve a multiobjective assembly line balancing problem with parallel workstations. Inter. J. Prod. Res.36 (1998) 2717–2741.  
  19. V. Minzu and J.M. Henrioud, Stochastic algorithm for task assignment in single or mixed-model assembly lines. APII-JESA32 (1998) 831–851.  
  20. P.R. McMullen and P. Tarasewich, Using ant techniques to solve the assembly line balancing problem. IEE Transactions35 (2003) 605–617.  
  21. B. Rekiek, Assembly Line Design: Multiple Objective Grouping Genetic Algorithm and the Balancing of Mixed-model Hybrid Assembly Line. Ph.D. thesis, Université Libre de Bruxelles (2000).  
  22. J. Rubinovitz and G. Levitin, Genetic algorithm for assembly line balancing. Inter. J. Prod. Econ.41 (1995) 444–454.  
  23. A. Scholl and C. Becker, State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research, special issue on Balancing of Automated Assembly and Transfer Lines, edited by A. Dolgui 168 (2006) 666–693.  
  24. A. Scholl, Balancing and Sequencing of Assembly Lines. Physica-Verlag Heidelberg, New-York (1999).  
  25. A. Scholl and R. Klein, Balancing assembly lines effectively – a computational comparison. Eur. J. Oper. Res.114 (1999) 50–58.  
  26. G. Suresh and S. Sahu, Stochastic assembly line balancing using simulated annealing. J. Production Res.32 (1994) 1801–1810.  
  27. A. Scholl and S. Voss, Simple assembly line balancing – heuristic approaches. J. Heuristics2 (1996) 217–244.  
  28. F.B. Talbot and J.H. Patterson, An integer programming algorithms with network cuts for solving the single model assembly line balancing problem. Manage. Sci.32 (1984) 85–99.  
  29. T.S. Wee and M.J. Magazine, Assembly line as generalized bin packing. Oper. Res. Lett.1 (1982) 56–58.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.