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.
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] and, Genetic algorithms for combinatorial optimization: The assembly line balancing problem. ORSA J. Comput. 6 (1994) 161-174. | Zbl
[2] , Heuristic method for cost-oriented assembly line balancing: A survey. Inter. J. Prod. Econ. 68 (2000) 1-14.
[3] , Comsoal a computer method of sequencing operations for assembly lines. Inter. J. Prod. Res. 4 (1966) 259-277.
[4] , A survey of exact algorithms for the simple assembly line balancing problem. Manage. Sci. 32 (1986) 909-932. | Zbl
[5] ,, and, Supply chain Optimisation, chapter Hybrid methods for line balancing problems, edited by A. Dolgui, J. Soldek, O. Zaikin, Kluwer Academic Publishers (2004).
[6] , 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] and, 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] and, A critique of some current assembly line balancing techni. Technical report, Indian Institute of Technology, Kharagpur, India (1987).
[9] , The application of a tabu search metaheuristic to the assembly line balancing problem. Ann. Oper. Res. 77 (1998) 209-227. | Zbl
[10] , and, Approximation algorithms for bin packing: A survey, in Approximation Algorithms for NP-Hard Problems, edited by Dorit S. Hochbaum (1997) 46-93.
[11] and, Using libga to develop genetic algorithms for solving combinatorial optimization problems. Appl. Handbook Genetic Algorithms 1 (1995) 144-172.
[12] , Heuristiques, métaheuristiques et systèmes de voisinage. Ph.D. thesis, Université Blaise Pascal, Clermont-Ferrand II (2002).
[13] and, 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] , Méthodes stochastiques et déterministes pour les problèmes NP-difficiles. Ph.D. thesis, Université Blaise Pascal, Clermont-Ferrand II (1993).
[15] and, Assembly line balancing using the rank positional weight technique. J. Ind. Eng. 12 (1961) 394-398.
[16] , 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] , and, Balancing assembly lines with tabu search. Eur. J. Oper. Res. (2004) in press. | Zbl
[18] and, Using simulated annealing to solve a multiobjective assembly line balancing problem with parallel workstations. Inter. J. Prod. Res. 36 (1998) 2717-2741. | Zbl
[19] and, Stochastic algorithm for task assignment in single or mixed-model assembly lines. APII-JESA 32 (1998) 831-851.
[20] and, Using ant techniques to solve the assembly line balancing problem. IEE Transactions 35 (2003) 605-617.
[21] , 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] and, Genetic algorithm for assembly line balancing. Inter. J. Prod. Econ. 41 (1995) 444-454.
[23] and, 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] , Balancing and Sequencing of Assembly Lines. Physica-Verlag Heidelberg, New-York (1999).
[25] and, Balancing assembly lines effectively - a computational comparison. Eur. J. Oper. Res. 114 (1999) 50-58. | Zbl
[26] and, Stochastic assembly line balancing using simulated annealing. J. Production Res. 32 (1994) 1801-1810. | Zbl
[27] and, Simple assembly line balancing - heuristic approaches. J. Heuristics 2 (1996) 217-244.
[28] and, An integer programming algorithms with network cuts for solving the single model assembly line balancing problem. Manage. Sci. 32 (1984) 85-99. | Zbl
[29] and, Assembly line as generalized bin packing. Oper. Res. Lett. 1 (1982) 56-58. | Zbl
Cité par Sources :
