46- #1135 UN ALGORITMO HÍBRIDO GENÉTICO PARA LA SOLUCIÓN DEL JOB SHOP MINIMIZANDO EL MAKESPAN
No Thumbnail Available
Date
Advisors
Evaluators
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad Industrial de Santander
Abstract
Description
Actualmente las organizaciones necesitan sercompetitivas, por lo tanto, la optimización de susrecursos es fundamental. En el área de gestión deoperaciones, en algunas actividades es necesariosecuenciar las operaciones de cada trabajo en lasmáquinas de tal manera que el tiempo de finalizaciónde todas las operaciones, es decir, Makespan seminimice. Esto es frecuente en sistemas tipo taller,donde cada trabajo tiene su propio flujo y es común enempresas manufactureras que manejan una granvariedad de productos con bajos volúmenes deproducción y su característica principal es que cadatrabajo 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 operacionesque tienen que ser procesadas en una específicasecuencia; cada operación tiene que ser procesada enuna máquina definida y tiene un tiempo deprocesamiento el cual es conocido sujeto a lasrestricciones de que cada máquina puede procesarcomo máximo una operación a la vez y que cadaoperación necesita ser procesada durante un períodode tiempo sin interrumpir en una máquina determinada.
El Job shop está entre los problemas de optimizacióncombinatoria más difíciles de tipo Np-hard (vanLaarhoven, Aarts, & Lenstra, 2008). Por tal motivo, senecesitan procedimientos eficientes para la búsqueda de su solución. En este trabajo se propone un AlgoritmoHíbrido Genético (AHG) que utiliza el Algoritmo deRecocido Simulado para generar parte de la poblacióninicial.
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 delas instancias.
Keywords
Job shop, Recocido Simulado, Algoritmo Híbrido Genético