A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem

The Job Shop Scheduling Problem (JSP) is a combinatorial optimization problem cataloged as type NP-Hard. To solve this problem, several heuristics and metaheuristics have been used. In order to minimize the makespan, we propose a Memetic Algorithm (MA), which combines the exploration of the search s...

Full description

Bibliographic Details
Main Authors: Lamos-Díaz, Henry, Aguilar-Imitola, Karin, Pérez-Díaz, Yuleiny Tatiana, Galván-Núñez, Silvia
Format: Online
Language:eng
Published: Universidad Pedagógica y Tecnológica de Colombia 2017
Subjects:
Online Access:https://revistas.uptc.edu.co/index.php/ingenieria/article/view/5776
_version_ 1801706076813393920
author Lamos-Díaz, Henry
Aguilar-Imitola, Karin
Pérez-Díaz, Yuleiny Tatiana
Galván-Núñez, Silvia
author_facet Lamos-Díaz, Henry
Aguilar-Imitola, Karin
Pérez-Díaz, Yuleiny Tatiana
Galván-Núñez, Silvia
author_sort Lamos-Díaz, Henry
collection OJS
description The Job Shop Scheduling Problem (JSP) is a combinatorial optimization problem cataloged as type NP-Hard. To solve this problem, several heuristics and metaheuristics have been used. In order to minimize the makespan, we propose a Memetic Algorithm (MA), which combines the exploration of the search space by a Genetic Algorithm (GA), and the exploitation of the solutions using a local search based on the neighborhood structure of Nowicki and Smutnicki. The genetic strategy uses an operation-based representation that allows generating feasible schedules, and a selection probability of the best individuals that are crossed using the JOX operator. The results of the implementation show that the algorithm is competitive with other approaches proposed in the literature.
format Online
id oai:oai.revistas.uptc.edu.co:article-5776
institution Revista Facultad de Ingeniería
language eng
publishDate 2017
publisher Universidad Pedagógica y Tecnológica de Colombia
record_format ojs
spelling oai:oai.revistas.uptc.edu.co:article-57762022-06-15T16:19:46Z A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem Lamos-Díaz, Henry Aguilar-Imitola, Karin Pérez-Díaz, Yuleiny Tatiana Galván-Núñez, Silvia Job Shop Schedule local search memetic algorithm metaheuristics The Job Shop Scheduling Problem (JSP) is a combinatorial optimization problem cataloged as type NP-Hard. To solve this problem, several heuristics and metaheuristics have been used. In order to minimize the makespan, we propose a Memetic Algorithm (MA), which combines the exploration of the search space by a Genetic Algorithm (GA), and the exploitation of the solutions using a local search based on the neighborhood structure of Nowicki and Smutnicki. The genetic strategy uses an operation-based representation that allows generating feasible schedules, and a selection probability of the best individuals that are crossed using the JOX operator. The results of the implementation show that the algorithm is competitive with other approaches proposed in the literature. Universidad Pedagógica y Tecnológica de Colombia 2017-01-25 info:eu-repo/semantics/article info:eu-repo/semantics/publishedVersion investigation application/pdf application/xml https://revistas.uptc.edu.co/index.php/ingenieria/article/view/5776 10.19053/01211129.v26.n44.2017.5776 Revista Facultad de Ingeniería; Vol. 26 No. 44 (2017); 113-123 Revista Facultad de Ingeniería; Vol. 26 Núm. 44 (2017); 113-123 2357-5328 0121-1129 eng https://revistas.uptc.edu.co/index.php/ingenieria/article/view/5776/4719 https://revistas.uptc.edu.co/index.php/ingenieria/article/view/5776/6397
spellingShingle Job Shop Schedule
local search
memetic algorithm
metaheuristics
Lamos-Díaz, Henry
Aguilar-Imitola, Karin
Pérez-Díaz, Yuleiny Tatiana
Galván-Núñez, Silvia
A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem
title A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem
title_full A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem
title_fullStr A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem
title_full_unstemmed A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem
title_short A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem
title_sort memetic algorithm for minimizing the makespan in the job shop scheduling problem
topic Job Shop Schedule
local search
memetic algorithm
metaheuristics
topic_facet Job Shop Schedule
local search
memetic algorithm
metaheuristics
url https://revistas.uptc.edu.co/index.php/ingenieria/article/view/5776
work_keys_str_mv AT lamosdiazhenry amemeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem
AT aguilarimitolakarin amemeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem
AT perezdiazyuleinytatiana amemeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem
AT galvannunezsilvia amemeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem
AT lamosdiazhenry memeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem
AT aguilarimitolakarin memeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem
AT perezdiazyuleinytatiana memeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem
AT galvannunezsilvia memeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem