Rosa Medina Durán¹ Lorena Pradenas Rojas¹ Víctor Parada Daza²

¹ 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; lpradena@udec.cl
² 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

RESUMEN

En este estudio se propone e implementa computacionalmente un algoritmo genético secuencial para resolver el problema del Job Shop Flexible (existente en la Gestión de Operaciones), el cual es parte de la familia de los problemas de programación de tareas o trabajos (Scheduling) en un taller que funciona a pedido. Surge como una generalización del problema del Job Shop y permite optimizar el uso de los recursos (máquinas) con mayor flexibilidad, ya que cada máquina puede realizar más de una operación. Este problema ha sido estudiado por numerosos autores, los que han propuesto diversos modelos matemáticos y enfoques heurísticos. Debido a la naturaleza combinatoria, los métodos exactos que resuelven modelos matemáticos encuentran soluciones sólo para instancias pequeñas o simples del problema mencionado. Los resultados muestran la efectividad del algoritmo propuesto para entregar buenas soluciones en tiempos computacionales razonables en más de 130 instancias encontradas en la literatura.

Palabras clave: Problema Job Shop Flexible, algoritmos genéticos, programación de trabajos, optimización combinatoria, gestión de operaciones.

ABSTRACT

This study proposes and computationally implements a sequential genetic algorithm to solve the Flexible Job Shop problem (found in Operations Management), which is part of the family of job or task scheduling problems in a shop that works on demand. It is a generalization of the Job Shop problem, and allows optimizing the use of resources (machines) in the shop, with greater flexibility, since each machine can perform more than one operation. This problem has been studied by many authors, who have proposed various mathematical models and heuristic approaches. Due to the combinatorial nature of the problem, the exact methods that solve the mathematical models are often solutions for small and simple instances of the problem. The results show the effectiveness of the proposed algorithm to provide good solutions in reasonable computational times in over 130 instances found in the literatura.

Keywords: Flexible Job Shop problem, genetic algorithms, scheduling, combinatorial optimization, operations management.

INTRODUCCIÓN

En la programación de la producción de las industrias manufactureras se debe decidir sobre la asignación de los recursos a las tareas o trabajos para optimizar, uno o más objetivos en el corto plazo. Para apoyar estas decisiones tradicionalmente se utiliza el modelo de Job Shop, el cual considera un conjunto de má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, entre otros, el tiempo de completación de la última operación, makespan.

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 de máquinas, razón por la cual también se requiere decidir sobre cuáles de las máquinas procesan cada operación.

Por ejemplo, consideremos un taller metal-mecánico, en el que se reciben dos trabajos compuestos por una secuencia fija de tres operaciones a realizar en tres máquinas. El primero requiere las operaciones de perforar, ranurar y pulir, mientras el segundo trabajo requiere cortar, limar y perforar. El taller dispone de un torno, que puede realizar las operaciones de perforar, pulir y cortar; una fresadora que puede perforar, ranurar, pulir y limar; y un taladro que puede perforar, ranurar y cortar. Los tiempos de las operaciones varían en las distintas máquinas, entonces, es necesario decidir cuál máquina realiza cada operación y en qué orden, con el objetivo de minimizar el tiempo total de completación de todos
los trabajos.

Este problema pertenece a la clase de problemas denominados de NP-Difíciles, para los cuales aún no se disponen de algoritmos de resolución eficientes que los ejecuten en tiempos computacionales razonables, sobre todo para instancias grandes y/o complejas.

Haciendo un breve recuento de los enfoques que intentan resolver el problema, tenemos que Brandimarte [1] propone un enfoque jerárquico para la resolución del problema, considerando un subproblema de asignación y un subproblema de secuenciamiento. El primero lo resuelve como un problema de ruteo, mientras que el segundo corresponde al problema de Job Shop. Para probar el algoritmo, este investigador usa quince instancias del Job Shop Flexible. Mesghouni, Hammadi y Borne [11] en cambio, resuelven el problema utilizando algoritmos genéticos, consideran un enfoque integrado, representando la solución mediante matrices. Por su parte, Kacem, Hammadi y Borne [10] proponen un enfoque por localización, que permite encontrar buenas soluciones, minimizando el makespan y la carga de las máquinas. Este último enfoque controla la evolución de un algoritmo genético.

