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: | Article |
| Language: | English |
| Published: |
Universidad Pedagógica y Tecnológica de Colombia
2017-01-01
|
| Series: | Revista Facultad de Ingeniería |
| Subjects: | |
| Online Access: | http://revistas.uptc.edu.co/index.php/ingenieria/article/view/5776 |
| _version_ | 1818067026670780416 |
|---|---|
| author | Henry Lamos-Díaz Karin Aguilar-Imitola Yuleiny Tatiana Pérez-Díaz Silvia Galván-Núñez |
| author_facet | Henry Lamos-Díaz Karin Aguilar-Imitola Yuleiny Tatiana Pérez-Díaz Silvia Galván-Núñez |
| author_sort | Henry Lamos-Díaz |
| collection | DOAJ |
| 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. |
| first_indexed | 2024-12-10T15:17:08Z |
| format | Article |
| id | doaj.art-d0ef7294c32340098df8d6d2eeb6781f |
| institution | Directory Open Access Journal |
| issn | 0121-1129 2357-5328 |
| language | English |
| last_indexed | 2024-12-10T15:17:08Z |
| publishDate | 2017-01-01 |
| publisher | Universidad Pedagógica y Tecnológica de Colombia |
| record_format | Article |
| series | Revista Facultad de Ingeniería |
| spelling | doaj.art-d0ef7294c32340098df8d6d2eeb6781f2022-12-22T01:43:47ZengUniversidad Pedagógica y Tecnológica de ColombiaRevista Facultad de Ingeniería0121-11292357-53282017-01-01264411312310.19053/01211129.v26.n44.2017.57765776A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problemHenry Lamos-Díaz0Karin Aguilar-Imitola1Yuleiny Tatiana Pérez-Díaz2Silvia Galván-Núñez3Ph. D. Universidad Industrial de Santander (Bucaramanga-Santander, Colombia).M. Sc. Universidad Industrial de Santander (Bucaramanga-Santander, Colombia).Esp. Universidad Industrial de Santander (Bucaramanga-Santander, Colombia).M. Sc. Universidad Industrial de Santander (Bucaramanga-Santander, Colombia).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.http://revistas.uptc.edu.co/index.php/ingenieria/article/view/5776Job Shop Schedulelocal searchmemetic algorithmmetaheuristics |
| spellingShingle | Henry Lamos-Díaz Karin Aguilar-Imitola Yuleiny Tatiana Pérez-Díaz Silvia Galván-Núñez A memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem Revista Facultad de Ingeniería Job Shop Schedule local search memetic algorithm metaheuristics |
| 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 |
| url | http://revistas.uptc.edu.co/index.php/ingenieria/article/view/5776 |
| work_keys_str_mv | AT henrylamosdiaz amemeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem AT karinaguilarimitola amemeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem AT yuleinytatianaperezdiaz amemeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem AT silviagalvannunez amemeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem AT henrylamosdiaz memeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem AT karinaguilarimitola memeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem AT yuleinytatianaperezdiaz memeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem AT silviagalvannunez memeticalgorithmforminimizingthemakespaninthejobshopschedulingproblem |