MODELOS MATEMATICOS DEL SISTEMA FLEXIBLE JOB-SHOP

MODELOS MATEMTICOS DEL SISTEMA FLEXIBLE JOB SHOP

PRESENTADO A:PhD. JAIME ACEVEDO CHEDID

PRESENTADO POR:SERGIO ANDRES QUINTERO GONZALEZ

UNIVERSIDAD TECNOLGICA DE BOLVAR FACULTAD DE INGENIERAPROGRAMA DE INGENIERA INDUSTRIALCARTAGENA DE INDIAS, D. T. Y C. 2015ResumenEn este estudio se propone e implementa computacionalmente un algoritmo gentico secuencial para resolver el problema delJob Shop Flexible(existente en la Gestin de Operaciones), el cual es parte de la familia de los problemas de programacin de tareas o trabajos (Scheduling) en un taller que funciona a pedido. Surge como una generalizacin del problema delJob Shopy permite optimizar el uso de los recursos (mquinas) con mayor flexibilidad, ya que cada mquina puede realizar ms de una operacin. Este problema ha sido estudiado por numerosos autores, los que han propuesto diversos modelos matemticos y enfoques heursticos. Debido a la naturaleza combinatoria, los mtodos exactos que resuelven modelos matemticos encuentran soluciones slo para instancias pequeas o simples del problema mencionado. Los resultados muestran la efectividad del algoritmo propuesto para entregar buenas soluciones en tiempos computacionales razonables en ms de 130 instancias encontradas en la literatura.Palabras clave:ProblemaJob Shop Flexible, algoritmos genticos, programacin de trabajos, optimizacin combinatoria, gestin de operaciones.

