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...
| Main Authors: | , , , |
|---|---|
| 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 |