Ho y Tay [6] y en sus distintas publicaciones estudian el problema del Job Shop Flexible, proponiendo reglas de despacho que utilizan como solución inicial para una nueva metodología denominada GENACE [8], en la cual las poblaciones son influenciadas por reglas heurísticas y en cada generación se guía el espacio de búsqueda mediante esquemas. Otros autores también estudian las representaciones de las soluciones [13], para encontrar la más eficaz en términos de tiempo de cómputo y de alcanzar el mejor makespan. Este enfoque es generalizado en una publicación posterior en Ho, Tay y Lai [7], donde se propone una arquitectura basada en algoritmos evolutivos, un aprendizaje con teoría de esquemas y un generador de poblaciones mediante reglas de despacho compuestas.

Fattahi, Meharab y Jolai [5] proponen un modelo matemático para el Job Shop Flexible y para probarlo generan diez instancias pequeñas y diez instancias medianas/grandes, aunque sólo logran resolver las instancias pequeñas. Utilizando también el enfoque jerárquico, combinan las metaheurísticas de Tabu Search y Simulated Annealing, con las que concluyen que el algoritmo que resuelve el subproblema de asignación con Tabu Search y el subproblema de secuenciamiento con Simulated Annealing presenta el mejor desempeño.

Zhang y Gen [15] proponen un algoritmo genético basado en escenarios múltiples, donde cada escenario corresponde a una operación y cada máquina factible a un estado. Pezzella, Morganti y Ciaschetti [12] también proponen un algoritmo genético, pero utilizan el enfoque de localización propuesto por Kacem, Hammadi y Borne [10].

Con ello establecen una mutación inteligente, que consiste en seleccionar una operación entre aquellas máquinas con más carga de trabajo y reasignar dicha carga a la máquina que tenga menos. Por último, la publicación más reciente corresponde a Yazdani, Zandieh y Amiri [14], quienes proponen un enfoque en paralelo de vecindario variable (VNS), con seis vecindarios, minimizando también el makespan.

Todo lo anterior nos lleva a plantear que el objetivo del presente estudio es proponer e implementar computacionalmente un nuevo algoritmo genético para resolver el problema de Job Shop Flexible, y luego comparar los resultados con otros obtenidos de la literatura en términos de desempeño computacional y calidad de solución.

DEFINICIÓN DEL PROBLEMA

El problema de Job Shop Flexible se define como:

"Dado un sistema con un conjunto de m máquinas, M={M₁,...,M_m}, y un conjunto de n trabajos independientes, J = {J₁,...,J_n}. Considerando que cada trabajo está compuesto por una secuencia de operaciones O_{j,1},O_{j,2},...,O_{j,h},...,O_{j,hj}, cada una de las cuales debe ser procesada en una máquina. Se dispone de los tiempos de proceso p_{i,j,h} de cada operación O_{j,h} en cada máquina factible , el problema de Job Shop Flexible requiere minimizar el tiempo de completación de la última operación: el makespan".

En la definición, O_{j,h} corresponde a la h-ésima operación del trabajo J_j y h_j indica el número de operaciones que requiere el trabajo J_j. Además, es el conjunto de todas las máquinas en el problema que pueden procesar la operación O_{j,h}. Cuando todas las operaciones pueden ser procesadas por todas las máquinas, M_{j,h} = M, la flexibilidad del problema es total (T-FJSP). Por el contrario, cuando al menos una operación O_{j,h} no puede ser procesada en todas las máquinas, es decir , la flexibilidad del problema es parcial (P-FJSP).

Se conoce el tiempo de proceso de cada operación en cada una de las máquinas donde puede ser procesada. Se denota como p_{i,j,h} el tiempo de proceso de la operación O_{j,h} en la máquina . No se permite interrumpir las operaciones cuando han iniciado su proceso, como tampoco se permite que las máquinas ejecuten más de una operación simultáneamente. Además, se asume que todos los trabajos y máquinas están disponibles en el instante (tiempo) cero.

