Hybridizing ant colony optimization by beam search for the assembly line balancing problem

Jiage Huo, Felix T.S. Chan, Carman K.M. Lee, Jan Ola Strandhagen, Ben Niu

Research output: Journal article publicationConference articleAcademic researchpeer-review

1 Citation (Scopus)


The type-I Assembly Line Balancing Problem (ALBP) focuses on the task assignment process with the objective of minimizing the number of workstations for a given cycle time. With the development of complex products, the problem size and the complexity in the assembly process is increasing. In this study, we hybridize the ant colony optimization algorithm via beam search (ACO-BS) in order to solve the type-I ALBP, and we focus more on the large scale ALBP in order to suit to the industrial requirements. We test ACO-BS with benchmark instances with a time limit of 360 seconds for one run, and the results show that 95.54% of the problems can reach their optimal solutions. In addition, since we want to explore the large scale ALBP, we generate 27 instances with a total of 400 tasks (the largest number of tasks in the benchmark instances of type-I ALBP is 297) randomly basing on the complexity indicators of order strength and processing time variation. There are three levels of order strength, 0.2, 0.6 and 0.9, and the time variation is set to be at 5-15, 65-75 and 135-145 levels. Meanwhile, the processing times of the tasks usually follow a unimodal or bimodal distribution, and we generate task times to follow three kinds of distribution respectively, unimodal distribution peaking at the bottom, unimodal distribution peaking in the middle and bimodal distribution. The comparison results with solutions obtained by the priority rule demonstrate the superiority of ACO-BS in solving large scale ALBP.

Original languageEnglish
Article numberICMIE 102
Number of pages9
JournalProceedings of the World Congress on Mechanical, Chemical, and Material Engineering
Publication statusPublished - 2018
Event4th World Congress on Mechanical, Chemical, and Material Engineering, MCM 2018 - Madrid, Spain
Duration: 16 Aug 201818 Aug 2018


  • Ant colony algorithm
  • Assembly line balancing
  • Beam search
  • Benchmarking data set
  • Computational efficiency

ASJC Scopus subject areas

  • Mechanical Engineering
  • Mechanics of Materials
  • General Chemical Engineering


Dive into the research topics of 'Hybridizing ant colony optimization by beam search for the assembly line balancing problem'. Together they form a unique fingerprint.

Cite this