46- #1135 UN ALGORITMO HÍBRIDO GENÉTICO PARA LA SOLUCIÓN DEL JOB SHOP MINIMIZANDO EL MAKESPAN

Abstract

Actualmente las organizaciones necesitan ser
competitivas, por lo tanto, la optimización de sus
recursos es fundamental. En el área de gestión de
operaciones, en algunas actividades es necesario
secuenciar las operaciones de cada trabajo en las
máquinas de tal manera que el tiempo de finalización
de todas las operaciones, es decir, Makespan se
minimice. Esto es frecuente en sistemas tipo taller,
donde cada trabajo tiene su propio flujo y es común en
empresas manufactureras que manejan una gran
variedad de productos con bajos volúmenes de
producción y su característica principal es que cada
trabajo tiene su propio flujo. (Pezzella, Morganti, &
Ciaschetti, 2008). Para representar el anterior sistema,
se modela mediante el Job Shop donde dado un
conjunto de trabajos n y un conjunto de máquinas m;
cada trabajo consiste en un conjunto de operaciones
que tienen que ser procesadas en una específica
secuencia; cada operación tiene que ser procesada en
una máquina definida y tiene un tiempo de
procesamiento el cual es conocido sujeto a las
restricciones de que cada máquina puede procesar
como máximo una operación a la vez y que cada
operación necesita ser procesada durante un período
de tiempo sin interrumpir en una máquina determinada.

El Job shop está entre los problemas de optimización
combinatoria más difíciles de tipo Np-hard (van
Laarhoven, Aarts, & Lenstra, 2008). Por tal motivo, se
necesitan procedimientos eficientes para la búsqueda
de su solución. En este trabajo se propone un Algoritmo
Híbrido Genético (AHG) que utiliza el Algoritmo de
Recocido Simulado para generar parte de la población
inicial.

Luego se validó el AHG con instancias y se comparó
con diferentes enfoques propuestos en la literatura,
arrojando buenos resultados para todos los tamaños de
las instancias.