Metaheuristics based on bin packing for the line balancing problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 2, pp. 193-211.

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.

DOI : 10.1051/ro:2007018
Classification : 90Bxx
Mots-clés : flow-shop, stochastic, markovian analysis, simulation, metaheuristic 
@article{RO_2007__41_2_193_0,
     author = {Gourgand, Michel and Grangeon, Nathalie and Norre, Sylvie},
     title = {Metaheuristics based on bin packing for the line balancing problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {193--211},
     publisher = {EDP-Sciences},
     volume = {41},
     number = {2},
     year = {2007},
     doi = {10.1051/ro:2007018},
     mrnumber = {2341440},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro:2007018/}
}
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 - Recherche Opérationnelle
PY  - 2007
SP  - 193
EP  - 211
VL  - 41
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro:2007018/
DO  - 10.1051/ro:2007018
LA  - en
ID  - RO_2007__41_2_193_0
ER  - 
%0 Journal Article
%A Gourgand, Michel
%A Grangeon, Nathalie
%A Norre, Sylvie
%T Metaheuristics based on bin packing for the line balancing problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2007
%P 193-211
%V 41
%N 2
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro:2007018/
%R 10.1051/ro:2007018
%G en
%F RO_2007__41_2_193_0
Gourgand, Michel; Grangeon, Nathalie; Norre, Sylvie. Metaheuristics based on bin packing for the line balancing problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 41 (2007) no. 2, pp. 193-211. doi : 10.1051/ro:2007018. http://www.numdam.org/articles/10.1051/ro:2007018/

[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. | Zbl

[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. | Zbl

[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. | Zbl

[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 Algorithms 1 (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. | Zbl

[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. | Zbl

[19] V. Minzu and J.M. Henrioud, Stochastic algorithm for task assignment in single or mixed-model assembly lines. APII-JESA 32 (1998) 831-851.

[20] P.R. Mcmullen and P. Tarasewich, Using ant techniques to solve the assembly line balancing problem. IEE Transactions 35 (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. | Zbl

[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. | Zbl

[26] G. Suresh and S. Sahu, Stochastic assembly line balancing using simulated annealing. J. Production Res. 32 (1994) 1801-1810. | Zbl

[27] A. Scholl and S. Voss, Simple assembly line balancing - heuristic approaches. J. Heuristics 2 (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. | Zbl

[29] T.S. Wee and M.J. Magazine, Assembly line as generalized bin packing. Oper. Res. Lett. 1 (1982) 56-58. | Zbl

Cité par Sources :