|   | 
Author Alvarez-Miranda, E.; Pereira, J.; Vila, M.
Title Analysis of the simple assembly line balancing problem complexity Type
Year 2023 Publication Computers & Operations Research Abbreviated Journal Comput. Oper. Res.
Volume 159 Issue Pages 106323
Keywords Manufacturing; Assembly line balancing; Packing; Precedence constraints; Instance sets
Abstract The simple assembly line balancing problem (SALBP) involves the determination of the assignment of elementary assembly operations to the workstations of the assembly line for the manufacture of a final product, with the objective of maximising assembly efficiency. In addition to its practicality, the SALBP can be considered as an extension of the bin packing problem (BPP) to account for the precedence relations between items. These constraints introduce an ordering component to the problem, which increases the complexity of SALBP resolution. However, previous studies indicated that precedence constraints do not play an important role in the capacity of state-of-the-art procedures to solve benchmark instances to optimality. In this study, we analysed the influences of different features of an SALBP instance on the performance of state-of-the-art solution methods for the abovementioned problem. First, we provide an alternative proof of complexity for the SALBP that uses precedence constraints to demonstrate its non-deterministic polynomial time (NP)-complete status, followed by a new set of benchmark instances directed towards an empirical analysis of the different features of SALBP instances. The experimental results revealed that the packing features of the SALBP are a major source of the perceived difficulty for any instance; however, precedence constraints play a role in the performance of these solution procedures. Specifically, the number of precedence constraints plays an important role in the results obtained from state-of-the-art methods. In addition to the analysis, certain issues that were identified in the publicly available implementations of the state-of-the-art method for resolving this problem were addressed in this study.
Corporate Author Thesis
Publisher Place of Publication Editor
Language Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0305-0548 ISBN Medium
Area Expedition Conference
Notes WOS:001033536100001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1849
Permanent link to this record