Cycle time enhancement by simulated annealing for a practical assembly line balancing problem

Authors

  • Huong Mai Dinh Hanoi University of Science and Technology; Hanoi University of Industry
  • Dung Viet Nguyen Hanoi University of Science and Technology
  • Long Van Truong Hanoi University of Science and Technology
  • Thuan Phan Do Hanoi University of Science and Technology
  • Thao Thanh Phan Hanoi University of Science and Technology
  • Nghia Duc Nguyen Hanoi University of Science and Technology

DOI:

https://doi.org/10.31449/inf.v44i2.3083

Abstract

In the garment industry, assembly line balancing is one of the most significant tasks. To make a product, a manufacturing technique called assembly line is utilized, where components are assembled and transferred from workstation to workstation until the final assembly is finished. Assembly line should always be as balanced as possible in order to maximize efficiency. Different types of assembly line balancing problems were introduced along with many proposed solutions. In this paper, we focus on an assembly line balancing problem where the upper bound of the number of workers is given, tasks and workers have to be grouped into workstations so that the cycle time is minimized, the total number of workers is minimized and balance efficiency is maximized. With unfixed number of workstations and other various constraints, our problem is claimed to be novel. We propose three different approaches: exhaustive search, simulated annealing and simulated annealing with greedy. Computational results affirmed that our SA algorithm performed extremely good in terms of both accuracy and running time. From these positive outcomes, our algorithms clearly show their applicability potential in practice.

References

Ilker Baybars. A survey of exact algorithms for the simple assembly line balancing problem. Management science, 32(8):909–932, 1986.

Nils Boysen, Malte Fliedner, and Armin Scholl. A classification of assembly line balancing problems. European journal of operational research, 183(2):674–693, 2007.

Benjamin Bryton. Balancing of a continuous production line. PhD thesis, Northwestern University, 1954.

GM Buxey. Assembly line balancing with multiple stations. Management science, 20(6):1010–1021, 1974.

Vladimır Cerny. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of optimization theory and applications, 45(1):41–51, 1985.

James C Chen, Chun-Chieh Chen, Yi-Jhen Lin, CJ Lin, and TY Chen. Assembly line balancing problem of sewing lines in garment industry. In Proceedings of the 2014 International Conference on Industrial Engineering and Operations Management Bali, Indonesia, pages 7–9, 2014.

Wen-Chyuan Chiang. The application of a tabu search metaheuristic to the assembly line balancing problem. Annals of Operations Research, 77:209–227, 1998.

Mai Huong Dinh, Viet Dung Nguyen, Van Long Truong, Phan Thuan Do, Thanh Thao Phan, and Duc Nghia Nguyen. Simulated annealing for the assembly line balancing problem in the garment industry. In Proceedings of the Tenth International Symposium on Information and Communication Technology, pages 36–42, 2019.

Selin Hanife ERYURUK. Clothing assembly line design using simulation and heuristic line balancing techniques. Journal of Textile & Apparel/Tekstil ve Konfeksiyon, 22(4), 2012.

SH Eryuruk, F Kalaoglu, and M Baskak. Assembly line balancing in a clothing company. Fibres & Textiles in Eastern Europe, 66(1):93–98, 2008.

Rasul Esmaeilbeigi, Bahman Naderi, and Parisa Charkhgard. The type e simple assembly line balancing problem: A mixed integer linear programming formulation. Computers & Operations Research, 64:168–177, 2015.

Waldemar Grzechca. Assembly line balancing problem with reduced number of workstations. IFAC Proceedings Volumes, 47(3):6180–6185, 2014.

Allan L Gutjahr and George L Nemhauser. An algorithm for the line balancing problem. Management science, 11(2):308–315, 1964.

WB Helgeson and Dunbar P Birnie. Assembly line balancing using the ranked positional weight technique. Journal of industrial engineering, 12(6):394–398, 1961.

Thomas R Hoffmann. Assembly line balancing with a precedence matrix. Management Science, 9(4):551–562, 1963.

