toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links (up)
Author Alvarez-Miranda, E.; Pereira, J.; Vila, M. doi  openurl
  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
Select All    Deselect All
 |   | 

Save Citations:
Export Records: