A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations
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 pr...
Main Authors: | , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
MDPI AG
2021-09-01
|
Series: | Mathematics |
Subjects: | |
Online Access: | https://www.mdpi.com/2227-7390/9/17/2157 |
_version_ | 1797521132880920576 |
---|---|
author | Eduardo Álvarez-Miranda Jordi Pereira Harold Torrez-Meruvia Mariona Vilà |
author_facet | Eduardo Álvarez-Miranda Jordi Pereira Harold Torrez-Meruvia Mariona Vilà |
author_sort | Eduardo Álvarez-Miranda |
collection | DOAJ |
description | 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. |
first_indexed | 2024-03-10T08:07:19Z |
format | Article |
id | doaj.art-d901322d171b46a6a7d73b0625ef52be |
institution | Directory Open Access Journal |
issn | 2227-7390 |
language | English |
last_indexed | 2024-03-10T08:07:19Z |
publishDate | 2021-09-01 |
publisher | MDPI AG |
record_format | Article |
series | Mathematics |
spelling | doaj.art-d901322d171b46a6a7d73b0625ef52be2023-11-22T10:58:46ZengMDPI AGMathematics2227-73902021-09-01917215710.3390/math9172157A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of WorkstationsEduardo Álvarez-Miranda0Jordi Pereira1Harold Torrez-Meruvia2Mariona Vilà3School of Economics and Business, Universidad de Talca, Talca 3460000, ChileFaculty of Engineering and Sciences, Universidad Adolfo Ibáñez, Av. Padre Hurtado 750, Viña del Mar 2520000, ChileEAE Business School, C. Aragó 55, 08015 Barcelona, SpainEAE Business School, C. Aragó 55, 08015 Barcelona, SpainThe 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.https://www.mdpi.com/2227-7390/9/17/2157assembly linesmanufacturingline balancinghybrid genetic algorithm |
spellingShingle | Eduardo Álvarez-Miranda Jordi Pereira Harold Torrez-Meruvia Mariona Vilà A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations Mathematics assembly lines manufacturing line balancing hybrid genetic algorithm |
title | A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations |
title_full | A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations |
title_fullStr | A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations |
title_full_unstemmed | A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations |
title_short | A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations |
title_sort | hybrid genetic algorithm for the simple assembly line balancing problem with a fixed number of workstations |
topic | assembly lines manufacturing line balancing hybrid genetic algorithm |
url | https://www.mdpi.com/2227-7390/9/17/2157 |
work_keys_str_mv | AT eduardoalvarezmiranda ahybridgeneticalgorithmforthesimpleassemblylinebalancingproblemwithafixednumberofworkstations AT jordipereira ahybridgeneticalgorithmforthesimpleassemblylinebalancingproblemwithafixednumberofworkstations AT haroldtorrezmeruvia ahybridgeneticalgorithmforthesimpleassemblylinebalancingproblemwithafixednumberofworkstations AT marionavila ahybridgeneticalgorithmforthesimpleassemblylinebalancingproblemwithafixednumberofworkstations AT eduardoalvarezmiranda hybridgeneticalgorithmforthesimpleassemblylinebalancingproblemwithafixednumberofworkstations AT jordipereira hybridgeneticalgorithmforthesimpleassemblylinebalancingproblemwithafixednumberofworkstations AT haroldtorrezmeruvia hybridgeneticalgorithmforthesimpleassemblylinebalancingproblemwithafixednumberofworkstations AT marionavila hybridgeneticalgorithmforthesimpleassemblylinebalancingproblemwithafixednumberofworkstations |