MODELOS MATEMTICOS FLEXIBLE JOB SHOPEn la programacin de la produccin de las industrias manufactureras se debe decidir sobre la asignacin de los recursos a las tareas o trabajos para optimizar, uno o ms objetivos en el corto plazo. Para apoyar estas decisiones tradicionalmente se utiliza el modelo deJob Shop, el cual considera un conjunto de mquinas y un conjunto de trabajos compuestos por una secuencia ordenada de operaciones que se deben procesar en las mquinas con el objetivo de minimizar, entre otros, el tiempo de completacin de la ltima operacin, makespan.El problema deJob Shop Flexiblees una generalizacin del problema deJob Shop. Considera que las operaciones pueden ser procesadas por un grupo de mquinas, razn por la cual tambin se requiere decidir sobre cules de las mquinas procesan cada operacin.Por ejemplo, consideremos un taller metal-mecnico, en el que se reciben dos trabajos compuestos por una secuencia fija de tres operaciones a realizar en tres mquinas. 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 varan en las distintas mquinas, entonces, es necesario decidir cul mquina realiza cada operacin y en qu orden, con el objetivo de minimizar el tiempo total de completacin de todoslos trabajos.Este problema pertenece a la clase de problemas denominados de NP-Difciles, para los cuales an no se disponen de algoritmos de resolucin 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 jerrquico para la resolucin del problema, considerando un subproblema de asignacin y un subproblema de secuenciamiento. El primero lo resuelve como un problema de ruteo, mientras que el segundo corresponde al problema deJob Shop. Para probar el algoritmo, este investigador usa quince instancias delJob Shop Flexible. Mesghouni, Hammadi y Borne [2] en cambio, resuelven el problema utilizando algoritmos genticos, consideran un enfoque integrado, representando la solucin mediante matrices. Por su parte, Kacem, Hammadi y Borne [3] proponen un enfoque por localizacin, que permite encontrar buenas soluciones, minimizando elmakespany la carga de las mquinas. Este ltimo enfoque controla la evolucin de un algoritmo gentico.Ho y Tay [4] y en sus distintas publicaciones estudian el problema delJob Shop Flexible, proponiendo reglas de despacho que utilizan como solucin inicial para una nueva metodologa denominada GENACE [5], en la cual las poblaciones son influenciadas por reglas heursticas y en cada generacin se gua el espacio de bsqueda mediante esquemas. Otros autores tambin estudian las representaciones de las soluciones [6], para encontrar la ms eficaz en trminos de tiempo de cmputo y de alcanzar el mejor makespan. Este enfoque es generalizado en una publicacin posterior en Ho, Tay y Lai [7], donde se propone una arquitectura basada en algoritmos evolutivos, un aprendizaje con teora de esquemas y un generador de poblaciones mediante reglas de despacho compuestas.Fattahi, Meharab y Jolai [8] proponen un modelo matemtico para elJob Shop Flexibley para probarlo generan diez instancias pequeas y diez instancias medianas/grandes, aunque slo logran resolver las instancias pequeas. Utilizando tambin el enfoque jerrquico, combinan las metaheursticas deTabu Search y Simulated Annealing, con las que concluyen que el algoritmo que resuelve el subproblema de asignacin conTabu Searchy el subproblema de secuenciamiento conSimulated Annealingpresenta el mejor desempeo.Zhang y Gen [9] proponen un algoritmo gentico basado en escenarios mltiples, donde cada escenario corresponde a una operacin y cada mquina factible a un estado. Pezzella, Morganti y Ciaschetti [10] tambin proponen un algoritmo gentico, pero utilizan el enfoque de localizacin propuesto por Kacem, Hammadi y Borne [11].Con ello establecen una mutacin inteligente, que consiste en seleccionar una operacin entre aquellas mquinas con ms carga de trabajo y reasignar dicha carga a la mquina que tenga menos. Por ltimo, la publicacin ms reciente corresponde a Yazdani, Zandieh y Amiri [12], quienes proponen un enfoque en paralelo de vecindario variable (VNS), con seis vecindarios, minimizando tambin elmakespan.Todo lo anterior nos lleva a plantear que el objetivo del presente estudio es proponer e implementar computacionalmente un nuevo algoritmo gentico para resolver el problema deJob Shop Flexible, y luego comparar los resultados con otros obtenidos de la literatura en trminos de desempeo computacional y calidad de solucin.En 2007, los autores Juan Carlos Osorio Gmez y Tulio Gerardo Motoa Garavito [13], establece que el modelo busca resolver el problema mediante la definicin de dos niveles, cada uno de los cuales tiene asociado diferentes problemas de toma de decisiones. En este modelo se considera que existe recirculacin en el Job Shop, es decir, que un trabajo puede visitar una mquina en ms de una ocasin, permitindose inclusive que todas las operaciones de un trabajo sean procesadas en una nica mquina, tambin se considera que hasta tanto una operacin haya terminado su procesamiento, la mquina en la cual se est realizando dicha operacin no se podr considerar disponible para ningn otro trabajo. En el nivel superior, el problema es solamente la asignacin de los trabajos a los centros de trabajo, de manera que se minimice la sumatoria de los tiempos de ejecucin, pero se busca tambin que los centros de trabajo estn balanceados, es decir, que no se recargue uno solo, puesto que si esto llega a suceder, el makespan, es decir, el mximo tiempo de terminacin de todos los trabajos, tendera a incrementarse, puesto que el centro mayor cargado sera el que determine el ltimo tiempo de terminacin, por tanto, lo que se debe buscar es que todos los centros tengan una carga similar y de esa manera, el tiempo de terminacin de cada uno sea equivalente, para lograr un mejor valor de makespan. En el nivel inferior o detallado, se realiza inicialmente la desagregacin de los centros de trabajo en mquinas y de los trabajos en operaciones. Una vez se realiza esta desagregacin, se tienen L subproblemas similares, en los cuales debe resolverse la asignacin de las operaciones que conforman los trabajos - que fueron asignados en el nivel superior-, a las mquinas que conforman el centro de trabajo en el que dicho trabajo fue asignado; y una vez resuelta la asignacin, se procede a realizar el secuenciamiento de dichas operaciones en las mquinas (el problema del scheduling), para finalmente tener el programa de produccin que define en qu momento y en cul mquina se deben procesar las operaciones, que es en resumen el problema del job shop flexible. Este problema ha sido abordado de mltiples maneras a lo largo de la historia. El Job Shop Scheduling es uno de los problemas combinatorios no polinomiales ms investigados y el nmero de artculos y trabajos desarrollados en torno a su solucin es enorme. Uno de los enfoques utilizados para la solucin ha sido el empleo de modelos de simulacin [(Bitran et al, 1983), (Tavakkoli y Daneshmand, 2005)], en los cuales se obtienen resultados interesantes para la solucin del problema, los cuales pese a no ser ptimos, se consideran como buenos resultados, dado su tiempo de respuesta y la flexibilidad de la herramienta. Como los problemas resultantes en la validacin de este modelo fueron pequeos, la solucin del Scheduling se logr mediante el empleo de simulacin simple utilizando el mdulo de Job Shop Scheduling del WinQsb.

