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

Huong Mai Dinh, Dung Viet Nguyen, Long Van Truong, Thuan Phan Do, Thao Thanh Phan, Nghia Duc Nguyen


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.

Full Text:



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.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.