toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
Details
   print
  Records Links
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 (up) 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.  
  Address  
  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
 

 
Author Pereira, J. pdf  doi
openurl 
  Title Procedures for the bin packing problem with precedence constraints Type
  Year 2016 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.  
  Volume 250 Issue (up) 3 Pages 794-806  
  Keywords Bin packing; Precedence constraints; Lower bounds; Dynamic programming; Branch-and-bound  
  Abstract The bin packing problem with precedence constraints (BPP-P) is a recently proposed variation of the classical bin packing problem (BPP), which corresponds to a basic model featuring many underlying characteristics of several scheduling and assembly line balancing problems. The formulation builds upon the BPP by incorporating precedence constraints among items, which force successor items to be packed into later bins than their predecessors. In this paper we propose a dynamic programming based heuristic, and a modified exact enumeration procedure to solve the problem. These methods make use of several new lower bounds and dominance rules tailored for the problem in hand. The results of a computational experiment show the effectiveness of the proposed methods, which are able to close all of the previous open instances from the benchmark instance set within very reduced running times. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.  
  Address [Pereira, Jordi] Univ Adolfo Ibanez, Fac Sci & Engn, Ave Padre Hurtado 750,Off C216, Vina Del Mar, Chile, Email: jorge.pereira@uai.cl  
  Corporate Author Thesis  
  Publisher Elsevier Science Bv Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN 0377-2217 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000369192500011 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 581  
Permanent link to this record
Select All    Deselect All
 |   | 
Details
   print

Save Citations:
Export Records: