Ensayo IA

Un algoritmo genético para solucionar el problema de Job Shop Scheduling
Miguel Ángel Rosales Quiroga1, Alejandro Serrano Mancilla1, Marcela Rivera Martinez2, Luis René Marcial Castillo2, Lourdes Sandoval Solís2
1,2 Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla, Puebla, México
1{serrano_ayn, mike_quiroga41}@hotmail.com
2{cmr, lmc, sandoval}@cs.buap.mxResumen. Los problemas de planificación hoy en día son importantes en cualquier ámbito, y debido a esto tienen que ser óptimos, para poder ahorrar tiempo entre procesos. Se analiza el problema de Job Shop Scheduling, y se propone un algoritmo genético para la solución del problema, la población inicial se genera aleatoriamente, también se realizan los operadores: cruza y mutación específicos paraeste problema, se prueba con diferentes problemas para verificar que los resultados sean fiables.
Palabras clave: Job shop scheduling, algoritmos genéticos, makespan.
1 Introducción
Un problema computacional que se presenta al tratar de resolver problemas de optimización combinatoria, es la explosión combinatoria, la cual consiste en que existen un gran número de soluciones posibles para dichoproblema. Para examinar cada una de estas posibles soluciones la computadora demora bastante tiempo.
Para problemas pequeños, el uso de métodos exhaustivos es una opción aceptable, sin embargo, cuando el espacio de búsqueda crece dichos métodos se comportan de manera inadecuada, además el uso de memoria necesaria es proporcional al tamaño del problema, esto hace que el uso de estos métodosno sean aplicables a la mayor parte de los problemas [1]. En estos casos, la mejor opción es utilizar un algoritmo heurístico, que produzca de manera rápida buenas soluciones aunque estas no sean las óptimas.
La elaboración de un producto requiere de una serie de procesos, cada uno de éstos se efectúa en una máquina determinada. Esto origina diferentes problemas entre los que se encuentrasecuenciar n trabajos en m máquinas. La secuenciación tiene como objetivo encontrar el orden de ejecución de n trabajos, que requieren una serie de procesos en m máquinas, de manera que se optimice una medida de desempeño definida para tal fin [2].
El trabajo está dividido de la manera siguiente. En la sección 2 se presenta la definición del problema, en la sección 3 se describen las heurísticas,en la sección 4 se trata el tema de algoritmos genéticos describiendo su proceso, creación de población inicial, selección de parejas, cruza, mutación y evaluación de los resultados, en la sección 5 se explica un problema por medio de una corrida así como las pruebas realizadas, en la sección 6 se presentan las conclusiones del trabajo y finalmente se listan las referencias utilizadas.
2Definición del problema
En el esquema de Job Shop cada trabajo tiene su propia ruta predeterminada a seguir. Las prioridades dependen de cada trabajo debido a diferentes factores como: mínima manipulación del material, fácil transporte, no existe regreso, manufacturaciones modernas, etc. En el job shop las operaciones consecutivas de un trabajo nunca se llevan a cabo en la misma máquina, cuando estoocurre, las dos operaciones se consideran como una sola cuyo tiempo de procesamiento es la suma de los tiempos de procesamiento de las operaciones individuales. Cada trabajo consta de un conjunto de operaciones con una secuencia específica, las cuales requieren de una máquina para su procesamiento y cada máquina puede realizar sólo una tarea a la vez.
Los problemas Job Shop Scheduling (JSP)son problemas que buscan la optimización de los tiempos de trabajo, estos problemas están clasificados como NP-Completos [2], esto quiere decir que no existe un algoritmo cuyo tiempo de procesamiento sea menor al orden exponencial.
Un problema Job Shop Scheduling consta de un conjunto n de trabajos, donde cada uno de estos tiene un conjunto de operaciones que tienen que ser procesadas por...