Para encontrar el tiempo de completación de la última operación (makespan) es necesario asignar las operaciones a las máquinas y secuenciar dichas operaciones, por lo cual la función objetivo del problema se puede expresar como:

(1)

ALGORITMO PROPUESTO

Los Algoritmos Genéticos son métodos metaheurísticos de optimización estocástica inspirados en la evolución natural de las especies y propuestos por Holland [9]. Establecen una analogía entre el conjunto de soluciones del problema y el conjunto de individuos de una población natural. Así como las poblaciones de individuos evolucionan en cada generación, el conjunto de soluciones mejora en cada iteración.

Para explicar con mayor detalle el algoritmo genético propuesto en este estudio se utiliza un ejemplo que corresponde a una instancia de P-FJSP [3], que contiene dos trabajos y tres máquinas (2×3), como el presentado en la Introducción. Para ejecutar cada trabajo se requiere realizar tres operaciones, por lo que el problema total consta de seis operaciones cuyos tiempos de proceso se muestran en la Tabla 1, donde las "X" indican que la máquina no puede procesar esa operación.

Tabla 1. Ejemplo Job Shop Flexible parcial.

Es fundamental utilizar una codificación de las soluciones que represente las características del problema y respete las restricciones. Para la representación de la solución y para una mejor comprensión y tratamiento de la solución, en este estudio se propone que cada solución del problema utilice tres vectores. El primero de ellos representa una solución para el subproblema de secuenciamiento; el segundo indica la operación a la cual corresponde cada celda y el tercero determina una solución para el subproblema de asignación.

El cromosoma de secuenciamiento es un vector de tamaño igual al número de operaciones en el problema, similar a la representación propuesta en [8]. En cada celda aparece el número de un trabajo; el orden en que se encuentran define cuál es la prioridad de proceso de los trabajos. Cada trabajo j aparece h_j veces en el vector, una vez por cada operación. Se requiere, además, una función que no permita que la repetición de los trabajos exceda el número de sus operaciones. De este modo se indica la precedencia de las operaciones entre distintos trabajos y esta se respeta cuando pertenecen al mismo trabajo. En el ejemplo, una solución para el problema de secuenciamiento se muestra en la Figura 1, los números de cada celda corresponden a un determinado trabajo, los cuales aparecen repetidos tres veces, ya que cada trabajo tiene tres operaciones señaladas bajo cada celda.

Figura 1. Ejemplo de cromosoma de secuenciamiento.

Por su parte el cromosoma de operaciones es un vector similar al anterior, pero en cada celda se indica el número de la operación para hacer la correspondencia entre los trabajos del cromosoma de secuenciamiento y sus operaciones. Para el ejemplo, los números de las operaciones se muestran a la izquierda en la Figura 2 y, a la derecha, se muestra el cromosoma de operaciones que se obtiene para el cromosoma de secuenciamiento de la Figura 1.

Figura 2. Número de las operaciones y ejemplo de cromosoma de operaciones.

Por otro lado, el cromosoma de asignación también es un vector de las mismas dimensiones que los anteriores, pero cada celda contiene el índice de la máquina en la cual se procesa la operación que corresponde según los cromosomas anteriores. Esta representación es parecida a la propuesta en [3], aunque difiere en que la secuencia de las operaciones a las cuales es asignado depende del cromosoma del subproblema de operaciones. En el ejemplo (Figura 3) cada celda está asociada con la operación indicada en la parte superior, de acuerdo al cromosoma de operaciones. Estas máquinas corresponden sólo a aquellas que pueden procesar la operación, es decir, en nuestro ejemplo no puede ir un número diferente de dos en la cuarta celda. De este modo, el cromosoma de la figura asigna la máquina tres (M₃) a la operación O_{2,1}, la máquina uno (M₁) a la operación O_{1,1}, la máquina dos (M₂) a la operación O_{1,2}, etc.

Figura 3. Ejemplo de cromosoma de asignación.

