Variable-depth local search heuristic for assembly line balancing problems

ABSTRACT

Assembly lines are production flow systems wherein activities are organised around a line consisting of various workstations through which the product flows. At each station, the product is assembled through a subset of operations. The assembly line balancing problem (ALBP) consists of allocating operations between stations to maximise the system efficiency. In this study, a variable-depth local search algorithm is proposed for solving simple assembly line balancing problems (SALBPs), which are the most widely studied versions of the ALBP. Although the state-of-the-art techniques for solving the SALBP consist of exact enumeration-based methods or heuristics, this paper proposes a local search-based heuristic using variable-length sequences that allow the solution space to be efficiently explored. The proposed algorithm improves the best solution known for multiple instances reported in the literature, indicating that its efficiency is comparable to those of the state-of-the-art method for solving the SALBP. Moreover, the characteristics of the instances for which the proposed procedure provides a better solution than previously reported construction procedures are investigated.

KEYWORDS:

• Assembly lines
• Manufacturing
• simple assembly line balancing
• local search
• variable-depth local search

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The instances used in this paper are available at https://assembly-line-balancing.de/salbp/. Detailed results for each specific instance are available upon request to the author through email.

Additional information

Funding

This research has been partially funded by the National Commission for Scientific and Technological Research CONICYT, Chile, through research grant N. 1191624 “Assembly Line Balancing for Industry 4.0”. E. Álvarez-Miranda also acknowledges the support of the National Commission for Scientific and Technological Research CONICYT, Chile, through funding from FONDECYT N. 1220830 and through the Complex Engineering Systems Institute PIA/BASAL AFB180003.

Notes on contributors

Eduardo Álvarez-Miranda

Eduardo Álvarez-Miranda is Associate Professor at the School of Economics and Business, Universidad de Talca in Chile. He is also a researcher of the Complex Systems Engineering Institute, Chile. He received his PhD in Operations Research in 2014 from the University of Bologna, Italy. His research interests are focussed on the development and application of mathematical optimisation techniques for problems from different application contexts.

Jordi Pereira

Jordi Pereira is Full Professor at the Faculty of Engineering and Science, Universidad Adolfo Ibáñez in Chile and Senior lecturer at UPF-Barcelona School of Manangement in Barcelona, Spain. He received his PhD in Engineering in 2004 from the Universitat Politécnica de Catalunya, Spain. His research considers the development of solution procedures for combinatorial optimisation problems in different application areas with special interest in assembly line balancing problems.

Camila Vargas

Camila Vargas is an Operations Research M.Sc. and Industrial Engineering B.Sc. at Universidad Adolfo Ibáñez in Chile. She currently works at Cotalker as Solutions Engineer.

Mariona Vilà

Mariona Vilà is an Associate Lecturer of the Production Management department at EAE Business School in Barcelona, Spain. She received her PhD in Business Management and Organisation in 2014 from the Universitat Politécnica de Catalunya, Spain. Her research interests are related to the study and resolution of combinatorial optimisation problems, with a special focus on applications on the design of production systems.