Algoritmo Genetico

ALGORITMO GENÉTICO PARA EL PROBLEMA DE JOB SHOP FLEXIBLE
GENETIC ALGORITHM FOR THE FLEXIBLE JOB SHOP PROBLEM
Rosa Medina Durán1

Lorena Pradenas Rojas2

Víctor Parada Daza3

RESUMEN
El problema de Job Shop Flexible es parte de la familia de los problemas de scheduling. Nace como una
generalización del problema de Job Shop, para optimizar el uso de los recursos en sistemas de produccióncon una
mayor flexibilidad, por ejemplo la capacidad de una máquina de realizar más de un tipo de operación. Este problema ha
sido estudiado por numerosos autores, que han propuesto diversos modelos matemáticos y enfoques heurísticos. Debido
a la naturaleza combinatorial de este problema, los métodos exactos que resuelven los modelos matemáticos logran
resolver sólo instancias pequeñas. Entrelos métodos heurísticos propuestos, las metaheurísticas de búsqueda local han
presentado un mejor desempeño. En este estudio se presenta un algoritmo genético secuencial para resolver el problema
del Job Shop Flexible. El algoritmo propuesto se prueba utilizando las instancias de la literatura. Los resultados
muestran la efectividad del algoritmo para encontrar buenas soluciones al problema.Palabras clave: Job Shop Flexible, Algoritmos Genéticos, Scheduling.
ABSTRACT
The Flexible Job Shop Problem is part of the family of scheduling problems. It extends the job shop problem in order to
optimize the use of the resources in flexible production systems, for example those with machines that can process more
than one type of operations. This problem has been studied for many authors,proposing mathematical models and
heuristics approaches. Due to its combinatorial complexity, the exact methods that solve the mathematical models only
solve small instances. Among the heuristics approaches, the metaheuristics of local search have demonstrated a better
performance. The proposed algorithm is tested using literature instances. The results show that the algorithm is
effective forfinding good solutions for the problem.
Keywords: Flexible Job Shop Problem, Genetic Algorithms, Scheduling.
INTRODUCCIÓN
En las industrias de manufactura, la planeación de la
producción debe decidir la asignación de los recursos
a las tareas para optimizar uno o más objetivos. Para
apoyar estas decisiones, tradicionalmente, se utiliza el
modelo de Job Shop, el cual considera un conjunto demáquinas y un conjunto de trabajos compuestos por
una secuencia ordenada de operaciones, que se deben
procesar en las máquinas con el objetivo de minimizar,
por ejemplo, el tiempo de completación de la última
operación, makespan.

1

El problema de Job Shop Flexible es una
generalización del problema de Job Shop; considera
que las operaciones pueden ser procesadas por un
grupo demáquinas; por lo cual, también se requiere
decidir cual de las máquinas procesa cada operación.
Brandimarte [1], propone un enfoque jerárquico para
la resolución del problema, separandolo en el
subproblema de asignación y en el subproblema de
secuenciamiento. El primer suproblema lo resuelve
como un problema de ruteo, mientras que el segundo
corresponde al problema de Job Shop. Para probar elalgoritmo propone quince instancias del Job Shop
Flexible. Mesghouni [9] corresponde a la primera
publicación que resuelve el problema utilizando

Departamento de Ingeniería Industrial. Facultad de Ingeniería. Universidad de Concepción. Casilla 160-C. Correo 3. Concepción, Chile. E-mail: rosmedina@udec.cl
Departamento de Ingeniería Industrial. Facultad de Ingeniería. Universidad de Concepción.Casilla 160-C. Correo 3. Concepción, Chile. E-mail: lpradena@udec.cl
3
Departamento de Ingeniería Informática. Facultad de Ingeniería. Universidad de Santiago de Chile. Avda. Ecuador 3659. Santiago, Chile. E-mail: victor.parada@usach.cl
2

Medina, et al.:Algoritmo Genético para el Problema de Job Shop Flexible

algoritmos genéticos. Utilizan un enfoque integrado,
representando la...