|   | 
Details
   web
Records
Author Alvarez-Miranda, E.; Pereira, J.; Vargas, C.; Vila, M.
Title Variable-depth local search heuristic for assembly line balancing problems Type
Year 2022 Publication International Journal Of Production Research Abbreviated Journal Int. J. Prod. Res.
Volume 61 Issue 9 Pages 3103-3121
Keywords Assembly lines; Manufacturing; simple assembly line balancing; local search; variable-depth local search
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.
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 0020-7543 ISBN Medium
Area Expedition Conference
Notes WOS:000800928700001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1578
Permanent link to this record
 

 
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.
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.
Title Modelling and solving a cost-oriented resource-constrained multi-model assembly line balancing problem Type
Year 2018 Publication International Journal Of Production Research Abbreviated Journal Int. J. Prod. Res.
Volume 56 Issue 11 Pages 3994-4016
Keywords assembly line balancing; combinatorial optimisation; lower bound; heuristics; estimation of distribution algorithm
Abstract A line balancing problem considers the assignment of operations to workstations in an assembly line. While assembly lines are usually associated to mass production of standardised goods, their advantages have led to their widespread use whenever a product-oriented production system is applicable and the benefits of the labour division and specialisation are significant, even when some of its characteristics may deviate from classical assembly lines. In this work, we study a line balancing problem found in the textile industry in which the line must be balanced for multiple types of goods taking into account resource requirements. In order to solve the problem, a hybrid method that combines classical methods for line balancing with an Estimation of Distribution Algorithm is proposed. Computational experiments show that the new procedure improves upon the state of the art when compared using a benchmark set derived from the literature, as well as when compared using data from the manufacturer that originated this research work.
Address [Pereira, Jordi] Univ Adolfo Ibanez, Fac Engn & Sci, Vina Del Mar, Chile, Email: jorge.pereira@uai.cl
Corporate Author Thesis
Publisher Taylor & Francis Ltd Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition
ISSN 0020-7543 ISBN Medium
Area Expedition Conference
Notes WOS:000438403800013 Approved
Call Number UAI @ eduardo.moreno @ Serial 889
Permanent link to this record
 

 
Author Pereira, J.; Ritt, M.
Title Exact and heuristic methods for a workload allocation problem with chain precedence constraints Type
Year 2023 Publication European Journal Of Operational Research Abbreviated Journal Eur. J. Oper. Res.
Volume 309 Issue 1 Pages 387-398
Keywords Manufacturing; Assembly line balancing; Worker allocation; Dynamic programming; Branch and bound
Abstract Industrial manufacturing is often organized in assembly lines where a product is assembled on a se-quence of stations, each of which executes some of the assembly tasks. A line is balanced if the maximum total execution time of any station is minimal. Commonly, the task execution order is constrained by precedences, and task execution times are independent of the station performing the task. Here, we con -sider a recent variation, called the “(Calzedonia) Workload Allocation Problem” (WAP), where the prece-dences form a chain, and the execution time of a task depends on the worker executing it. This problem was recently proposed by Battarra et al. (2020) and it is a special case of the Assembly Line Worker As-signment and Balancing Problem Miralles et al. (2007) where precedence relations are arbitrary. In this paper we consider the computational complexity of the problem and prove its NP-hardness. To solve the problem, we provide different lower bounds and exact and heuristic procedures. The performance of the proposed methods is tested on previously proposed instances and on new, larger instances with the same characteristics. The results show that the proposed methods can solve instances with up to about 40 0 0 tasks and 29 workers, doubling the size of the instances that previously could be solved to optimality.
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 0377-2217 ISBN Medium
Area Expedition Conference
Notes WOS:000970067900001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1794
Permanent link to this record
 

 
Author Pereira, J.; Ritt, M
Title A note on “Algorithms for the Calzedonia workload allocation problem” Type
Year 2022 Publication Journal of the Operational Research Society Abbreviated Journal J. Oper. Res. Soc.
Volume 73 Issue 6 Pages 1420-1422
Keywords Assembly line balancing; worker allocation; dynamic programming
Abstract Battarra et al. recently proposed a novel assembly line balancing problem with applications to the apparel industry, where the tasks are performed in a fixed order. To solve the problem, one has to assign workers and tasks to the workstations with the objective of maximising the throughput of the assembly line. In this paper, we provide dynamic programming formulations for the general problem and some special cases. We then use these formulations to develop an exact solution approach that optimally solves the instances in Battarra et al. within seconds.
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 0160-5682 ISBN Medium
Area Expedition Conference
Notes WOS:000627308200001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1351
Permanent link to this record