×

A mathematical model and a genetic algorithm for two-sided assembly line balancing. (English) Zbl 1157.90390

Summary: A two-sided assembly line is a type of production line where tasks are performed in parallel at both sides of the line. The line is often found in producing large products such as trucks and buses. This paper presents a mathematical model and a genetic algorithm (GA) for two-sided assembly line balancing (two-ALB). The mathematical model can be used as a foundation for further practical development in the design of two-sided assembly lines. In the GA, we adopt the strategy of localized evolution and steady-state reproduction to promote population diversity and search efficiency. When designing the GA components, including encoding and decoding schemes, procedures of forming the initial population, and genetic operators, we take account of the features specific to two-ALB. Through computational experiments, the performance of the proposed GA is compared with that of a heuristic and an existing GA with various problem instances. The experimental results show that the proposed GA outperforms the heuristic and the compared GA.

MSC:

90B30 Production models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bartholdi, J. J., Balancing two-sided assembly lines: a case study, International Journal of Production Research, 31, 2447-2461 (1993)
[2] Kim, Y. K.; Kim, Y.; Kim, Y. J., Two-sided assembly line balancing: a genetic algorithm approach, Production Planning and Control, 11, 1, 44-53 (2000)
[3] Talbot, F. B.; Patterson, J. H.; Gehrlein, W. V., A comparative evaluation of heuristic line balancing techniques, Management Science, 32, 430-454 (1986)
[4] Ghosh, S.; Gagnon, R. J., A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems, International Journal of Production Research, 27, 637-670 (1989)
[5] Scholl, A.; Becker, C., State-of-the art exact and heuristic solution procedures for simple assembly line balancing, European Journal of Operational Research, 168, 3, 666-693 (2006) · Zbl 1083.90019
[6] Lapierre, S. D.; Ruiz, A.; Soriano, P., Balancing assembly lines with tabu search, European Journal of Operational Research, 168, 826-837 (2006) · Zbl 1083.90017
[7] Baybars, I., A survey of exact algorithms for the simple assembly line balancing problem, Management Science, 32, 909-932 (1986) · Zbl 0601.90081
[8] Johnson, R. V., Optimally balancing large assembly lines with FABLE, Management Science, 34, 240-253 (1988)
[9] Klein, R.; Scholl, A., Maximizing the production rate in simple assembly line balancing—a branch and bound procedure, European Journal of Operational Research, 91, 367-385 (1996) · Zbl 0924.90094
[10] Hu, X.; Wu, E.; Jin, Y., A station-oriented enumerative algorithm for two-sided assembly line balancing, European Journal of Operational Research, 186, 435-440 (2008) · Zbl 1146.90387
[11] Lee, T. O.; Kim, Y.; Kim, Y. K., Two-sided assembly line balancing to maximize work relatedness and slackness, Computers & Industrial Engineering, 40, 273-292 (2001)
[12] Lapierre, S. D.; Ruiz, A., Balancing assembly lines: an industrial case study, Journal of the Operational Research Society, 55, 589-597 (2004) · Zbl 1060.90686
[13] Baykasoglu A, Dereli T. Two-sided assembly line balancing using an ant-colony-based heuristic. International Journal of Advanced Manufacturing Technology; doi 10.1007/s00170-006-0861-3.; Baykasoglu A, Dereli T. Two-sided assembly line balancing using an ant-colony-based heuristic. International Journal of Advanced Manufacturing Technology; doi 10.1007/s00170-006-0861-3. · Zbl 1186.90126
[14] Fleszar, K.; Hindi, K. S., An enumerative heuristic and reduction methods for the assembly line balancing problem, European Journal of Operational Research, 145, 606-620 (2003) · Zbl 1011.90039
[15] Kim, Y. K.; Park, K.; Ko, J., A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling, Computers & Operations Research, 30, 1151-1171 (2003) · Zbl 1049.90026
[16] Kim, J. Y.; Kim, Y. K., Multileveled symbiotic evolutionary algorithm: application to FMS loading problems, Applied Intelligence, 22, 3, 233-249 (2005) · Zbl 1084.68100
[17] Syswerda, G., A study of reproduction in generational and steady-state genetic algorithms, (Gregory, J. E., Foundations of genetic algorithms (1991), Morgan Kauffmann: Morgan Kauffmann San Mateo), 94-101
[18] Jones, D. R.; Beltramo, M. A., Solving partitioning problems with genetic algorithms, (Belew, R.; Booker, L., Proceedings of the 4th international conference on genetic algorithms (1991), Morgan Kauffman: Morgan Kauffman San Diego, San Mateo), 442-449
[19] Helgeson, W. B.; Birnie, D. P., Assembly line balancing using the ranked positional weight technique, Journal of Industrial Engineering, 12, 394-398 (1961)
[20] von Laszewski, G., Intelligent structural operator for \(k\)-way group partitioning problem, (Belew, R.; Booker, L., Proceedings of the 4th international conference on genetic algorithms (1991), Morgan Kauffman: Morgan Kauffman San Diego, San Mateo), 45-52
[21] Khuri, S.; Schütz, M.; Heitkötter, J., Evolutionary heuristics for the bin packing problem, (Pearson, D. W.; Steele, N. C.; Albrecht, R. F., Artificial neural nets and genetic algorithms (1995), Springer: Springer Alès, New York), 285-288
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.