Para evaluar la calidad de un individuo se utiliza la función de fitness. En este problema, el objetivo es la minimización del makespan; es decir, individuos con menor makespan tienen un mejor fitness; por lo cual, la función de fitness adoptada corresponde al inverso del makespan.

Los operadores genéticos más utilizados son el crossover y la mutación. El crossover corresponde al cruzamiento de los individuos de una población y el consiguiente intercambio de información genética en los individuos generados. La mutación, por otra parte, permite introducir la aleatoriedad que puede dar lugar a diferentes soluciones y permiten explorar distintas zonas de la región factible evitando óptimos locales o convergencia prematura.

El operador de crossover se aplica a los cromosomas de secuenciamiento y de asignación, entre cromosomas del mismo tipo. Dadas dos soluciones para aplicar el operador, se aplica a ambos cromosomas (con 20% de probabilidad); con 40% se aplica sólo al cromosoma de secuenciamiento y también con 40% se aplica sólo al cromosoma de asignación. Se utiliza el crossover de dos puntos, el cual selecciona dos posiciones aleatorias e intercambia los genes intermedios dando origen a dos soluciones nuevas. Una función verifica que los cromosomas obtenidos sean válidos para el subproblema correspondiente, si no es así, reasigna valores válidos. Los cromosomas de secuenciamiento pueden no ser factibles, ya que podría incrementarse el número de veces que aparece un trabajo en la solución; en este caso, se cambian los trabajos que se encuentran en exceso por aquellos en los que faltan operaciones. Los cromosomas de asignación pueden no ser válidos, ya que las máquinas podrían no ser factibles para las operaciones de los nuevos cromosomas; en este caso se cambia la máquina a una de las máquinas factibles seleccionada en forma aleatoria.

Se proponen tres operadores de mutación, de los cuales se aplica uno a cada individuo seleccionado para la mutación. El operador de mutación de asignación al azar, aplicado con 20% de probabilidad, selecciona una posición del cromosoma de asignación y cambia la máquina que ha sido asignada por otra máquina factible. El operador de asignación inteligente, también con 20% de probabilidad, es similar al anterior pero la nueva máquina asignada se escoge entre aquellas que tienen menor carga. El tercer operador modifica el cromosoma de secuenciamiento, tiene 60% de probabilidad; dado un cromosoma de secuenciamiento, escoge dos posiciones aleatoriamente y cambia su valor. Una función asegura que los cromosomas de operaciones y de asignación asociados continúen siendo válidos para el nuevo cromosoma de secuenciamiento.

La solución inicial del algoritmo genético se obtiene de modo aleatorio. Para generar un cromosoma de secuenciamiento se escoge una posición cualquiera y se le asigna la primera operación; en la celda a la derecha de ésta, se asigna la segunda operación y así sucesivamente se completan todas las celdas; cuando se llega a la última, se vuelve al inicio del vector. Una vez obtenida la población de secuenciamiento queda determinada la población de operaciones. Por cada cromosoma se debe generar un cromosoma de asignación, para lo cual, por cada celda, se escoge una máquina aleatoriamente. Se verifica que la máquina pueda procesar la operación, de lo contrario se escoge una nueva máquina para ser asignada.

Los parámetros del algoritmo genético son el tamaño de la población, el número de generaciones o iteraciones, la probabilidad de crossover y la mutación. Estos deben ser determinados por el usuario antes de su ejecución.

RESULTADOS

El algoritmo se implementa en Lenguaje C y los experimentos se realizan en un MacBook, con un procesador Intel Core 2 Duo de 2.4Ghz, 2GB de memoria RAM y sistema operativo Mac OS X 10.5.8.

Para la experimentación se utilizan algunas instancias de la literatura, disponibles en internet o en las publicaciones, mientras que otras han sido solicitadas a los propios autores. Es preciso señalar que los elementos que caracterizan a una instancia son: el número de máquinas, el número de trabajo y el número de operaciones totales.

