|   | 
Details
   web
Records
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 (up) 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.; Vila, M.
Title A new model for supply chain network design with integrated assembly line balancing decisions Type
Year 2016 Publication International Journal Of Production Research Abbreviated Journal (up) Int. J. Prod. Res.
Volume 54 Issue 9 Pages 2653-2669
Keywords decomposition; mixed integer linear programming; supply chain design; line balancing; SALBP-1
Abstract Supply chain network design aims at the integration of the different actors of a supply chain within a single framework in order to optimise the total profit of the system. In this paper, we consider the integration of line balancing issues within the tactical decisions of the supply chain, and we offer a novel model and a solution approach for the problem. The new approach decomposes the problem into multiple line balancing problems and a mixed integer linear model, which is easier to solve than the previously available non-linear mixed integer formulation. The results show that the new method is able to solve previously studied models within a fraction of the reported running times, and also allows us to solve larger instances than those reported in earlier works. Finally, we also provide some analysis on the influence of the cost structure, the demand and the structure of the assembly process on the final configuration of the assemblies and the distribution network.
Address [Pereira, Jordi] Univ Adolfo Ibanez, Fac Sci & Engn, 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:000373632300009 Approved
Call Number UAI @ eduardo.moreno @ Serial 608
Permanent link to this record
 

 
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 (up) 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.; Torrez-Meruvia H.; Vila, M.
Title A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations Type
Year 2021 Publication Mathematics Abbreviated Journal (up) Mathematics
Volume 9 Issue 17 Pages 2157
Keywords assembly lines; manufacturing; line balancing; hybrid genetic algorithm
Abstract The assembly line balancing problem is a classical optimisation problem whose objective is to assign each production task to one of the stations on the assembly line so that the total efficiency of the line is maximized. This study proposes a novel hybrid method to solve the simple version of the problem in which the number of stations is fixed, a problem known as SALBP-2. The hybrid differs from previous approaches by encoding individuals of a genetic algorithm as instances of a modified problem that contains only a subset of the solutions to the original formulation. These individuals are decoded to feasible solutions of the original problem during fitness evaluation in which the resolution of the modified problem is conducted using a dynamic programming based approach that uses new bounds to reduce its state space. Computational experiments show the efficiency of the method as it is able to obtain several new best-known solutions for some of the benchmark instances used in the literature for comparison purposes.
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 2227-7390 ISBN Medium
Area Expedition Conference
Notes WOS:000694360700001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1466
Permanent link to this record
 

 
Author Yuraszeck, F.; Mejia, G.; Pereira, J.; Vila, M.
Title A Novel Constraint Programming Decomposition Approach for the Total Flow Time Fixed Group Shop Scheduling Problem Type
Year 2022 Publication Mathematics Abbreviated Journal (up) Mathematics
Volume 10 Issue 3 Pages 329
Keywords scheduling; fixed group shop; group shop; constraint programming
Abstract This work addresses a particular case of the group shop scheduling problem (GSSP) which will be denoted as the fixed group shop scheduling problem (FGSSP). In a FGSSP, job operations are divided into stages and each stage has a set of machines associated to it which are not shared with the other stages. All jobs go through all the stages in a specific order, where the operations of the job at each stage need to be finished before the job advances to the following stage, but operations within a stage can be performed in any order. This setting is common in companies such as leaf spring manufacturers and other automotive companies. To solve the problem, we propose a novel heuristic procedure that combines a decomposition approach with a constraint programming (CP) solver and a restart mechanism both to avoid local optima and to diversify the search. The performance of our approach was tested on instances derived from other scheduling problems that the FGSSP subsumes, considering both the cases with and without anticipatory sequence-dependent setup times. The results of the proposed algorithm are compared with off-the-shelf CP and mixed integer linear programming (MILP) methods as well as with the lower bounds derived from the study of the problem. The experiments show that the proposed heuristic algorithm outperforms the other methods, specially on large-size instances with improvements of over 10% on average.
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 2227-7390 ISBN Medium
Area Expedition Conference
Notes WOS:000756126100001 Approved
Call Number UAI @ alexi.delcanto @ Serial 1549
Permanent link to this record