En 2008, los autores Alexander Alberto Correa Espinal, Elkin Rodrguez Velsquez, Mara Isabel Londoo Restrepo [14], establecen que en el problema de asignacin de operaciones en la configuracin de planta tipo Flexible Job Shop, presenta dos problemas a resolver el primero consiste en la asignacin de cada operacin a la mquina y el segundo es referente a la secuencia de operaciones a cada mquina para minimizar la funcin objetivo. Los procesos de manufactura en la actualidadse han vuelto ms complejos por lo que, la secuencia de operaciones se ha convertido enuntema importante para mejorar la competitividad de las compaas, el problema del Flexible Job Shop Scheduling se ajusta de manera adecuada a los problemas reales de casi todos los tipos de manufactura y en todos los sectores. Entonces, dada la importancia de los problemas prcticos del tipo planeacin Schedulingy a sugran dificultadde obtener soluciones por ser del tipo NP-Hard, es de relevancia el dirigir nuestra mirada a los acercamientos a travs de meta heursticas, pues con una investigacin ms profunda se puede encontrar un camino para una importante simplificacinen el trato de estos problemas. De acuerdo a la bsqueda realizada enla literatura encontramos que, los algoritmos genticos son los ms recurrentes a la hora de solucionar el problema genrico del JSSP. Mediante el enfoque de algoritmos genticos se logra encontrar una alternativa para la evaluacinde un problema Flexible Job Shop Scheduling, de acuerdo a la literatura, tambin encontramos que por medio de este enfoque, se puede incrementar la eficiencia algortmica en cuanto a complejidad y encontrar buenas soluciones, en cuanto a la asignacin y la secuencia.

En 2011, los autores Rosa Medina Durn, Lorena Pradenas Rojas & Vctor Parada Daza [15], establecen que es fundamental utilizar una codificacin de las soluciones que represente las caractersticas del problema y respete las restricciones. Para la representacin de la solucin y para una mejor comprensin y tratamiento de la solucin, en este estudio se propone que cada solucin del problema utilice tres vectores. El primero de ellos representa una solucin para el subproblema de secuenciamiento; el segundo indica la operacin a la cual corresponde cada celda y el tercero determina una solucin para el subproblema de asignacin. La solucin inicial del algoritmo gentico se obtiene de modo aleatorio. Para generar un cromosoma de secuenciamiento se escoge una posicin cualquiera y se le asigna la primera operacin; en la celda a la derecha de sta, se asigna la segunda operacin y as sucesivamente se completan todas las celdas; cuando se llega a la ltima, se vuelve al inicio del vector. Una vez obtenida la poblacin de secuenciamiento queda determinada la poblacin de operaciones. Por cada cromosoma se debe generar un cromosoma de asignacin, para lo cual, por cada celda, se escoge una mquina aleatoriamente. Se verifica que la mquina pueda procesar la operacin, de lo contrario se escoge una nueva mquina para ser asignada. Los parmetros del algoritmo gentico son el tamao de la poblacin, el nmero de generaciones o iteraciones, la probabilidad de crossover y la mutacin. Estos deben ser determinados por el usuario antes de su ejecucin. Esta investigacin propone un algoritmo gentico para resolver el problema de Job Shop Flexible. Mediante un diseo de experimentos se determinan los parmetros del algoritmo. Se resuelven instancias de la literatura, en un tiempo razonable para la programacin de la produccin en un taller que funciona a pedido. Dado que las soluciones convergen, podran ser mejoradas diversificando la poblacin inicial o los operadores genticos. Tambin sera interesante paralelizar el algoritmo, lo cual permite disminuir los tiempos de cmputo y diversificar las soluciones.

Referencias bibliogrficas[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] 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.[3] 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.[4] 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.[5] 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.[6] 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.[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] 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.

[9] M. Gen, J. Gao and L. Lin. "Multistagedbased genetic algorithm for flexible job-shop scheduling problem". Complexity International. Vol. 11. 2005.[10] 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.[11] 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.[12] 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.[13] Planificacin jerrquica de la produccin en un Job Shop Flexible [en lnea]. Escuela de Ingeniera Industrial y Estadstica, Facultad de Ingeniera, Edificio 357, Universidad del Valle, Calle 13 No. 100-00, Ciudad Universitaria Melndez, Cali, Colombia: Juan Carlos Osorio Gmez & Tulio Gerardo Motoa Garavito, Octubre de 2007. [Consulta: 27 de junio de 2015]. Disponible en: http://www.scielo.org.co/pdf/rfiua/n44/n44a15.pdf[14] Secuenciacin de operaciones para configuraciones de planta tipo flexible Job Shop: Estado del arte [en lnea]. Escuela de Ingeniera de la Organizacin, Universidad Nacional de Colombia Sede Medelln: Alexander Alberto Correa Espinal, Ph.D,Elkin Rodrguez Velsquez, MSc, Mara Isabel Londoo Restrepo, Ing., Noviembre de 2008. [Consulta: 27 de junio de 2015]. Disponible en: http://www.bdigital.unal.edu.co/15495/1/10109-18482-1-PB.pdf[15] Un algoritmo gentico para el problema de Job Shop Flexible [en lnea]. Ingeniare. Revista chilena de ingeniera, Chile: Rosa Medina Durn, Lorena Pradenas Rojas & Vctor Parada Daza, Enero de 2011. [Consulta: 27 de junio de 2015]. Disponible en: http://www.scielo.cl/pdf/ingeniare/v19n1/art06.pdf