Mahmut Kayar and ¨O C Akyalc¸in. Applying different heuristic assembly line balancing methods in the apparel industry and their comparison. Fibres & Textiles in Eastern Europe, 2014.

Maurice D Kilbridge and Leon Wester. A heuristic method of assembly line balancing. Journal of Industrial Engineering, 12(4):292–298, 1961.

Scott Kirkpatrick, C Daniel Gelatt, and Mario P Vecchi. Optimization by simulated annealing. science, 220(4598):671–680, 1983.

N Kriengkorakot and N Pianthong. The assembly line balancing problem: Review problem. J. Ind. Eng, 6(3):18–25, 1955.

Sophie D Lapierre, Angel Ruiz, and Patrick Soriano. Balancing assembly lines with tabu search. European journal of operational research, 168(3):826–837, 2006.

Yuchen Li, Honggang Wang, and Zaoli Yang. Type ii assembly line balancing problem with multi-operators. Neural Computing and Applications, 31(1):347–357, 2019.

Patrick R McMullen and GV Frazier. Using simulated annealing to solve a multiobjective assembly line balancing problem with parallel workstations. International Journal of Production Research, 36(10):2717–2741, 1998.

SG Ponnambalam, P Aravindan, and G Mogileeswar Naidu. A multi-objective genetic algorithm for solving assembly line balancing problem. The International Journal of Advanced Manufacturing Technology, 16(5):341–352, 2000.

M. E. Salveson. Induced matchings in intersection graphs. The Journal of Industrial Engineering, 6(3):18–25, 1955.

Bhaba R Sarker and JG Shanthikumari. A generalized approach for serial or parallel line balancing. THE INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 21(1):109–133, 1983.

Armin Scholl and Christian Becker. Stateof-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research, 168(3):666–693, 2006.

Yuri N Sotskov, Alexandre Dolgui, TsungChyan Lai, and Aksana Zatsiupa. Enumerations and stability analysis of feasible and optimal line balances for simple assembly lines. Computers & Industrial Engineering, 90:241–258, 2015.

El-Ghazali Talbi. Metaheuristics: from design to implementation, volume 74. John Wiley & Sons, 2009.

Pedro M Vilarinho and Ana Sofia Simaria. A two-stage heuristic method for balancing mixed-model assembly lines with parallel workstations. International Journal of Production Research, 40(6):1405–1420, 2002.

Downloads

Published

2020-06-15

How to Cite

Dinh, H. M., Nguyen, D. V., Truong, L. V., Do, T. P., Phan, T. T., & Nguyen, N. D. (2020). Cycle time enhancement by simulated annealing for a practical assembly line balancing problem. Informatica, 44(2). https://doi.org/10.31449/inf.v44i2.3083

Issue

Vol. 44 No. 2 (2020)

Section

SoICT 2019

License

I assign to Informatica, An International Journal of Computing and Informatics ("Journal") the copyright in the manuscript identified above and any additional material (figures, tables, illustrations, software or other information intended for publication) submitted as part of or as a supplement to the manuscript ("Paper") in all forms and media throughout the world, in all languages, for the full term of copyright, effective when and if the article is accepted for publication. This transfer includes the right to reproduce and/or to distribute the Paper to other journals or digital libraries in electronic and online forms and systems.

I understand that I retain the rights to use the pre-prints, off-prints, accepted manuscript and published journal Paper for personal use, scholarly purposes and internal institutional use.

In certain cases, I can ask for retaining the publishing rights of the Paper. The Journal can permit or deny the request for publishing rights, to which I fully agree.

I declare that the submitted Paper is original, has been written by the stated authors and has not been published elsewhere nor is currently being considered for publication by any other journal and will not be submitted for such review while under review by this Journal.  The Paper contains no material that violates proprietary rights of any other person or entity. I have obtained written permission from copyright owners for any excerpts from copyrighted works that are included and have credited the sources in my article. I have informed the co-author(s) of the terms of this publishing agreement.


Copyright ©  Slovenian Society Informatika