El desempeño de cualquier metaheurística depende fuertemente de los parámetros que la controlan. Por esta razón, es muy importante hacer un análisis de cuáles son los mejores óptimos o intervalos de valores para estos parámetros, con la finalidad de encontrar los mejores resultados. Se usa un diseño experimental [4], para lo cual se seleccionan al azar ocho instancias de prueba (08a.fjs, 01a.fjs, 04a.fjs, Mk04.fjs, 11a.fjs, orb8.fjs, car5.fjs, mt20. fjs). Por cada parámetro se elige un valor inicial, un rango y un paso de incremento. Estos valores se muestran en la Tabla 2; fueron determinados de acuerdo a estudios preliminares de comportamiento del algoritmo propuesto.

Tabla 2. Valor inicial, rango y paso de incremento para la parametrización.

Por ejemplo, para el parámetro; "Tamaño de la Población", el algoritmo fue ejecutado para cada una de las ocho instancias de prueba y para cada valor de "Tamaño de Población" en el intervalo recomendado (1.000, 1.500, 2.000, 2.500, 3.000, 3.500, 4.000, 4.500 y 5.000), manteniendo constantes todos los otros parámetros. De igual forma se realizó el experimento para los otros parámetros restantes. De los resultados anteriores, los mejores parámetros en términos de makespan para el algoritmo propuesto son:

• Tamaño de la Población: 4.500
• Número de Generaciones: 3.000
• robabilidad de Crossover: 0,75
• Probabilidad de Mutación: 0,30

En Anexo A (Tabla 4) se encuentran los resultados alcanzados en cada una de las 137 instancias de la literatura utilizadas, se dispone de: número de máquinas (N° máq.), número de trabajos (N° trab.), número de operaciones totales (N° Ope.), tiempos de cómputo (Tiempo, en segundos) y el mejor valor de makespan obtenido. El tiempo medio de cómputo es 43,56 minutos. La convergencia del valor promedio de makespan por cada generación se muestra en el gráfico de la Figura 4. La línea violeta (superior) corresponde al makespan promedio de cada generación, mientras que la línea negra (inferior) corresponde al mejor makespan de cada generación. Se observa que ambas secuencias se estabilizan luego de 1.500 generaciones, aproximadamente, en un valor cercano a 1.500.

Figura 4. Convergencia de la media de los valores promedio de makespan y mejor makespan por cada generación.

DISCUSIÓN

La Tabla 3 compara los resultados obtenidos con el algoritmo propuesto respecto a otros algoritmos de la literatura. La primera columna indica el nombre del grupo de instancias; la segunda, el número de instancias en el grupo; la tercera, entrega el promedio de los mínimos makespan informados en la literatura , mientras que la cuarta columna entrega los promedios de nuestros resultados, ; la quinta columna indica el tiempo promedio de cómputo de nuestro algoritmo. Lamentablemente no se dispone de los tiempos de cómputo de los algoritmos de la literatura; la última columna indica la diferencia porcentual promedio entre la solución obtenida con nuestro algoritmo y la mejor de la literatura calculada de acuerdo a la fórmula:

(2)

Tabla 3. Comparación instancias de la literatura.

Se observa un buen desempeño del algoritmo. En las instancias de Chan [2] y Kacem [10] se superan o alcanzan las mejores soluciones conocidas, mientras en los otros grupos nuestra solución es cercana a la mejor solución conocida, sin superar el 50% de diferencia, en media. Respecto a los tiempos de cómputo, podemos ver que no exceden de una hora.

CONCLUSIONES

Esta investigación propone un algoritmo genético para resolver el problema de Job Shop Flexible. Mediante un diseño de experimentos se determinan los parámetros del algoritmo. Se resuelven instancias de la literatura, en un tiempo razonable para la programación de la producción en un taller que funciona a pedido.

Dado que las soluciones convergen, podrían ser mejoradas diversificando la población inicial o los operadores genéticos. También sería interesante paralelizar el algoritmo, lo cual permite disminuir los tiempos de cómputo y diversificar las soluciones.

AGRADECIMIENTOS

