Open AccessA memetic algorithm for minimizing the makespan in the Job Shop Scheduling problem
Author(s) -
Henry Lamos-Díaz,
Karin Aguilar-Imitola,
Yuleiny Tatiana Pérez-Díaz,
Silvia Galván-Núñez
Publication year - 2017
Publication title -
revista facultad de ingeniería/revista facultad de ingeniería
Language(s) - English
Resource type - Journals
eISSN - 2357-5328
pISSN - 0121-1129
DOI - 10.19053/01211129.v26.n44.2017.5776
Subject(s) - job shop scheduling , memetic algorithm , mathematical optimization , heuristics , metaheuristic , computer science , local search (optimization) , job shop , scheduling (production processes) , flow shop scheduling , genetic algorithm , mathematics , schedule , operating system
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.