O uso da programação inteira 0-1 para o balanceamento de linhas de montagem: modelagem, estudos de caso e avaliação
Assembly line balancing by means of integer programming 0-1: modeling, case studies and evaluation
Fernandes, Flavio Cesar F.; Godinho Filho, Moacir; Cutigi, Ricardo Augusto; Guiguet, Aline Malerbo
http://dx.doi.org/10.1590/S0103-65132008000200002
Prod, vol.18, n2, p.210-221, 2008
Resumo
O presente trabalho trata do problema do balanceamento de linha de montagem. Dentro deste contexto o objetivo é mostrar que nos dias atuais, em muitos casos práticos, é possível, mesmo em problemas relativamente grandes, a aplicação de procedimentos de solução exatos (no caso, programação inteira). Isto é feito por meio de dois estudos de caso em grandes empresas do Estado de São Paulo, as quais apresentam problemas de balanceamento de linha relativamente grandes (linhas com 80 e 104 tarefas). Em um destes problemas foi incluída no modelo uma restrição, inédita na literatura, para melhor adequá-lo à situação real. Esta restrição se refere a situações nas quais a linha de montagem possui tanto operações manuais quanto automáticas. Os resultados conseguidos foram muito bons, conseguindo-se redução de mais de 10% no número de estações de trabalho necessárias em cada caso.
Palavras-chave
Problema do balanceamento de linha de montagem, procedimentos de solução exata, programação inteira, estudos de caso.
Abstract
This paper deals with the assembly line balancing problem. Within this context, the objective is to show that nowadays, in many practical cases, it is possible, even in large problems, the application of exact solution procedures (in this case, integer programming). This is accomplished by means of two case studies in big companies of São Paulo State, which presents large assembly line balancing problems (lines with 80 and 104 tasks). In one of these cases one constraint unpublished on literature was included in the model to adapt the model to the real situation. This constraint accounts to those cases in which the assembly line has both manual and automatic tasks. The results were very good, and a reduction of more than 10% was attained in the number of workstations required on the assembly line.
Keywords
Assembly line balancing problem, exact solution procedures, integer programming, case studies.
References
AMEN, M. Heuristic methods for cost-oriented assembly line balancing: A comparison on solution quality and computing time. International Journal Production Economics, v. 69, p. 255-264, 2001.
______________. Heuristic methods for cost-oriented assembly line balancing: A survey. International Journal Production Economics, v. 68, p. 1-14, 2000.
______________. Cost-oriented assembly line balancing - model formulations, solution difficulty, upper and lower bounds. European Journal of Operational Research, v. 168, p. 747-770, 2006.
BAYBARS, I. A survey of exact Algorithms for the Simple Assembly Line Balancing Problem; Management Science, v. 32, n. 8, 1986.
BECKER, C.; SCHOLL, A. A survey on problems and methods in generalized assembly line balancing. European Journal of Operational Research, v. 168, n. 3, p. 694-715, 2006.
BOWMAN, E. H. Assembly line balancing by linear programming, Operations Research, v. 8, p. 385-389, 1960.
DAR-El, E. M. MALB-A heuristic technique for balancing large single-model assembly lines, AIIE Transactions, v. 5, p. 343-356, 1973.
EREL, E.; SARIN, S. C. A survey of the Simple Assembly Line Procedures; Production Planning & Control, v. 9, n. 5, p. 414-434, 1998.
FERNANDES, F. C. F.; MORÁBITO, R. Linguagens de Modelagem GAMS e LINGO: Aplicação a um problema de Balanceamento de Linha de Montagem; Cadernos de Engenharia de Produção, Ano X, n. 20, p. 8-31, 1993.
GHOSH, S.; GAGNON, R. J. A comprehensive literature review and analyses of design, balancing and scheduling of assembly systems; International Journal of Production Research, v. 27, n. 4, p. 637-670, 1989.
HELGESON, W.B.; SALVESON, M.E.; SMITH, W.W. How to balance an assembly line. Management Report n. 7 (New Caraan, Conn.: Carr Press, Division for Advanced Management), 1954.
MASTOR, A. A. An experimental investigation and comparative evaluation of production line balancing techniques, Management Science, v. 16, p. 728-746, 1970.
PATTERSON, J. H.; ALBRACHT, J. J. Assembly line balancing: 0-1 programming with Fibonacci Search, Operations Research, v. 23, p. 166-174, 1975.
PLANS, J.; COROMINAS, A. Modelling and solving the SALB-E problem. Proceedings of the IEEE International Symposium on Assembly and Task Planning. Porto, Portugal, p. 356-360, 1999.
SALVESON, M. E. The assembly line balancing problem, Journal Industrial Engineering, v. 6, p. 18-25, 1955.
SCHOLL, A. Balancing and sequencing assembly lines, 2nd ed. Physica, Heidelberg, 1999.
SCHOLL, A.; BECKER, C. State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research, v. 168, n. 3, p. 666-693, 2006.
TALBOT, F. B.; PATTERSON, J. H.; GEHRLEIN, W.V. A comparative evaluation of heuristic line balancing techniques, Management Science, v. 32, n. 4, p. 430-454, 1986.
THANGAVELU, S. R.; SHETTY, C. M. Assembly Line Balancing by Zero-One Programming. AIIE Transactions, v. 3, n. 1, p. 61-68, 1971.
WHITE, W. W. Comments on a paper by Bowman, Operations Research, v. 9, p. 274-276, 1961.
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email