Este estudio fue apoyado por el proyecto ALFA Nº II-0457-FA-FCD-FI-FC, de la Comunidad Europea, coordinado desde Concepción (Chile), con la participación de investigadores de: Chile, Uruguay, Brasil, Cuba, Bélgica, Francia e Italia y por el proyecto DIUC-208.97011-1, de la Universidad de Concepción, Chile.

REFERENCIAS

[1] P. Brandimarte. "Routing and scheduling in a flexible job shop by tabu search". Annals of Operations Research. Vol. 41, Issue 1-4, pp. 157-183. 1993.

[2] F.T.S. Chan, T.C. Wong and L.Y. Chan. "Flexible job-shop scheduling problem under resource constraints". International Journal of Production Research. Vol. 44, Issue 11, pp. 2071-2089. 2006.

[3] H. Chen, J. Ihlow and C. Lehman. "A genetic algorithm for flexible job-shop scheduling". IEEE International Conference on Robotics and Automation. Vol. 2, pp. 1120-1125. 1999.

[4] S. Coy, B. Golden, G. Runger and E. Wasil. "Using experimental design to find effective parameter setting for heuristics". Journal of Heuristics. Vol. 7, pp. 77-97. 2001.

[5] P. Fattahi, M. Saidi Meharab and F. Jolai. "Mathematical modeling and heuristic approaches to flexible job shop scheduling problems". Jounal of Intelligent Manufacturing. Vol. 8, Issue 3, pp. 331-342. 2007.

[6] N.B. Ho and J.C. Tay. "Evolving dispatching rules for solving the flexible job-shop problem". IEEE Congress on Evolutionary Computation. Vol. 3, pp. 2848-2855. September, 2005.

[7] N.B. Ho, J.C. Tay and E.M.-K. Lai. "An effective architecture for learning and evolving flexible job-shop schedules". European Journal of Operational Research. Vol. 179, Issue 2, pp. 316-333. June, 2007.

[8] N.B. Ho and J.C. Tay. "GENACE: An efficient cultural algorithm for solving the flexible job-shop problem". Congress on Evolutionary Computation, pp. 1759-1766. 2004.

[9] J.H. Holland. "Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence". The MIT Press, 228 p. April, 1992.

[10] I. Kacem, S. Hammadi and P. Borne. "Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems". IEEE Transactions on Systems, Man, and Cybernetics. Vol. 32, Issue 1, pp. 1-13. February, 2002.

[11] K. Mesghouni, S. Hammadi and P. Borne. "Evolution Programs for job-shop scheduling". IEEE International Conference on Systems, Man and Cybernetics. Computational Cybernetics and Simulation. Vol. 1, pp. 720-725. October, 1997.

[12] F. Pezzella, G. Morganti and G. Ciaschetti. "A genetic algorithm for the flexible jobshop scheduling problem". Computers and Operations Research. Vol. 35, Issue 10, pp. 3202-3212. October, 2008.

[13] J.C. Tay and D. Wibowo. "An effective chromosome representation for evolving flexible job shop schedules". Lecture Notes in Computer Sciences. Vol. 3103/2004, pp. 210-221. 2004.

[14] M. Yazdani, M. Zandieh and M. Amiri. "Flexible job-shop scheduling with parallel variable neighborhood search algorithm". Expert Systems with Applications: An International Journal. Vol. 37, Issue 1, pp. 678-687. January, 2010.

[15] M. Gen, J. Gao and L. Lin. "Multistagedbased genetic algorithm for flexible job-shop scheduling problem". Complexity International. Vol. 11. 2005. URL: http://www.complexity.org.au/ci/vol11/zhang01/

ANEXO A. TABLA DE RESULTADOS

La primera columna de la Tabla 4 tiene el número y nombre de la instancia; la segunda, el número de máquinas (N° máq.); la tercera, el número de trabajos (N° trab.); la cuarta, el total de operaciones (N° Ope.); la quinta, el tiempo de cómputo del algoritmo propuesto y, la última, el mejor makespan encontrado. La instancia orb7.fjs no fue ejecutada por problemas en el archivo de lectura.

Tabla 4. Resultados del algoritmo propuesto.

Recibido 21 de diciembre de 2009, aceptado 10 de enero de 2011