Source: http://docplayer.es/1260286-Secuenciacion-de-operaciones-para-configuraciones-de-planta-tipo-flexible-job-shop-estado-del-arte.html
Timestamp: 2017-01-18 12:28:44+00:00

Document:
⭐Secuenciación de operaciones para configuraciones de planta tipo flexible Job Shop: Estado del arte
Secuenciación de operaciones para configuraciones de planta tipo flexible Job Shop: Estado del arte
Download "Secuenciación de operaciones para configuraciones de planta tipo flexible Job Shop: Estado del arte"
Alberto Navarrete Juárez
1 Secuenciación de operaciones para configuraciones de planta tipo flexible Job Shop: Estado del arte Scheduling for shop settings types to flexible Job Shop: State of the art Alexander Alberto Correa Espinal, Ph.D, Elkin Rodríguez Velásquez, MSc, María Isabel Londoño Restrepo, Ing. Escuela de Ingeniería de la Organización, Universidad Nacional de Colombia Sede Medellín Recibido para revisión: 2 de Octubre de 2008, Aceptado: 28 de Noviembre de 2008, Versión final: 22 de Diciembre de 2008 Resumen Un número considerable de investigaciones han sido enfocadas en solucionar el problema de las configur aciones de planta tipo Flexible Job Shop, problema genérico correspondiente al problema Job Shop; por años, numerosos métodos han sido pr opuestos para resolver difer entes instancias del problema, dependiendo de las restricciones impuestas y del objetivo mismo. Recientemente muchos de esos acercamientos se han concentrados en técnicas conocidas como algoritmos interactivos de búsqueda local o meta heurísticas. En este artículo estamos interesados en ilustr ar el estado actual de desar rollo de los métodos meta heurísticos, principalmente algoritmos genéticos existentes en la literatura para el problema genérico del Job Shop minimizando el makespan. Adicional a esto incluimos las posibles líneas de investigación en trabajos futuros. Pala bras Clave Flexible J ob Shop, Algor it mos genéticos, Secuenciación de oper aciones, Makespan. Abstract A considerable number of research have been focused on solving the problem of the configurations of shop type Flexible Job Shop, it s the generic problem for the Job Shop problem, for years, many methods have been proposed to solve differ ent instances of the problem, depending on the constraints and the performance indicator. Recently many of these approaches have focused on techniques known as interactive local search algorithms or heuristics. In this paper, we are interested in illustrating the current state of development of the heur istic methods, mainly genetic algor ithms in the liter ature for the gener ic problem of Job Shop minimizing the makespan. Additional to this we include the possible lines of research in future works. Keywords Flexible J ob Shop, Genetic algorithms, Scheduling, Makespan. I. INTRODUCCIÓN rwich y Brech [1984] introducen referencias sobre la U planificación de la producción, indican que toda aquella persona que esté familiarizada con la industria debe apreciar la enorme ventaja que se obtiene de un análisis de las necesidades, si es posible, para todo el año. Indican que cuando uno conoce, a intervalos regulares de tiempo, la cantidad de producción que es demandada, por lo tanto, a procesar, es posible desarrollar programas para la manufactura, que permitan a la compañía alcanzar un pleno rendimiento; que la producción se abarate enormemente; que no sea necesario mantener grandes stocks en tiempos excesivos; que el capital y el interés se economicen, en general que aumente la eficacia [1]. La planificación es un proceso complejo, en el que hay que tener en cuenta muchos factores y considerar ciertos objetivos. Precisamente por este motivo no es posible tenerlos en cuenta a la vez y, por lo tanto, se debe establecer una metodología racional si se desean obtener resultados útiles. Por eso, se consideran diferentes niveles de planificación relacionados entre sí, con distintos niveles de detalle, y plazos de tiempo para llevarlos a cabo. La secuenciación de operaciones hace parte del nivel de planificación a corto plazo y principalmente, es una área de investigación desde hace más de cinco décadas, es una rama de la optimización combinatoria que ha desarrollado su propia metodología utilizando herramientas matemáticas y computacionales variadas; donde el objetivo es encontrar una secuencia óptima para la ejecución de unos trabajos y sus respectivas operaciones en las máquinas o recursos disponibles limitados, la optimalidad de la secuencia depende de la función objetivo. Es un proceso de toma de decisiones que constituye uno de los problemas más importantes en gestión de la producción, tanto desde el punto de vista teórico como práctico [2]. Las investigaciones recientes en la teoría de la secuenciación Revista Avances en Sistemas e Informática, Vol. 5 No.3, Diciembre de 2008, Medellín, ISSN2 152 Revista Avances en Sistemas e Informática, Vol. 5 No. 3, Diciembre de 2008, Medellín, ISSN de operaciones han sido objeto de significativos desarrollos con técnicas como reglas de despacho altamente sofisticadas y algoritmos basados en heurísticas y meta heurísticas, estos desarrollos han sido formulados por un amplio y diverso espectro de investigadores, indicando entonces, la multiplicidad de este campo, además el amplio campo de aplicación de la secuenciación, a su vez se han hecho acercamientos a diferentes tipos de configuraciones de planta. Uno de los más populares modelos en la teoría de la secuenciación es el problema del Job Shop (JSSP), que es considerado como una buena representación de las configuraciones de planta industriales reales modernas; sin embargo en investigaciones recientes se estableció un problema más genérico para el JSSP, llamado el problema del Flexible Job Shop Scheduling (FJSSP) por lo que es una representación realmente aproximada a los sistemas de manufactura actuales, dado la posibilidad de la configuración de centros de trabajo en la planta, que constituye un conjunto de máquinas que pueden ejecutar una de las operaciones especificas de los trabajos, por lo que el FJSSP es más complejo que el JSSP, por que la meta de la secuenciación es, escoger una asignación para cada una de las operaciones de los trabajos a alguna máquina del conjunto, el problema genérico del JSSP ha sido menos estudiado que este último, sin embargo se ha conocido como un problema NP Hard, por lo que los investigadores han desarrollado diferentes técnicas para llegar a acercamientos exitosos en la secuenciación del problema Flexible Job Shop Scheduling. Por lo tanto, El objetivo de este documento es ofrecer una visión de este problema de secuenciación y los métodos, desde sus inicios hasta la actualidad, destacando las referencias y las propuestas de cada autor. II. CONCEPTOS BÁSICOS Según Fogarty, Blackstone y Hoffmann [1991] plantean que, la planeación de producción es la fijación de objetivos de producción cuantificables en el tiempo (Planeación estratégica) y la toma de decisiones sobre la determinación de cómo lograrlos; por lo que esto implica determinar las cantidades a producir para un horizonte temporal de planificación, conformando lo que se denomina un plan de producción [3]. La programación de operaciones (scheduling), en un sentido amplio, puede pensarse como; la asignación de recursos (máquinas) en un lapso de tiempo para realizar un conjunto de trabajos [4], o bien como resolver el problema de encontrar la asignación óptima de ciertos recursos a determinados tareas [5]. Por lo que, en un problema de planificación siempre existirá tres componentes diferenciadas: las tareas u operaciones (trabajos) que se tienen que realizar, los recursos disponibles para su realización (máquinas), y las finalidades u objetivos (función objetivo) que se desean lograr y que nos permite identificar, entre varias planificaciones posibles, aquellas que sean óptimas, de acuerdo a los componentes anteriores, los problemas de planificación se dividen en dos, deterministicos y estocásticos. Se denomina deterministico, ( Deterministic machine scheduling ) cuando todos los datos del problema de planificación son conocidos a priori. Estos modelos son estudiados por la optimización combinatoria; una característica común a la mayoría de los problemas estudiados por la optimización combinatoria es que son relativamente fáciles de plantear, pero difíciles de modelizar y, consecuentemente, mucho más difíciles de resolver, [6]. Una extensión natural de los modelos de planificación determinístico, consiste en asumir que ciertos datos del problema varían aleatoriamente y, de esa forma, aparecen los problemas de Planificación Estocástica ( Stochastic machine scheduling ) [7]. El estado de planificación determinística, es especialmente frecuente en los problemas de planificación y secuenciación de tareas, por tanto su resolución exige el uso de medios de computación adecuados. Los correspondientes aspectos computacionales se estudian analizando la complejidad computacional de los métodos propuestos. En este sentido, es importante mencionar el análisis de la complejidad computacional de problemas combinatorios y las implicaciones resultantes para el diseño y análisis de algoritmos adecuados. Se acepta comúnmente que un problema está bien resuelto o es fácil si se puede resolver por un algoritmo cuyo tiempo de ejecución éste acotado por una función polinomial en el tamaño del problema [8]. En la mayoría de problemas de optimización combinatoria no se tiene conocimiento de la existencia de tal algoritmo; entonces, surge la cuestión de probar si el problema es NP Hard o puede resolverse en tiempo polinomial, (los problemas NP hard son un subconjunto de la clase NP Problemas para los que no se puede tener una solución en tiempo polinomial para todas sus instancias Con la característica de que todos los problemas de ésta clase pueden ser reducidos a NP). Los problemas para los que se puede encontrar un algoritmo de solución en tiempo polinomial forman la clase P, que es un subconjunto de la clase NP, [9 y 10]. Es decir, el tiempo de cómputo que se requiere para resolver uno de estos problemas se incrementan conforme crece el tamaño del problema presentando una dependencia funcional tal que no admite ser acotada por un polinomio; en consecuencia a esto, la resolución de este tipo de problemas se centra en encontrar soluciones cuasi óptimas en tiempos de aplicación razonable; lo que quiere decir que se prefiere comprometer la calidad de la solución a cambio de obtener el acceso del resultado en un tiempo viable. Muchos autores han medido los algoritmos de acuerdo a varios indicadores, para escoger el mismo, uno de los distintos tipos de indicadores, incluyen, la raíz cuadrada del retraso, el tiempo medio de estancia en el sistema y el número de cambios3 Secuenciación de operaciones para configuraciones de planta tipo flexible Job Shop: Estado del arte Correa, Rodríguez y Londoño 153 de recursos auxiliares. A medida que aumenta la utilización de la planta, el estudio revelará que un algoritmo escogido proporciona muy buenos resultados en los tres tipos de indicadores mencionados [11]. Teniendo en cuenta que los algoritmos adaptativos para la programación de la producción, como los algoritmos genéticos han entregado buenas soluciones durante el proceso de investigación, y usualmente mejoran al acercamiento de la solución óptima, ese es el enfoque que se discutirá a través de este documento. Los a lgoritmos genéticos (AG) son algoritmos de optimización aproximados que utilizan una terminología basada en los procesos de evolución genéticos de las especies. En realidad, los AG emplean los mecanismos de selección natural y la genética para encontrar soluciones óptimas a problemas de optimización combinatorios. Los AG surgieron a partir de los estudios llevados a cabo por John Holland en la Universidad de Michigan. Goldberg [1989] proporciona una interesante recopilación del trabajo práctico llevado a cabo en esta área. Los Algoritmos Genéticos pueden entenderse como una generalización de los algoritmos estocásticos de búsqueda local. El espacio de búsqueda de las soluciones candidatas se asemeja a un conjunto de organismos agrupados en poblaciones que evolucionan en el tiempo. La función objetivo del problema de optimización se implementa como una función de adaptación de organismos. La función de adaptación representa el grado de adaptación al entorno del organismo. Los Algoritmos Genéticos se aplican a campos como la planificación de operaciones en planta, problemas de corte de materiales y de componentes irregulares, el entrenamiento de redes neuronales y muchos otros problemas de optimización. Los AG presentan muchas ventajas de cara a su empleo en problemas de programación de operaciones en planta. La calidad de la solución y el tiempo de proceso dependen directamente de los parámetros de los AG, concretamente del número de organismos de la población y del máximo número de generaciones a probar. Esta característica les confiere gran flexibilidad. Rossi y Dini [2000] [12] afirman que es posible encontrar los mejores valores de los parámetros de configuración de un AG a través de otro procedimiento de optimización. III. DESCRIPCIÓN DEL PROBLEMA El problema de secuenciación de FJSSP presenta una serie de variantes dependiendo de la naturaleza y el comportamiento; tanto de las operaciones como de las máquinas. Una de las variantes más difíciles de plantear, debido a su alta complejidad computacional, es aquella en donde las tareas son dependientes y las máquinas son diferentes. En esta variante cada trabajo presenta una lista de operaciones que la preceden y para ser ejecutada deben esperar el procesamiento de dicha lista en su totalidad. A esta situación hay que agregarle la característica de heterogeneidad de las máquinas: cada tarea demora tiempos distintos de ejecución en cada máquina. El objetivo será minimizar el tiempo acumulado de ejecución de las máquinas, conocido en la literatura como makespan En el problema de asignación de operaciones en la configuración de planta tipo Flexible Job Shop, presenta dos problemas a resolver; el primero consiste en la asignación de cada operación a la máquina y el segundo es referente a la secuencia de operaciones a cada máquina para minimizar la función objetivo. El problema de FJSSP suele ser definido por las siguientes condiciones [13]: Hay n trabajos con subíndice i, y estos trabajos son independientes entre ellos. Cada trabajo i tiene una secuencia de operación, denotada por J i. Cada trabajo consiste de una o más operaciones O i,j. Cada secuencia de operación está ordenada por un juego de operaciones O i,j Hay m máquinas con subíndice K (El k ésima máquina es denotado por m k ) Para cada operación O i,j. hay un juego de maquinas capaces de cumplir con la función objetivo. Este juego de máquina es denotado por U i,j. Los tiempos de procesamiento P i, de una operación O i,j en una máquina K es predefinido y mayor que cero. Restricciones generales Cada operación no puede ser interrumpida durante el cumplimiento de la ejecución de la misma. Todas las máquinas están disponibles en el tiempo t=0 Cada máquina K, no puede procesar más de una operación simultáneamente. Un problema de programación de operaciones está definido por tres campos α, β, γ, donde α representa la configuración del taller, β representa las restricciones y/o características propias a las tareas, y γ es la función objetivo que se va a minimizar. Por consiguiente, nuestro problema es denotado por Vaessens, en su tesis doctoral, [1995], basada en los estudios de Graham y otros [1966], entonces, el problema puede ser denotado como [14]: m1m/ Chain,opd µ / Cmax, donde: el primer campo m especifica el numero de maquinas, es una constante, 1 especifica que alguna operación requiere al menos de una máquina para ser procesada y la segunda m indica un limite superior del numero de máquinas que puede procesar una operación. El segundo campo muestra el estado de las restricciones de precedencia y el máximo numero de operaciones por trabajo, mientras que el tercer campo indica la función objetivo.4 154 Revista Avances en Sistemas e Informática, Vol. 5 No. 3, Diciembre de 2008, Medellín, ISSN Este problema es conocido como fuertemente NP Hard, incluso si el trabajo tiene tres operaciones y tan sólo dos máquinas [15]. Williamson y otros [16] demostraron que, cuando el número de máquinas, trabajos y operaciones por trabajo son parte de la entrada, en este caso no existe una aproximación de tiempo polinomial con el peor de los casos como limite inferior de 5/4 a menos que P=NP. Otra versión de la complejidad computacional es presentada por González y Sahni [1978] es que el problema es fuertemente sensible cuando m=3 y µ=3 [17] IV. SECUENCIACIÓN DE OPERACIONES DE UNA PLANTA CON CONFIGURACIÓN TIPO J OB SHOP El problema clásico de programación Job Shop para minimizar el makespan, J//C max fue presentado por primera vez por Fisher y Thompson,[1963]; desde entonces el problema ha sido un tema estándar en la programación y secuenciación de operaciones. [18]; Morton y Pentico, [1993] Y Rinnooy Kan, [1976]; proporcionaron un estudio para este problema de la demostración de que el problema es NP Hard. El problema del Job Shop es un programa que consiste en; un juego de N trabajos en M máquinas, cada trabajo i es procesado en una máquina de acuerdo a la secuencia de operaciones Ji, además la secuencia final de las operaciones es independiente de los tiempos de procesamiento de cada una de las operaciones y los trabajos; donde generalmente se ha encontrado que las investigaciones determinan como criterio de optimalidad para este problema, la minimización de la función regular de optimización, Makespan. Uno de los acercamientos más tempranos al esquema de algoritmo genético fue desarrollado por Nakano y Yamada [1991], quienes crearon una codificación binaria basada en las relaciones de precedencia de operaciones con iguales máquinas; una estrategia llamada Forcing, en 1992 estos mismos autores mejoraron este trabajo, definiendo un operador de cruce llamado GA/GT basado en el algoritmo desarrollado por Giffler y Thompson [1960]. En el desarrollo de Nakano y Yamada los cromosomas están en una lista ordenada de tiempos de completación de las operaciones [19]. Un acercamiento importante mediante algoritmos genéticos lo dio Bean [1994], donde propuso sistemas de aleatorios para la codificación de esta meta heurística, Bean y norma [1997] desarrollaron y mejoraron el desarrollo anterior de Bean, donde establecieron cada gen, mediante una generación aleatoria de caracteres, que se componía de dos partes: una parte entera {1, 2,¼, m}y una segunda fracción generada de un aleatorio (0,1). La parte entera del gen es la asignación de la máquina mientras que la parte binaria, determina la secuencia de operación en cada máquina [20]. Kumar y otros [1996] [21] direccionaron su trabajo de investigación, en el desarrollo de un algoritmo genético y una combinación de reglas de despacho, el propósito de este algoritmo fue mejorar una solución anteriormente determinada para este problema, reduciendo el makespan al 30% sobre ese sistema, que consistía en, un algoritmo ramal y limite que determinaba el óptimo makespan probado para un pequeño grupo de problemas y basado en heurísticas de reglas de despacho especificas para minimizar diferentes medidas de cumplimiento disponibles para un gran grupo de problemas; Azarmi y otros [2000] [22], ellos propusieron un algoritmo genético con una representación incompleta, lo que quiere decir es que, el numero de genes es menor que el número de operaciones y lo aplicaron al JSSP, lo mas importante de su desarrollo fue la decodificación en la secuenciación del cromosoma y el resto del programa es completado por una simple regla heurística, este enfoque fue considerado debido a que; la solución de este tipo de problemas es contenido por un cromosoma a una programación real, desde el primer gen hasta el último gen; presentándose dos problemas para los algoritmos genéticos, alta redundancia y pequeña significancia de posteriores genes sobre la calidad de la secuenciación. Eikelder y otros [2001] [23], ellos describen un algoritmo hibrido, una combinación de algoritmos genéticos y búsqueda tabú, los componentes de su algoritmo genético son: Una representación natural de la solución y una recombinación capaz de transmitir las características significativas de los padres a los hijos; los problemas de factibilidad y restricciones de los trabajos fueron discutidas y solucionadas en el esquema de trabajo. El operador de cruce (Recombinación) desarrollado preserva la diversidad en la secuencia de los padres. Además, todo el algoritmo genético fue hibridizado con búsqueda tabú (tabu search, TS) y sus resultados experimentales mostraron que es más beneficioso combinar GA con TS que otros acercamientos como el recocido simulado, porque requiere menos tiempo para obtener una solución de calidad y una gran diferencia en el orden de las magnitudes en la solución. En estas instancias los autores requieren determinar los valores para los parámetros de los algoritmos propuestos para entregar en menor tiempo una solución de calidad, por lo que, la parametrización de los modelos comenzó a ser un tema adicional en los trabajos desarrollados para la secuenciación de operaciones, cómo método para mejorar la calidad de la solución y los tiempos computacionales; Pérez y Herrera [2006], [24] desarrollaron un algoritmo genético multimodal, para el problema de Job Shop, con el criterio de optimalidad del makespan, donde inicialmente pretendían conocer más sobre este método, el que a demostrado ser uno de los más potentes, y conocer sobre el comportamiento de este método con respecto a la variación de sus parámetros; donde analizaron la influencia de dichos parámetros en la eficacia del método, y principalmente, sobre su efectividad, entendida esta como la capacidad de alcanzar en una única ejecución del algoritmo el mayor número posible de soluciones óptimas globales del problema. Además, estudiaron la posibilidad de dirigir la5 Secuenciación de operaciones para configuraciones de planta tipo flexible Job Shop: Estado del arte Correa, Rodríguez y Londoño 155 búsqueda hacia la exploración del espacio de búsqueda o su explotación, variando la parametrización, la parametrización del algoritmo lo desarrollaron mediante un método denominado clearing. En el 2007, [25] desarrollaron un algoritmo basado en agentes, colonia de hormigas para el problema del Job Shop scheduling para minimizar el makespan, donde los parámetros del algoritmo fueron calibrados utilizando un diseño experimental, factorial completo; en los modelos de secuenciación los parámetros son calibrados para reducir los tiempos computacionales de ejecución de algoritmo sin sacrificar la calidad de la solución. Y para determinar los efectos e interacciones en el valor del makespan, utilizaron un diseño experimental fraccionado. En el 2008, [26], consideraron el problema de Job shop con fecha prevista para iniciación de cada uno de los trabajos y fecha prevista de entrega, con el objetivo de minimizar el peso total de la tardanza, en esta investigación usan un algoritmo genético combinado con una búsqueda interactiva local, que usa una larga ruta de acercamiento en un grafico de un modelo disyuntivo, donde es empleado el diseño de experimentos para calibrar los parámetros y operadores del algoritmo; donde ellos detectaron que, los algoritmos genéticos son altamente dependientes de las cromosomas que son decodificadas, también ellos muestran que, la eficiencia de los algoritmos genéticos no depende de la construcción de la programación cuando una heurística de búsqueda local interactiva es usada. Sin embargo, en las investigaciones recientes los acercamientos a la configuración de planta tipo Job Shop han sido, mediante optimización bicriterio, es decir dos criterios de optimización, donde la función objetivo no es una función regular. En el 2008, se hicieron acercamientos con optimización bicriterio (Makespan y máxima demora) [27] en esta investigación encontraron una aproximación a la frontera de Pareto. Ellos propusieron un algoritmo genético rápido y elitista, basado en NSGA II para solucionar el problema, en este trabajo la población inicial del algoritmo es generado por un aleatorio de partida generado usando un algoritmo de búsqueda tabú; los dos algoritmos desarrollados son probados mediante programa benchmark y los resultados computacionales muestran la efectividad y eficiencia del algoritmo por la resolución de ambos métodos. V. SECUENCIACIÓN DE OPERACIONES PARA LA CONFIGURACIÓN DE PLANTA TIPO FLEXIBLE J OB SHOP El problema del Flexible Job Shop Scheduling (FJSSP) es una generalización del clásico problema de Job Shop, donde se determina y se optimiza de acuerdo a un criterio, las rutas de los trabajos, por lo que significa decidir, la ruta para cada operación, en que máquinas ha ser procesadas y la disponibilidad de las mismas, optimizando esa secuencia. Varios procedimientos heurísticos (reglas de despacho, búsqueda local y meta heurísticos) han sido utilizado en las investigaciones de acercamiento a la configuración de este tipo de planta como son: búsqueda tabú (tabu search, TS), enfriamiento simulado (simulated annealing, SA) y algoritmos genéticos (genetic algorithm, GA) han sido desarrollados en los últimos años para FJSSP. La solución de este tipo de problemas pueden ser clasificados en dos categorías: planteamientos jerárquicos y planteamientos integrados. A. Planteamiento jerárquico e integrado para el enfoque de solución El planteamiento jerárquico, trata de resolver el problema por descomposición de una secuencia en subproblemas, y con ello reducir la dificultad. Una típica descomposición es la asignación luego secuenciar, partiendo desde la observación trivial, una vez que la asignación es hecha, el resultado de la programación es un Job Shop Scheduling. Este enfoque ha sido trabajado por Brandimarte P. [1993], Paulli J. [1995], Chambers JB y Barnes JW. [1996]; ellos tratan de resolver el problema de asignación utilizando reglas de despacho, y luego resolver el resultado de JSSP usando diferentes algoritmos, entre ellos búsqueda tabú [28]. Por otra parte el planteamiento integrado, es realizar de forma integrada la asignación y la secuenciación, posee más dificultad para ser resuelto, pero en general da mejores resultados, como lo describe Vaessens y otros [1994], Hurink J, Jurish B, Thole M., [1994], Mastrolilli M y Gambardella LM., [1996] y Dauzére Pérés S y Paulli J., [1997]. Ellos adoptan un planteamiento integrado, proponiendo diferentes formas de búsqueda tabú para resolver el problema [29]. Mastrolilli y Gambordella, [30] muestran resultados computacionales los cuales enseñan que el desempeño de la búsqueda tabú es mejor que otros desarrollos heurísticos, ambos en términos de tiempo de procesamiento computacional y calidad de la solución. B. Enfoque de solución para el problema General del Job Shop Muchos autores han definido el modelo general y han trabajado con el en sus investigaciones, el problema que han considerado como modelo General del Job Shop Scheduling Problem (GJSSP), es definido como un numero de trabajos a ejecutar, cada uno con un juego de operaciones que deben ser procesadas en un especifico orden; las rutas no son necesariamente lineales; los recursos son máquinas que pueden ser usadas para diferentes tipos de procesamiento y la ejecución de cada una de las operaciones puede ser realizada en un recurso elegido de un grupo de ellas. Este problema es considerado por unas razones prácticas, no necesariamente a los autores les interesa un único criterio de optimalidad, sino que requieren varios criterios para tener una mejor calidad en la solución [31], en la mayoría de los trabajos relacionados a la6 156 Revista Avances en Sistemas e Informática, Vol. 5 No. 3, Diciembre de 2008, Medellín, ISSN programación de tareas se concentra en el JSSP, son pocos los que hay sobre GJSSP, que puede ser considerado plenamente como un FJSSP, los siguientes son los trabajos desarrollados en la literatura que solucionan el problema del GJSSP. Para el GJSSP, Paullí [1995] [32] plantea un algoritmo jerárquico donde el primer paso es resolver el problema de asignación, y el segundo paso es resolver el JSSP. Dauzére Pérés S y otros [1997] [33] proponen un algoritmo de búsqueda tabú para resolver el makespan de un GJSSP. Kacem y otros [2002] [34] plantea la hibridación de un algoritmo evolutivo y lógica difusa. Alvarez Valdez y otros [2005] [35] plantean un algoritmo heurístico para un GJSSP para una industria de vidrio con restricciones de no espera o traslapes. Con el objetivo de encontrar una secuencia con un criterio basado en las penalizaciones de tardanza y en la prontitud. Los autores generan un algoritmo de dos pasos; en el primero priorizan las rutas de los trabajos que son utilizadas para resolver el problema, y en el segundo paso mejoran la solución con una búsqueda local. Para la investigación de G. Vilcot y J. Billaut, [2008], planteada anteriormente en el cual desean comparar los procedimientos de búsqueda tabú y el algoritmo genético, consideran como problema base el General Job Shop Scheduling Problem GJSSP. C. Enfoque de solución Jerárquico para el Flexible Job Shop mediante el enfoque de máquinas paralelas Al procesar una cantidad de trabajos estos deben pasar por varias etapas, y en cada etapa hay un determinado numero de maquinas paralelas con diferentes capacidades de procesamiento de los trabajos. Además generalmente hay etapas que representan cuellos de botella para el procesamiento de los trabajos, con lo cual al secuenciar los trabajos se tienen en cuenta las restricciones, como la capacidad y la productividad de cada maquina, el tomar la decisión de la posición de los trabajos para las maquinas y la selección de los tiempos de comienzo de cada trabajo, es un proceso complejo que requiere ser analizado y discutido desde varias perspectivas, el problema de secuenciar en una planta con configuración FJSSP, puede ser adaptado a secuenciar, teniendo en cuenta principalmente la configuración de los recursos en cada etapa. Chichang [2005] [36], realizó una investigación evaluando un algoritmo genético con partición de genes sub indexados con número distintivo (GASP), con operadores que incrementan la diversidad de permutación, cuando el número de generaciones con la misma mejor solución excede un punto de inicio, un comportamiento es cambiado para ayudar a que el algoritmo se impulse fuera del sub optimo y con ello prevenir una convergencia prematura; utilizando el método de la selección de la ruleta, encogiendo la base de cromosomas sobre el valor de la función, y asignando a los cromosomas una distribución de probabilidad a favor de los buenos cromosomas, y con ello obtener una mejor oportunidad de generar una siguiente generación buena. Considerando los factores en la evaluación de la programación; la tardanza, la prontitud, los tiempos de utilización y la variable de costos es optimizada la secuencia para las máquinas en paralelo. Además, en la programación de los trabajos en las plantas de manufactura, se utilizan métodos de secuenciación heurísticos, los que se basan en reglas y métodos adaptativos. Los heurísticos basados en reglas se han realizado dependiendo de los tipos de ordenamiento y los tiempos de carga de las maquinas, con lo cual las reglas que más frecuentemente se utilizan para configuraciones con una maquina, como lo muestra la literatura [37] al secuenciar a partir de Earliest Due Date (EDD), y [38] con un Shortest Processing Time (SPT). Para extender estas reglas para maquinas en paralelo necesitaron integrar las características de los trabajos asignados a las maquinas. Por otra parte se han hecho desarrollos mediante los heurísticos adaptativos en estos desarrollo se encuentran autores como: Aarts y Korst, [1989], Van Laarhoven y Aarts, [1987], Palmer, [1996], utilizando algoritmos de enfriamiento simulado, otros utilizan búsqueda Tabú entre ellos, Brandimarte y Calderini [1995], Ben Daya y Al Fawzan, [1998], Armentano y Ronconi, [1999], además de algoritmos Hill Climbing se encuentran Bonet y Geffner, [1999] y en secuenciación con algoritmos genéticos se encuentran autores como: Goldberg, [1989], Gen y Cheng, [1997], [Liu y Tang, 1999], [Lee et al., 2002], [Kacem, 2003]. Los cuales se han acercado a la solución óptima a través de la interacción de parámetros ajustados para obtener una solución subóptima. Una de las características de los algoritmos adaptativos es que todos ellos necesitan alguna evaluación o juzgamiento de que tan buena es la solución subóptima. Ellos pueden luego modificar la configuración de probabilidad existente generando soluciones muy similares, y continuar la búsqueda de la solución óptima hasta que resulte satisfactoria [39]. D. Enfoque de solución utilizando Algoritmos Genéticos Recientemente los algoritmos genéticos han sido adoptados para resolver el problema de Flexible Job Shop Scheduling (FJSSP), generando un incremento en el número de estudios desarrollados como lo muestran las publicaciones, por que los algoritmos genéticos tienen unos atributos que permiten desarrollar adecuadamente la tarea de la secuenciación, entonces, los GA tienen cinco atributos básicos: representación genética de soluciones para los problemas; el camino para crear la población inicial; operadores genéticos para cambiar la población genética; función de evaluación y valor de los parámetros; estos parámetros han permitido que los investigadores desarrollen teorías a través de estos elementos y mejoren los acercamientos desde el modelo simple de algoritmo genético para optimizar la secuencia de operaciones mediante alguna medida de cumplimiento en la producción.7 Secuenciación de operaciones para configuraciones de planta tipo flexible Job Shop: Estado del arte Correa, Rodríguez y Londoño 157 Algunos de los trabajos más relevantes los han desarrollado Lehmann y otros [1999] [40], ellos proponen un algoritmo genético para el FJSSP, donde dividen la representación de cromosomas en dos partes, la primera define la política de enrute, y la segunda los operadores de secuencia sobre la máquina; según ellos, la principal ventaja de su algoritmo es que puede resolver una larga clase de problemas, incluyendo el JSSP; las pruebas iniciales del algoritmo muestran que encontraron una alta calidad en la secuenciación para los problemas de una talla realista y entonces consideran que es una prometedora aplicación practica. El algoritmo presentado sólo considera el criterio del Makespan y dentro de ese mismo algoritmo pueden considerar otro criterio como es el peso del flujo de tiempo total o flujo de tiempo total o la tardanza total; lo que ellos consideraron como debería ser un trabajo futuro en el desarrollo obtenido. Kacem I, Hammadi S, Borne P., [2002], Jia HZ, Nee AYC, Fuh JYH, Zhang YF., [2003] y Tay JC y Ho NB [2004], todos ellos han utilizado enfoques integrados, cada uno con diferentes esquemas de representación, generación de población inicial, selección de cromosomas y estrategias de generación de poblaciones. [41] Jeong y otros [2002], evalúan las alternativas de procesos en la planta para trabajos con restricciones de precedencia en la planeación avanzada y secuenciando sistemas utilizando algoritmos genéticos, incluyendo en la función de evaluación parámetros de intervalos de entrega de los trabajos y costos de salvamento de outsourcing. Kacem I, y otros [2002] [42], utiliza la representación de cromosomas que combina la información de secuencia y de enrute, y desarrolla un planteamiento por localización para encontrar una asignación inicial prometedora. Las reglas de despacho son luego utilizadas para la secuencia de las operaciones. Una vez que la población inicial es encontrada, ellos aplican operadores de mutación y de cruce juntando y modificando la asignación y la secuencia, produciendo mejores individuos para cada generación Kacem, [2003] [43] utiliza un algoritmo genético con operadores de preservación de precedencia para minimizar el makespan y los tiempos de carga de las maquinas. Ese mismo año este mismo autor presenta, un algoritmo genético para el peor caso de análisis [44], donde propone un método heurístico para solucionar el problema, mediante operadores de preservación de precedencia, para una optimización multiobjetivo, además usando un método de localización en el primer paso, en el segundo paso un algoritmo evolucionario para encontrar la solución inicial, tomando en cuenta todas las restricciones y especificaciones del problema, en este proceso muchos operadores son asignados, concernientes a dos componentes del problema: La asignación y la secuencia. Algunas pruebas de simulación realizadas en esta investigación muestran que, la pequeña distancia entre los límites inferiores y el valor del criterio obtenido por la solución generada, es generalmente satisfactoria y promisoria, en su trabajo concluyen que sus resultados obtenidos demuestran la buena calidad de los diferentes límites y la adecuación del método evolucionario, al problema. Sankar y otros, [2003] [45] adopta un algoritmo genético para minimizar el costo total de penalización y maximizar la utilización de las maquinas para un sistema de manufactura flexible. Tay J.C y Ho N.B., [2004] [46], propone una metodología eficiente llamada GENACE basada en la cultura de arquitectura evolucionaría para resolver el FJSSP con recirculación, muestran como un CDR (Composición de reglas de despacho) son usadas para solucionar el FJSSP con recirculación por ellos mismos y generando un mecanismo de inicialización GENACE. Ellos adoptaron una arquitectura cultural evolucionaria, manteniendo el conocimiento del esquema y la localización de los recursos aprendidos sobre cada generación. La creencia de la influencia de los espacios de mutación y selección sobre una representación factible del cromosoma. Los resultados experimentales que muestran de GENACE obtienen mejores resultados para los limites superiores para 11 de 13 problemas benchmark con una mejora de los factores entre un 2 y 48 por ciento cuando los resultados son comparados con los estudios realizados por Kacem y Brandimarte y el uso de CDR solamente. Tanev, y otros [2004] [47], proponen un algoritmo hibrido evolucionario, el cual combina las prioridades de reglas de despacho (Priority Dispaching Rules) PDRs con algoritmos genéticos; con las reglas de despacho determinan cual es el orden a ejecutar de la próxima tarea, desde la lista de trabajos no secuenciados. Comparando las otras alternativas, las PDRs ofrecen la ventaja de la simplicidad, generando un bajo costo computacional y pudiendo aplicar a los problemas reales que se presentan en las plantas de maquinas de inyección de plástico (factories of plastic injection machines FPIM) que dan lugar a la configuración de planta tipo Flexible Job Shop FJSSP, considerando que las empresas tienen recursos (maquinas, moldes, etc.) que son impredecibles, el algoritmo influye de forma importante en el éxito de la secuenciación. El algoritmo planteado no trata de predecir el futuro sino que toma decisiones según el presente, con lo cual localiza los procesos durante la secuenciación y consecuentemente reduce el costo computacional de un algoritmo, al descomponer las tareas de la programación de los trabajos en agentes autónomos donde cada agente es una maquina de la planta. Sin embargo, el procedimiento de PDR tiene elementos no ventajosos como: Su corta visión, utilizando un óptimo local que está lejos de un óptimo global, ningún PDR simple puede aplicarse para posibles casos de secuenciación de FPIM. Esto se debe a que se necesitaría un desarrollo empírico que involucre PDRs como combinación de ellos, que se podría en instancia concreta secuenciación de FPIM8 158 Revista Avances en Sistemas e Informática, Vol. 5 No. 3, Diciembre de 2008, Medellín, ISSN Por lo anterior, se observa que los PDRs tienen desventajas que deterioran una solución que se acerque a un óptimo global, de forma que la generación de una combinación de un PDRs y de un algoritmo genético (GA) utiliza las ventajas de ambos procedimientos dando lugar a un procedimiento de mejor calidad. Borne y otros (2004) [48], desarrollaron una aplicación de algoritmos evolucionarios para el FJSSP con restricciones de problemas del mundo real, ellos demostraron que escogiendo una conveniente representación del cromosoma (Codificación en paralelo) que es un paso importante según ellos, para encontrar mejores resultados, desarrollaron un operador genético adaptado para cada representación (Cambiar y asignar la mutación para el PME (Parallel machina encoding) y controlar la mutación para el PJE (Parallel Jobs encoding)) y un eficiente creación de una población inicial, mediante una combinación de algunos métodos para PME y un aleatorio acercamiento para el PJE porque todas las restricciones son integradas en la sintaxis del cromosoma. Una conveniente selección de los parámetros del genético para una aplicación de los algoritmos evolucionarios. Los parámetros (Tasa de cruce, tasa de mutación, tamaño de población, etc) son usualmente seleccionados heuristicamente. En este trabajo no hay líneas exactas de estrategia a ser adoptadas para los diferentes problemas. En este trabajo aplican claramente, un tamaño de población fija con diferentes valores de tasa para el cruce y mutación, ellos encontraron que la mutación controlada reduce la selección hecha a ciegas. Sus resultados de simulación mostraron las representaciones paralelas propuestas son más convenientes para el FJSSP, confirmando la efectividad de los acercamientos propuestos. Gen y otros [2005] [49], ellos proponen una nueva base de multiestado de representación para simplificar el cromosoma, usando este método los acercamientos desarrollados para los cruces y la mutación pueden ser aplicados, la importancia de este se desarrollo se da, porque la efectividad de la solución es principalmente afectada por la complejidad de la representación del cromosoma; el algoritmo desarrollado fue diseñado para tres criterios de optimización incluyendo el Makespan, carga de trabajo total para cada una de las máquinas y la máxima carga de trabajo para todas las máquinas, mediante pruebas numéricas experimentales ellos demostraron la eficiencia de este acercamiento a la solución del FJSSP. Chan y otros [50], también exploran un algoritmo genético, basado en el acercamiento a los recursos restrictivos de asignación de operaciones a máquina, que a su vez puede resolver interactivamente el problema genérico del JSSP, es decir, el problema resuelto mediante este esquema de acercamiento es RCFJSSP. En este estudio el desarrollo es llamado IGA y muestra las mejoras a este ambiente y al ambiente de las múltiples máquinas bajo recursos restrictivos, así, demostraron que los conflictos entre el Makespan y MIC (Machina idle cost) pueden ser solucionados bajo diferentes niveles de recurso RL; de igual forma, este acercamiento puede ser fácilmente modificado a tipo II FJSSP con múltiples máquinas no idénticas bajo recursos restrictivos. Gen y otros, [2007] [51], realizan la programación del problema para planta tipo FJSSP teniendo en cuenta tres objetivos: minimizar el makespan, minimizar el máximo tiempo de carga de maquina y minimizar el tiempo total de tiempo de carga, desarrollando un algoritmo hibrido genético (hga) para el problema. Basados en la habilidad de cruce y mutación de los vectores, mejorando la población y la búsqueda por medio de una descendencia variable de vecindad (VND), desarrollando un método eficiente para encontrar intervalos de tiempo asignables para la eliminación de operaciones, basados en el concepto de prontitud y tardanza de un tiempo presentado. El movimiento óptimo local de una operación es mejorado mediante el movimiento de dos operaciones simultáneas. Como se ha descrito, en los trabajos desarrollados se ha encontrado que los autores en las diferentes configuraciones de planta especialmente este tipo de configuración, consideran restricciones, ya que una programación ideal ocasionaría que la producción y el Scheduling no se ejecuten como se plantea [52]; existen varios tipos de restricciones en la planta, los cuales se definen en dos tipos fijos y No fijos. Las restricciones asociadas a los tipos de restricciones fijos, son aquellos que empiezan y terminan en un tiempo definido; mientras que en las restricciones No fijas, no existen tiempos definidos de comienzo y fin de la parada, periodo en el cual las máquinas no se encuentran disponibles, estos tiempos deben ser determinados durante la secuencia de producción. En la producción se presentan mantenimientos preventivos ejecutados una vez, en un intervalo de tiempo. En algunos horizontes de programación no hay actividades de mantenimiento. Además en algunos periodos se presentan una o varias actividades de mantenimiento que deben ser programadas en las máquinas, afectando de forma directa la programación de las mismas. El manteniendo preventivo impone restricciones no fijas de disponibilidad sobre las máquinas y generalmente el tiempo de inicio del mantenimiento preventivo es flexible. El problema de restricciones no fijas para un Flexible Job Shop Scheduling (FJSSP nfa), es decir, cada máquina está sujeta a un número arbitrario de tareas asociadas a mantenimiento preventivo PM, para lo cual [53] realizan un algoritmo genético hibrido (hga), dado que en el algoritmo genético, un cromosoma únicamente contiene información parcial de la solución candidata y la información ignorada es eliminada para la optimización de un método heurístico en el proceso de decodificación. Contrario a los algoritmos genéticos, los operadores de cruce (crossover) y de mutación (mutation) del hga propuesto son implementados en el espacio del fenotipo, preferiblemente, que al espacio del genotipo de acuerdo al incremento de heredabilidad de un hga. Dos tipos de vecindades las cuales solamente contienen soluciones que tienen posibilidades de mejorar la solución inicial definida para9 Secuenciación de operaciones para configuraciones de planta tipo flexible Job Shop: Estado del arte Correa, Rodríguez y Londoño 159 el FJSP nfa, basado en el concepto de ruta crítica. Un procedimiento de búsqueda local que trabaja sobre las dos vecindades es luego hibrizado con el algoritmo genético de acuerdo al incremento de la habilidad de búsqueda. Por lo cual generan dos vectores v1(r) y v2(r), donde v1(r) es el vector de asignación de máquinas, y v2(r) es el vector operador de secuencia, y al programar se realizan cambios de las operaciones hacia la izquierda para compactar lo más posible la secuenciación. Un cambio es llamado cambio global izquierdo (global left shift) si alguna operación puede empezar más temprano en el tiempo sin demorar las otras operaciones aun si el cambio hecho cambia la secuencia de las operaciones. Un programa es semiactivo si no hay cambios locales a la izquierda y por tanto un programa es activo si no hay cambio global a la izquierda. En este trabajo, utilizan la prioridad basada en la decodificación, donde cada operación busca el intervalo de tiempo disponible para implementarlo en su máquina asignada en orden a la representación dada por el vector operador de secuencia. Estos mismos autores en el 2008, [54] desarrollaron una extensión del trabajo anterior con tres criterios de optimización: Makespan, Minimización de la máxima carga de máquina y la minimización total de la carga. Este acercamiento fue probado computacionalmente con 181 problemas benchmark mostrando el cumplimiento de ese acercamiento, porque muestran que la misma solución es obtenida por la combinación de esfuerzos de trabajos previos, además, encuentran 38 nuevas mejores soluciones. Otros autores han estudiado como G. Vilcot y J. Billaut, [2008], el desempeño de las diferentes metodologías para problemas particulares, para lo cual [55], comparan un algoritmo Genético con otro de búsqueda tabú, llevando a colación los problemas que se presentan en las empresas de impresión y en la industria de encartonado. El objetivo es minimizar el makespan y la máxima tardanza, encontrando una aproximación de la frontera de Pareto. Proponen un algoritmo genético rápido y elitista basados en NGSA II para resolver el problema. La población inicial es generada aleatoriamente o parcialmente y ambos algoritmos genético y de búsqueda tabú son probados sobre problemas benchmark, para un análisis y comparación computacional para configuraciones de planta Flexible Job Shop obtenidos con ambos métodos. Pezzella y otros, [2008] [56], toman inicialmente como base de su estudio los desarrollos realizados por Kacem [2002] entonces, ellos desarrollan un algoritmo genético para Flexible Job Shop, en el cual analizan algoritmos que no han sido efectivos para resolver el FJSSP para pequeñas instancias. De hecho los métodos exactos basados en representaciones disyuntivas de los problemas han sido desarrolladas, pero estos métodos no son aplicables para instancias con mas de 20 trabajos y 10 maquinas, Pinedo M., [2002], por lo cual realizan su desarrollo en algoritmos heurísticos. Desde los estudios anteriores se sabe que ningún algoritmo conocido para FJSSP produce soluciones con una garantía en distancia desde la solución óptima; para mejorar su método, además conducen los resultados experimentales en ejemplos completando el trabajo con un estudio computacional extensivo, para conseguir los anteriores resultados los investigadores recurrieron a una integración de diferentes estrategias para generar la población inicial y las estrategias para reproducción de nuevos individuos Ho y otros [2008] [57], desarrollaron un estudio para el FJSSP multi objetivo usando reglas de despacho descubiertas a través de programas genéticos, muestran la evaluación y empleo de parámetros y operadores apropiados para construir reglas de despacho usando genéticos, con un fin hacia la escalabilidad y flexibilidad, donde casi todas esas reglas de despacho son basadas en la experiencia del programador, la generación de estas reglas de despacho se realizaron a través de framework que soluciona efectivamente el JSSP. Cinco reglas de despacho fueron generadas por el programa genético, estas reglas fueron basadas en combinación de parámetros como: tiempos de procesamiento, fecha prevista, fecha de liberación, fecha común, número de operaciones y promedio total de tiempo de procesamiento de cada trabajo. Muchas simulaciones se realizaron para obtener la evaluación de los criterios de optimización de las cinco reglas, variando los grados de flexibilidad del problema; otras cinco populares reglas de despacho de la literatura fueron evaluadas y usadas en la simulación de los problemas benchmark. Los resultados experimentales de esta investigación mostraron que las populares reglas de despacho validadas en la literatura no cumplen satisfactoriamente con todos los criterios, mientras que la combinación de parámetros contribuye eficazmente con las reglas. Encontraron que la EDD es significativamente mejor que otras reglas de la literatura minimizando la tardanza, el flujo de tiempo y el porcentaje de trabajos tardíos mientras que es pobre la minimización del Makespan. Sin embargo, las reglas generadas por el programa genético, cumplieron con los criterios de optimización por encima de la EDD, mostrando esto que, la aplicación desarrollada es efectiva en la construcción de reglas de despacho para solucionar el multiobjetivo FJSSP. Ellos muestran estadísticamente que sus reglas de despacho son suficientes y bien diseñadas, realizando un análisis de varianza (ANOVA). Finalmente, las reglas de despacho desarrolladas pueden ser aplicadas directamente en la práctica sin modificaciones. VI. CONCLUSIONES Y PERSPECTIVAS Los procesos de manufactura en la actualidad se han vuelto más complejos por lo que, la secuencia de operaciones se ha convertido en un tema importante para mejorar la competitividad de las compañías, el problema del Flexible Job Shop Scheduling se ajusta de manera adecuada a los problemas reales de casi10 160 Revista Avances en Sistemas e Informática, Vol. 5 No. 3, Diciembre de 2008, Medellín, ISSN todos los tipos de manufactura y en todos los sectores. Entonces, dada la importancia de los problemas prácticos del tipo planeación scheduling y a su gran dificultad de obtener soluciones por ser del tipo NP Hard, es de relevancia el dirigir nuestra mirada a los acercamientos a través de meta heurísticas, pues con una investigación más profunda se puede encontrar un camino para una importante simplificación en el trato de estos problemas. De acuerdo a la búsqueda realizada en la literatura encontramos que, los algoritmos genéticos son los más recurrentes a la hora de solucionar el problema genérico del JSSP. Mediante el enfoque de algoritmos genéticos se logra encontrar una alternativa para la evaluación de un problema Flexible Job Shop Scheduling, de acuerdo a la literatura, también encontramos que por medio de este enfoque, se puede incrementar la eficiencia algorítmica en cuanto a complejidad y encontrar buenas soluciones, en cuanto a la asignación y la secuencia. Dentro de los algoritmos genéticos hay elementos que han sido poco estudiados en la literatura del FJSSP, pero que han sido desarrollados por autores en el problema del JSSP; que son los elementos de la parametrización del algoritmo de solución para el problema, las razones para implementar la parametrización en un modelo es poder obtener numéricamente y de manera significativa, algunos de los efectos, dados por elementos como: el tipo de cruce en la calidad de solución para un problema dado y otro podría ser, la influencia que tiene el tamaño de la población en la calidad de dicha solución. La pregunta cuál es el tamaño idóneo para una población? parece no tener una respuesta clara, dado que intuitivamente se puede pensar que las poblaciones pequeñas corren el riesgo de no cubrir adecuadamente el espacio de búsqueda, mientras que trabajar con poblaciones de gran tamaño puede acarrear problemas asociados al gran costo computacional, por tanto un aspecto importante para desarrollar en trabajos futuros, es la parametrización del enfoque de solución para el FJSSP mediante algoritmos genéticos. AGRADECIMIENTOS Los autores quieren presentar los más sinceros agradecimientos a la Dirección de Investigación de la Universidad Nacional de Colombia, Sede Medellin (DIME) por la financiación del proyecto de investigación titulado: Evaluación de la metodología de algoritmos genéticos con diseño experimental para la programación de plantas con configuración tipo Job Shop con código No del cual este es uno de sus resultados. REFERENCIAS [1] Dante Boiteux, O., Estado del arte sobre planificación agregada de la producción. Tesis doctoral, Universidad Politécnica de Cataluña, Instituto de la organización y sistemas industriales: Barcelona. [2] Pinedo, M., Scheduling: theory, algorithms and systems. Englewood cliffs, NJ: Prentice Hall. [3] Londoño, M., Reprogramación de ordenes de trabajo en el modelo básico, con una fecha de entrega común para minimizar la penalización por prontitud / tardanza, basado en métodos heurísticos. Tesis de pregrado, Universidad Nacional Sede Medellín. [4] Op Cit. Pinedo M., [2] [5] Lawler, E.L, Lenstra, J.K.,. Rinnooy Kan, A.H.G. y Shmoys, D.B., Secuencing and scheduling: Algorithms and complexity. Handbooks in Operations Research and Management Science, North Holland. [6] Alcaide López de Pablo, D., Problemas de planificación y secuenciación determinística: modelización y técnicas de resolución. Curso de ciencia y tecnología. Universidad de la Laguna. [7] Op Cit. Alcaide López de Pablo, D. [6] [8] Lawyer, E.L., Combinatorial Optimization: networks and matroids, Holt, Rinehart and Winston, New York. [9] Karp, R.M., Reducibility among combinatorial problems. En: Complexity of computer computations, Plenum Press, New York, pp [10] Garey, M.R. y Johnson, D.S., Computers and intractability: a guide of the theory of NP Completeness, Freeman. [11] Álvarez de los Mozos, E. y Zubillaga, F. J., Análisis comparativo de métodos de secuenciación para la programación dinámica de operaciones. En: VIII Congreso de ingeniería de organización, Léganes. [12] Rossi, A. y Dini, G., Dynamic Scheduling of FMS using a Real Time Genetic Algorithm, International Journal of Production Research. Vol.38 (1), pp [13] Chen H., Ihlow J. y Lehmann C., A genetic algorithm for Flexible Job Shop Scheduling. En: Proceedings of the IEEE Transactions on Neural Networks, International Conference on Robotics & automation. Detroit, Michigan. [14] Jansen K., Mastrolilli M. y Solis Oba, R., 2005 Approximation algorithms for Flexible Job Shop Problems. En: International Journal of Foundations of Computer Science. Vol 16, pp [15] Op Cit. Jansen K., Mastrolilli, M. y Solis Oba, R [14] [16] Hall, L., Hoogeveen, J., Hurkens, C., Lenstra, J., Sevastianov, S., Shmoys, D. y Williamson, D., Short shop schedules. En: Operation Research, Vol. 45, pp [17] Gonzalez, T. y Sahni, S., Flowshop and Job Shop schedules: complexity and approximation. En: Operation research. Vol. 26, pp [18] Baker, K. R., Introduction to secuencing and scheduling. John Wiley and Sons, New York. [19] Nakano, R. y Yamada, T., Conventional Genetic Algorithm for Job Shop Problems, in Kenneth, M. K. y Booker, L. B. En: Proceedings of the 4th International Conference on Genetic Algorithms and their Applications, San Diego, USA, pp [20] Norman, B. A. y Bean, J., Random Keys Genetic Algorithm for Job Shop Scheduling. En: Engineering Design and Automation. Vol. 3, pp [21] Kumar, N.S. y Srinivasan, G., A genetic algorithm for Job Shop Scheduling A case study. En: Computer in industry. Vol. 31, pp [22] Azarmi, N., Hughest, JG:, Song, Y. y Voudourist, C., A genetic algorithm with an incomplete representation for de Job Shop Scheduling Problems. En: Informe de investigación, University of Ulster at Jordanstown. Intelligent System Research Group. [23] Eikelder, Ten., H.M.M., Moraglio, A. y Tadei, I., Genetic Local Search for Job Shop Scheduling Problem. Technical Report CSM 435 ISSN [24] Herrera, F. y Pérez, M. E., Algoritmos genéticos multimodales: Un estudio sobre la parametrización del método clearing aplicado al problema Job shop. Reporte de investigación, Universidad de Valladolid, TIN C [25] Engin, O., Figlali, Al., Figlali, N. y Özcale, C., Investigation of ant system parameter interactions by using design of experiments for Job Shop Scheduling problems; Computers & Industrial Engineering, pp [26] Dauzère Pérès, S., Essafi, I. y Mati, Y, A genetic local search algorithm for minimizing total weight tardiness in the Job Shop scheduling problem.11 Secuenciación de operaciones para configuraciones de planta tipo flexible Job Shop: Estado del arte Correa, Rodríguez y Londoño 161 Computer & Operation research, Vol.35, pp [27] Billaut J. C. y Vilcot G., A tabu search and genetic algorithm for solving a bicriteria Job Shop Scheduling problem, En: Discrete optimization, European Journal of Operational Research, Vol. 190, pp [28] Ciaschetti, G., Morganti, G., y Pezzella, F., A genetic algorithm for the Flexible Job shop Scheduling Problem. En: Computers & Operations Research, Vol. 35, pp [29] Op Cit. Ciaschetti, G., Morganti, G., y Pezzella, F. [28] [30] Gambardella, L.M. y Mastrolilli, M., Effective neighborhood functions for the flexible job shop problem. Journal of Scheduling Vol.3 pp [31] Op Cit. Billaut Jean Charles y Vilcot Geoffrey, [27]. [32] Paulli J., A hierarchical approach for the FMS scheduling problem. En: European Journal of Operational Research Vol.86, pp [33] Dauzére Pérés, S. y Paulli, J., An integrated approach for modeling and solving the general multiprocessor job shop scheduling problem using tabu search. En: Annals of Operations Research Vol.70, pp [34] Kacem, I., Hammadi, S. y Borne, P., Pareto optimality approach for flexible job shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic. En: Mathematics and Computers Simulation Vol. 60, pp [35] Álvarez Valdez, R., Fuertes, A., Giménez, R., Ramos, G. y Tmarit, J.M., A heuristic to Schedule flexible job shop in glass factory. En: European Journal of Operational Research Vol.165, pp [36] Chichang, Jou., A genetic algorithm with sub indexed partitioning genes and its application to production scheduling of parallel machines. En: Computers & Inductrial Engineering, Vol.48, pp [37] Cheng, T. C. E., y Sin, C. C. S. (1990). A state of the art review of parallel machine scheduling research. En: European Journal of Operational Research, Vol. 47(3), p [38] Cheng, T. C. E. y Chen, Z. L., Parallel machine scheduling problem with earliness and tardiness penalties. En: Journal of the Operational Research Society, Vol. 45, pp [39] Op. Cit. Chen H., Ihlow J. y Lehmann C [13] [41] Jeong, C. S., Lee, Y. H. y Moon, C., Advanced planning and scheduling with outsourcing in manufacturing supply chain. En: Computers and Industrial Engineering, Vol.43(2), pp [42] Borne, P., Hammad,i S, y Kacem, I., 2002 Approach by localization and multiobjetive evolutionary optimization for flexible job shop scheduling problems. En: IEEE Transactions on Systems, Man, and Cybernetics, Part C. Vol.32 (1), pp [43] Kacem, I., Genetic algorithm for the flexible job shop scheduling problem. Proceedings of IEEE international conference on systems, man and cybernetics. Vol. 4, pp [44] Kacem, I., Scheduling Flexible Job Shop: A worst case análisis and an evolutionary algorithm. En: International Journal of Computational Intelligence and Applications. Vol. 3, No. 4, pp [45] Ponnanbalam, S. G., Rajendran, C y Sankar, A. S., A multiobjetive genetic algorithm for scheduling a flexible manufacturing system. En: International of Advanced Manufacturing Technology, Vol. 22(3), pp [46] Ho, N.B. y Tay, J.C., GENACE: An effective cultural Algorithm for solving the flexible job shop schedules, En: Lecture notes in IEEE, pp [47] Tanev, I. T., Takashi, U. y Yoshihauru M., Hybrid evolutionary algorithm based real world flexible job shop scheduling problem: application service provider approach. En: Applied Soft Computing, Vol.5, pp [48] Borne, P., Hammadi, S. y Mesghouni, K., Evolutionary algorithms for Job Shop Scheduling. International Journal Application Mathematics computers Science. Vol.14 (1), pp [49] Gen, M. y Zhang, H., Multistage based genetic algorithm for flexible Job Shop Scheduling Problem. En: Complexity International. Vol. 11, pp [50] Chan, F.T.S., Chan, L.Y. y Wong, T.C., Flexible Job Shop Scheduling Problem under resource constraints. En: International Journal of Production Research. Preview article, pp [51] Gao, J., Gen, M. y Sun, L., Scheduling jobs and maintenances in flexible job shop with a hybrid genetic algorithm. En: Journal Intelligent Manufacture Vol.17, pp [52] Schmidt G., Scheduling with limited machine availability. En: European Journal Of Operational Research, Vol.121, pp [53] Gao, J., Gen, M., Sun, L. y Zhao, X., A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible Job Shop Scheduling Problems. En: Computers & Operations Research Vol. 53, pp [54] Gao, J.., Gen, M. y Sun, L., A hybrid genetic and variable neighborhood descent algorithm for Flexible Job Shop Scheduling Problems. En: Computers & Operations Research Vol. 35, pp [55] Op. cit. Billaut J. C. y Vilcot G. [27] [56] Op Cit. Ciaschetti, G., Morganti, G., y Pezzella, F. [28] [57] Ho, N. B. y Tay, J. C., Evolving dispatching rules using genetic programming for solving multi objective flexible job shop problems. En: Computers & Industrial Engineering. Vol 54, pp12 162 Revista Avances en Sistemas e Informática, Vol. 5 No. 3, Diciembre de 2008, Medellín, ISSN Mostrar más
Capítulo VI MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING 6.1. HEURÍSTICAS CONVENCIONALES El problema de job shop scheduling (JSSP) es un problema muy importante [69]; está entre los problemas de optimización Más detalles Elkin Rodríguez Velásquez Profesor Escuela de Ingeniería de la Organización, Universidad Nacional de Colombia, Medellín, erodrigu@unal.edu.
EVALUACIÓN DE LA METDLGÍA DE ALGRITMS GENÉTICS CN DISEÑ EXPERIMENTAL PARA PRGRAMACIÓN DE PLANTAS CN CNFIGURACIÓN PRDUCTIVA TIP JB SHP FLEXIBLE. Alexander A. Correa Espinal Profesor Escuela de Ingeniería Más detalles Algoritmos Genéticos
Algoritmos Genéticos. Miguel Cárdenas Montes, Antonio Gómez Iglesias Centro de Investigaciones Energéticas Medioambientales y Tecnológicas, Madrid, Spain miguel.cardenas@ciemat.es 15-19 de Octubre de 2011 Más detalles Algoritmos Genéticos Y
Algoritmos Genéticos Y Optimización n Heurística Dr. Adrian Will Grupo de Aplicaciones de Inteligencia Artificial Universidad Nacional de Tucumán awill@herrera.unt.edu.ar Operadores de Mutación El operador Más detalles Introducción a los Algoritmos Genéticos. Tomás Arredondo Vidal 17/4/09
Introducción a los Algoritmos Genéticos Tomás Arredondo Vidal 17/4/09 Esta charla trata de lo siguiente: Introducción a algunos aspectos de los algoritmos genéticos. Introducción a algunas aplicaciones Más detalles Scheduling Problem. Cuándo y dónde debo hacer cada trabajo?
Scheduling Problem Cuándo y dónde debo hacer cada trabajo? Ejemplos de problemas de asignación de recursos Fabricación de varios tipos de productos Asignación de turnos de trabajo Inversión financiera Más detalles Algoritmos genéticos como métodos de aproximación analítica y búsqueda de óptimos locales
Algoritmos genéticos como métodos de aproximación analítica y búsqueda de óptimos locales Jorge Salas Chacón A03804 Rubén Jiménez Goñi A93212 Juan Camilo Carrillo Casas A91369 Marco Vinicio Artavia Quesada Más detalles Temario III Algoritmos Combinatorios y Metaheurísticas
Temario III Algoritmos Combinatorios y Metaheurísticas Verificación y Validación de Software UNCo 1 Contenidos Combinación de Datos de Test Algoritmos Combinatorios Metaheurísticas Búsqueda Tabú Algoritmos Más detalles Métodos evolutivos de Optimización. Prof. Cesar de Prada Dpto. Ingeneiria de Sitemas y Automática Universidad de Valladolid
Métodos evolutivos de Optimización Prof. Cesar de Prada Dpto. Ingeneiria de Sitemas y Automática Universidad de Valladolid Indice Introducción Método de Montecarlo Algoritmos genéticos Tabú Search Simulated Más detalles Desarrollo de algoritmos genéticos, de recocido simulado e híbridos para la planificación de un taller flexible
X Congreso de Ingeniería de Organización Valencia, 7 y 8 de septiembre de 2006 Desarrollo de algoritmos genéticos, de recocido simulado e híbridos para la planificación de un taller flexible Sara Lumbreras Más detalles ALGORITMOS GENÉTICOS PARA LA RESOLUCIÓN DE PROBLEMAS PRÁCTICOS DE SCHEDULING
ALGORITMOS GENÉTICOS PARA LA RESOLUCIÓN DE PROBLEMAS PRÁCTICOS DE SCHEDULING Alberto Cortés, Víctor Jacobo, Lázaro Morales, Armando Ortiz Unidad de Investigación y Asistencia Técnica en Materiales, Universidad Más detalles Jhoan Sebastián Cadavid Jaramillo Ingeniero Industrial, Universidad Nacional de Colombia, jscadav0@unal.edu.co RESUMEN
PROBLEMA DE PROGRAMACIÓN DE PRODUCCIÓN ABIERTA CON CARACTERÍSTICAS DE MÁQUINAS MÓVILES DEDICADAS Y CON TIEMPOS DE PREPARACIÓN DEPENDIENTES DE LA SECUENCIA ENTRE ETAPAS Alexander Alberto Correa Espinal Más detalles MODELOS DE PLANIFICACIÓN
MODELOS DE PLANIFICACIÓN Santiago de Compostela, Octubre 2006 1 s jk C max P Jm prmt L max NP Rm tree C j Algoritmos wj U j Uj Calendarios Fm prec w j U j Práctica CONTENIDO. Contents 1 Descripción del Más detalles Un algoritmo genético para el problema de Job Shop Flexible
Ingeniare. Revista chilena de ingeniería, vol. 19 Nº 1, 2011, pp. 53-61 Un algoritmo genético para el problema de Job Shop Flexible A genetic algorithm for the Flexible Job Shop problem Rosa Medina Durán Más detalles Universidad Autónoma de Nuevo León
Universidad Autónoma de Nuevo León Facultad de Ingeniería Mecánica y Eléctrica División de Estudios de Posgrado Secuenciación en máquinas paralelas no relacionadas con tiempos de preparación y tareas de Más detalles FORMULACIÓN DE UN ALGORITMO GENÉTICO PARA EL PROBLEMA DE PROGRAMACIÓN DE ÓRDENES DE TRABAJO DE UNA EMPRESA DE ARTES GRÁFICAS
FORMULACIÓN DE UN ALGORITMO GENÉTICO PARA EL PROBLEMA DE PROGRAMACIÓN DE ÓRDENES DE TRABAJO DE UNA EMPRESA DE ARTES GRÁFICAS PROYECTO DE GRADO Javier mauricio gamboa salgado Código: 544004 John alexander Más detalles Un algoritmo genético híbrido para resolver el EternityII. Rico, Martin; Ros, Rodrigo Directora: Prof. Dra. Irene Loiseau
Un algoritmo genético híbrido para resolver el EternityII Rico, Martin; Ros, Rodrigo Directora: Prof. Dra. Irene Loiseau Temas Temas Introducción Eternity II Historia Descripción Demo Metaheurísticas Algoritmos Más detalles Computación Evolutiva: Técnicas de Selección
Computación Evolutiva: Técnicas de Selección Dr. Gregorio Toscano Pulido Laboratorio de Tecnologías de Información Centro de Investigación y de Estudios Avanzados del IPN Cinvestav-Tamaulipas Dr. Gregorio Más detalles Estado del Arte del Job Shop Scheduling Problem
Estado del Arte del Job Shop Scheduling Problem Víctor Peña y Lillo Zumelzu Departamento de Informática, Universidad Técnica Federico Santa María Valparaíso, Chile vpena@inf.utfsm.cl 17 de mayo de 2006 Más detalles Algoritmos Genéticos. Introduccion a la Robótica Inteligente
Algoritmos Genéticos Introduccion a la Robótica Inteligente 7 Marzo 2014 (IRIN) AGs 7/03/2014 1 / 43 Índice 1 Introducción 2 Algoritmos Genéticos 3 Algunos Fundamentos Matemáticos 4 Conclusiones (IRIN) Más detalles &$3Ì78/2 $/*25,7026 (92/87,926 $9$1=$'26 3$5$ 763 6.1. INTRODUCCIÓN
&$3Ì78/2 6.1. INTRODUCCIÓN Los primeros avances para solucionar el TSP, por medio de Algoritmos Evolutivos han sido introducidos por Goldberg y Lingle en [68] y Grefenstette en [72]. En éste área muchos Más detalles UN ALGORITMO DE ESTIMACIÓN DE DISTRIBUCIONES PARA EL PROBLEMA DE SECUENCIAMIENTO EN CONFIGURACIÓN JOBSHOP FLEXIBLE
UN ALGORITMO DE ESTIMACIÓN DE DISTRIBUCIONES PARA EL PROBLEMA DE SECUENCIAMIENTO EN CONFIGURACIÓN JOBSHOP FLEXIBLE Ricardo Pérez Rodríguez & Arturo Hernández Aguirre Comunicación del CIMAT No I-15-01/23-01-2015 Más detalles IN4703 Gestión de Operaciones. Programación de Operaciones (Operations Scheduling)
IN4703 Gestión de Operaciones Programación de Operaciones (Operations Scheduling) Lineamientos de la Clase de Hoy Objetivos de la Programación de Operaciones Sistemas de Manufactura (Manufacturing Execution Más detalles Búsqueda Local. cbea (LSI-FIB-UPC) Inteligencia Artificial Curso 2011/2012 1 / 33
Introducción Búsqueda Local A veces el camino para llegar a la solución no nos importa, buscamos en el espacio de soluciones Queremos la mejor de entre las soluciones posibles alcanzable en un tiempo razonable Más detalles EXTENSIONES DE META-RAPS AL PROBLEMA DE MÁQUINAS PARALELAS NO RELACIONADAS
1 UNIVERSIDAD DEL BÍO-BÍO FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL EXTENSIONES DE META-RAPS AL PROBLEMA DE MÁQUINAS PARALELAS NO RELACIONADAS TESIS PARA OBTENER EL GRADO DE MAGÍSTER Más detalles Procesamiento Digital de Imágenes. Pablo Roncagliolo B. Nº 22. Algoritmos Genéticos. prb@2007 2
Procesamiento Digital de Imágenes Pablo Roncagliolo B. Nº 22 prb@2007 2 1 El núcleo de cada célula humana contiene una base de datos química. Esta base de datos contiene todas las instrucciones que la Más detalles Programación de tareas, un reto diario en la empresa
Programación de tareas, un reto diario en la empresa Pedro Sánchez Martín Ingeniero del ICAI (1993) y Doctor en Ingeniería Industrial por la UPCO (1998). Profesor del Departamento de Organización Industrial Más detalles Combinación de Algoritmos Evolutivos y Técnicas Heurísticas para Problemas de Scheduling
Combinación de Algoritmos Evolutivos y Técnicas Heurísticas para Problemas de Scheduling Ramiro Varela, Javier Blanco, Camino Rodríguez, Jorge Puente y César Alonso Centro de Inteligencia Artificial. Universidad Más detalles Una heurística para la asignación de máquinas a trabajos fijos
VIII Congreso de Ingeniería de Organización Leganés, 9 y 10 de septiembre de 2004 Una heurística para la asignación de máquinas a trabajos fijos José Manuel García Sánchez, Marcos Calle Suárez, Gabriel Más detalles Introducción a la Computación Evolutiva
Introducción a la Computación Evolutiva Sección de Computación CINVESTAV-IPN Av. IPN No. 2508 Col. San Pedro Zacatenco México, D.F. 07300 email: ccoello@cs.cinvestav.mx http: //delta.cs.cinvestav.mx/~ccoello Más detalles Un algoritmo evolutivo simple para el problema de asignación de tareas a procesadores
Un algoritmo evolutivo simple para el problema de asignación de tareas a procesadores Pablo Ezzatti CeCal, Facultad de Ingeniería Universidad de la República, Uruguay pezzatti@fing.edu.uy Sergio Nesmachnow Más detalles Desarrollo de un sistema capaz de optimizar rutas de entrega utilizando algoritmos genéticos
MT 6 Desarrollo de un sistema capaz de optimizar rutas de entrega utilizando algoritmos genéticos Rosario Baltazar 1 Judith Esquivel Vázquez 2 Andrea Rada 3 Claudia Díaz 4 Resumen Durante los últimos 15 Más detalles Comportamiento de los parámetros principales de un Algoritmo Genético para el Flow Shop Scheduling
Comportamiento de los parámetros principales de un Algoritmo Genético para el Flow Shop Scheduling Yunior César Fonseca Reyna Universidad de Granma E-mail: fonseca@udg.co.cu Temática: Inteligencia Artificial Más detalles Un algoritmo evolutivo simple para el problema de asignación de tareas a procesadores
Un algoritmo evolutivo simple para el problema de asignación de tareas a procesadores Pablo Ezzatti CeCal, Facultad de Ingeniería Universidad de la República, Uruguay pezzatti@fing.edu.uy Sergio Nesmachnow Más detalles Ingeniería Energética E-ISSN: 1815-5901 orestes@cipel.ispjae.edu.cu. Instituto Superior Politécnico José Antonio Echeverría. Cuba
Ingeniería Energética E-ISSN: 1815-5901 orestes@cipel.ispjae.edu.cu Instituto Superior Politécnico José Antonio Echeverría Cuba Carvajal- Pérez, Raúl Nicolás Un Algoritmo Genético Especializado en Planeamiento Más detalles Planificación detallada
Planificación detallada 77 Planificación detallada En las empresas que fabrican contra pedido la tarea de determinar la secuencia óptima de fabricación de artículos en un taller es complicada debido al Más detalles ALGORITMOS GENÉTICOS
Arranz de la Peña, Jorge Universidad Carlos III 100025106@alumnos.uc3m.es ALGORITMOS GENÉTICOS Parra Truyol, Antonio Universidad Carlos III 100023822@alumnos.uc3m.es En este documento se pretende analizar Más detalles [ Guía para recién llegados a los ALGORITMOS GENÉTICOS]
UVa Dpto. de Organización de Empresas Escuela de Ingenierías Industriales Elena Pérez www.eis.uva.es/elena [ Guía para recién llegados a los ALGORITMOS GENÉTICOS] El propósito de esta guía es dar soporte Más detalles Aplicación de la inteligencia artificial a la resolución del problema de asignación de estudiantes del departamento de PDI
Aplicación de la inteligencia artificial a la resolución del problema de asignación de estudiantes del departamento de PDI Ricardo Köller Jemio Departamento de Ciencias Exactas e Ingeniería, Universidad Más detalles METAHEURISTICAS Ideas, Mitos, Soluciones
METAHEURISTICAS Ideas, Mitos, Soluciones OPTIMIZACION COMBINATORIA Qué es un problema de optimización combinatoria? Cómo se modela matemáticamente un problema de optimización combinatoria? Minimizar (o Más detalles A L G O R I T M O S E VO L U T I VO S A P L I C A D O S A L A G E N E R AC I Ó N D E H O R A R I O S PA R A C O L E G I O
E S C U E L A P O L I T É C N I C A N A C I O N A L F A C U L T A D D E C I E N C I A S D E P A R T A M E N T O D E M A T E M Á T I C A S A L G O R I T M O S E VO L U T I VO S A P L I C A D O S A L A G Más detalles CAPÍTULO 1 INTRODUCCIÓN, HIPÓTESIS Y OBJETIVOS
CAPÍTULO 1 INTRODUCCIÓN, HIPÓTESIS Y OBJETIVOS 1 INTRODUCCIÓN 1.1 Justificación Esta investigación está motivada por el interés en lograr una mejor comprensión del papel que desempeña la creatividad dentro Más detalles ALGORITMOS EVOLUTIVOS AVANZADOS
UNIVERSIDAD NACIONAL DE LA PLATA FACULTAD DE INFORMÁTICA TESIS PARA LA MAESTRÍA EN AUTOMATIZACIÓN DE OFICINAS ALGORITMOS EVOLUTIVOS AVANZADOS COMO SOPORTE DEL PROCESO PRODUCTIVO Realizada por la Lic. Carolina Más detalles OPTIMIZACIÓN EN MANTENIMIENTO
OPTIMIZACIÓN EN MANTENIMIENTO Entrenamiento en técnicas avanzadas para optimizar el remplazo de componentes e inspección de equipos Driven by knowledge info@apsoluti.es 2015 1 OPTIMIZACIÓN DE MANTENIMIENTO Más detalles Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 Programación Lineal Entera
Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 11 de septiembre de 2003 1. Introducción Un LP donde se requiere que todas las variables sean enteras se denomina un problema Más detalles Secuenciación de tareas mediante metaheurísticos
VIII Congreso de Ingeniería de Organización Leganés, 9 y 10 de septiembre de 2004 Secuenciación de tareas mediante metaheurísticos Santiago López de Haro 1, Pedro Sánchez Martín 2, Javier Conde Collado Más detalles UTgeNes - Framework para Implementación y Estudio de Algoritmos
UTgeNes - Framework para Implementación y Estudio de Algoritmos Genéticos Abstract UTgeNes es un framework para la implementación y estudio de algoritmos genéticos propuesto para la realización de trabajos Más detalles Una permutación eficiente para minimizar la suma de los tiempos de acabado de "n" trabajos en "m" máquinas Freddy Abarca R. fabarca@ic-itcr.ac.
Una permutación eficiente para minimizar la suma de los tiempos de acabado de "n" trabajos en "m" máquinas Freddy Abarca R. fabarca@ic-itcr.ac.cr El problema de la asignación de cargas de trabajo, a pesar Más detalles Programación de Sistemas Productivos
Universidad Simón Bolívar Programación de Sistemas Productivos Secuenciación de Operaciones PS-4162 Gestión de la Producción II 1 Contenido Secuencias de trabajo en los centros de trabajo Reglas de prioridad Más detalles UNIVERSIDAD TECNOLÓGICA DE PEREIRA FACULTAD DE INGENIERÍA ELÉCTRICA PROGRAMA DE MAESTRÍA EN INGENIERÍA ELÉCTRICA
UNIVERSIDAD TECNOLÓGICA DE PEREIRA FACULTAD DE INGENIERÍA ELÉCTRICA PROGRAMA DE MAESTRÍA EN INGENIERÍA ELÉCTRICA ALGORITMOS GRASP Y SIMULATED ANNEALING COMO INICIALIZADORES DE BRANCH AND BOUND EN LA SOLUCIÓN Más detalles 7. Conclusiones. 7.1 Resultados
7. Conclusiones Una de las preguntas iniciales de este proyecto fue : Cuál es la importancia de resolver problemas NP-Completos?. Puede concluirse que el PAV como problema NP- Completo permite comprobar Más detalles Introducción INTRODUCCIÓN
Introducción INTRODUCCIÓN Las empresas de distintos sectores económicos han concebido la logística como un proceso estratégico para mantener su actividad y garantizar la eficiencia de las operaciones de Más detalles GPU IMPLEMENTATIONS OF SCHEDULING HEURISTICS FOR HETEROGENEOUS COMPUTING ENVIRONMENTS
GPU IMPLEMENTATIONS OF SCHEDULING HEURISTICS FOR HETEROGENEOUS COMPUTING ENVIRONMENTS MAURO CANABÉ SERGIO NESMACHNOW Centro de Cálculo, Facultad de Ingeniería Universidad de la República, Uruguay GPU IMPLEMENTATIONS Más detalles MODELO JERÁRQUICO PARA EL JOB SHOP FLEXIBLE
!#"$%$$ %!& '($! *)!!#% $)$ +-,/.103254 687/9:6(;=1.1?A@50 Más detalles CAPITULO II. MARCO TEÓRICO. Actualmente todas las personas que tengan un capital considerable pueden invertir en
CAPITULO II. MARCO TEÓRICO II.1. Mercados Financieros II.1.1 Marco histórico Actualmente todas las personas que tengan un capital considerable pueden invertir en acciones a fin de obtener ganancias rápidas Más detalles TÉCNICAS HEURÍSTICAS Y METAHEURÍSTICAS DE OPTIMIZACIÓN
TÉCNICAS HEURÍSTICAS Y METAHEURÍSTICAS DE OPTIMIZACIÓN RAMÓN ALFONSO GALLEGO RENDÓN ANTONIO ESCOBAR ZULUAGA ELIANA MIRLEDY TORO OCAMPO Universidad Tecnológica de Pereira Pereira - Risaralda - Colombia Más detalles Algoritmos exactos y heurísticos para minimizar el adelantamiento y retraso ponderados en una máquina con una fecha de entrega común
Algoritmos... en una máquina con una fecha de entrega común Algoritmos exactos y heurísticos para minimizar el adelantamiento y retraso ponderados en una máquina con una fecha de entrega común R. Alvarez-Valdés, Más detalles SOLUCIÓN DEL PROBLEMA DE PROGRAMACIÓN DE FLOW-SHOP FLEXIBLE EMPLEANDO EL ALGORITMO GENÉTICO DE CHU-BEASLEY ÁNGELA PATRICIA JIMÉNEZ MORALES
SOLUCIÓN DEL PROBLEMA DE PROGRAMACIÓN DE FLOW-SHOP FLEXIBLE EMPLEANDO EL ALGORITMO GENÉTICO DE CHU-BEASLEY ÁNGELA PATRICIA JIMÉNEZ MORALES UNIVERSIDAD TECNOLÓGICA DE PEREIRA FACULTAD DE INGENIERÍA INDUSTRIAL Más detalles SESIÓN 8 TIPOS DE SISTEMAS DE MANUFACTURA
SESIÓN 8 TIPOS DE SISTEMAS DE MANUFACTURA CONTENIDO Términos en manufactura Clasificación de sistemas de manufactura Beneficios y ejemplos de sistemas de manufactura Los componentes de un sistema de manufactura Más detalles Metaheurísticas: una visión global *
Metaheurísticas: una visión global * Belén Melián, José A. Moreno Pérez, J. Marcos Moreno Vega DEIOC. Universidad de La Laguna 38271 La Laguna {mbmelian,jamoreno,jmmoreno}@ull.es Resumen Las metaheurísticas Más detalles PROCEDIMIENTO HEURÍSTICO PARA MINIMIZAR EL C max EN CELDAS ROBOTIZADAS CON BUFFERS FINITOS Y PIEZAS DISTINTAS
27 Congreso Nacional de Estadística e Investigación Operativa Lleida, 8 11 de abril de 2003 PROCEDIMIENTO HEURÍSTICO PARA MINIMIZAR EL C max EN CELDAS ROBOTIZADAS CON BUFFERS FINITOS Y PIEZAS DISTINTAS Más detalles Algoritmos Genéticos Y
Algoritmos Genéticos Y Optimización n Heurística Dr. Adrian Will Grupo de Aplicaciones de Inteligencia Artificial Universidad Nacional de Tucumán awill@herrera.unt.edu.ar Algoritmos Genéticos - Operadores Más detalles Nuevas Tendencias y Retos en Métodos Heurísticos para Problemas de Scheduling
Nuevas Tendencias y Retos en Métodos Heurísticos para Problemas de Scheduling Ramiro Varela Grupo de Tecnologías de la Computación. Departamento de Informática. Centro de Inteligencia Artificial Universidad Más detalles TÉCNICAS DE PLANIFICACIÓN Y CONTROL DE PROYECTOS 1
Técnicas de planificación y control de proyectos Andrés Ramos Universidad Pontificia Comillas http://www.iit.comillas.edu/aramos/ Andres.Ramos@comillas.edu TÉCNICAS DE PLANIFICACIÓN Y CONTROL DE PROYECTOS Más detalles Estado del arte del problema de flujo general flexible con costes en la función objetivo *
Estado del arte del problema de fluo general flexible con costes en la función obetivo * Albert Corominas, Néstor Andrés González, Rafael Pastor Institut d'organització i Control de Sistemes Industrials Más detalles Uso de una Colonia de Hormigas. para resolver Problemas de Programación. de Horarios
LABORATORIO NACIONAL DE INFORMÁTICA AVANZADA A. C. Centro de Enseñanza LANIA Uso de una Colonia de Hormigas para resolver Problemas de Programación de Horarios Tesis que presenta: Emanuel Téllez Enríquez Más detalles Análisis del Sistema de Información
Análisis del Sistema de Información ÍNDICE DESCRIPCIÓN Y OBJETIVOS... 2 ACTIVIDAD ASI 1: DEFINICIÓN DEL SISTEMA... 6 Tarea ASI 1.1: Determinación del Alcance del Sistema... 6 Tarea ASI 1.2: Identificación Más detalles Algoritmos Evolutivos
Algoritmos Evolutivos 2003-11-20 Cristóbal Romero, Pedro González y Sebastián Ventura 1.1 Introducción En general, cualquier tarea abstracta a realizar puede considerarse como la resolución de un problema Más detalles Uso de algoritmos genéticos para resolver el modelo determinista y estocástico para el diseño de una red de recogida de residuos
International Conference on Industrial Engineering & Industrial Management - CIO 2007 1443 Uso de algoritmos genéticos para resolver el modelo determinista y estocástico para el diseño de una red de recogida Más detalles UN MODELO PARA LA PREDICCIÓN DE RECIDIVA DE PACIENTES OPERADOS DE CÁNCER DE MAMA (CMO) BASADO EN REDES NEURONALES
UN MODELO PARA LA PREDICCIÓN DE RECIDIVA DE PACIENTES OPERADOS DE CÁNCER DE MAMA (CMO) BASADO EN REDES NEURONALES José Alejandro Chiri Aguirre RESUMEN La predicción de recidiva en pacientes que han sido Más detalles UNIVERSIDAD DE CONCEPCIÓN CHILE FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL
UNIVERSIDAD DE CONCEPCIÓN CHILE FACULTAD DE INGENIERÍA DEPARTAMENTO DE INGENIERÍA INDUSTRIAL APLICACIÓN DE HEURÍSTICAS GRASP AL PROBLEMA DE MÁQUINAS PARALELAS NO RELACIONADAS CON TIEMPOS DE SETUP DEPENDIENTES Más detalles Revista Ingenierías Universidad de Medellín ISSN: 1692-3324 revistaingenierias@udem.edu.co Universidad de Medellín Colombia
Revista Ingenierías ISSN: 1692-3324 revistaingenierias@udem.edu.co Colombia Osorio, Juan Carlos; Lasso, Diego Fernando; Ruiz, Gabriel Alonso JOB SHOP SCHEDULING BIOBJETIVO MEDIANTE ENFRIAMIENTO SIMULADO Más detalles Universidad Tecnológica Nacional Facultad Regional Tucumán
Categoría: Trabajos Finales de Carreras de Grado Título del trabajo: Optimización de la Toma de Decisiones en Gestión, utilizando Algoritmos Genéticos y Sistemas Expertos Difusos Autores: Director y Asignatura: Más detalles DESARROLLO DE SOFTWARE CON CALIDAD PARA UNA EMPRESA
DESARROLLO DE SOFTWARE CON CALIDAD PARA UNA EMPRESA Resumen AUTORIA CARLOS CABALLERO GONZÁLEZ TEMATICA INFORMÁTICA ETAPA ESO-BACHILLERATO-CFGM(ESI,ASI,DSI) Se describe la revolución que supuso la incursión Más detalles Fundamento de Informática Teórica(2003) Prof. Dr. Eric Jeltsch F. ORGANIZACION FISICA DE LOS SISTEMAS DE BASE DE DATOS
ORGANIZACION FISICA DE LOS SISTEMAS DE BASE DE DATOS La organización física de una base de datos es un tópico extenso y se aborda en detalle, principalmente en la asignatura Base de Datos, y digo principalmente Más detalles 1. CONCEPTO DE CONFIABILIDAD, HISTORIA Y CAMPOS DE APLICACIÓN
1. CONCEPTO DE CONFIABILIDAD, HISTORIA Y CAMPOS DE APLICACIÓN 1.1 CONCEPTO DE CONFIABILIDAD Desde el punto de vista de Ingeniería, se ha aceptado la definición de Confiabilidad de un elemento, como la Más detalles Sistemas, modelos y simulación
Sistemas, modelos y simulación Introducción I Un SISTEMA es una colección de entidades (seres o máquinas) que actúan y se relacionan hacia un fin lógico. Ejemplo: Un banco con: Cajeros [comerciales] [cajas Más detalles Tema I: Gestión de Proyectos Software: Planificación
Tema I: Gestión de Proyectos Software: Planificación Bibliografía Calvo-Manzano, J.A., Cervera, J., Fernández, L., Piattini, M. Aplicaciones Informáticas de Gestión. Una perspectiva de Ingeniería del Software. Más detalles PLANIFICACIÓN DE PROYECTOS
Pert - CPM: Uno de los primeros casos documentados de la epoca actual sobre la administración y planificacion de proyectos se refiere al proyecto de armamentos del Polaris, empezando 1958. Así surgió el Más detalles Describir el CMMI para el desarrollo de software, evolución, alcance y representación
Unidad 6: Introducción a CMMI Objetivo terminal de la Unidad Describir el CMMI para el desarrollo de software, evolución, alcance y representación Temas: Acerca del Modelo Capacidad Madurez Evolución de Más detalles Estimación de parámetros, validación de modelos y análisis de sensibilidad
Tema 6 Estimación de parámetros, validación de modelos y análisis de sensibilidad 6.1 Calibración Una vez que se ha identificado el modelo y se ha programado, necesitamos aplicarlo al problema concreto Más detalles Nota Técnica. Modelo de Diseño Instruccional de Hannafin & Peck: algunas apreciaciones técnico-funcionales en ambientes WEB 1
Nota Técnica Modelo de Diseño Instruccional de Hannafin & Peck: algunas apreciaciones técnico-funcionales en ambientes WEB 1 YSRAEL ORLANDO MÁRQUEZ RAMÍREZ ysraelmarquez@gmail.com Universidad Nacional Más detalles Evaluación de la disponibilidad de los servicios desplegados sobre Volunteer Computing
Evaluación de la disponibilidad de los servicios desplegados sobre Volunteer Computing Antonio Escot Praena Enginyeria Informàtica i Tècnica de Gestió Dirección del TFC Ángel A. Juan, PhD. Eva Vallada Más detalles Selección usando Algoritmos
Capítulo 3 Selección usando Algoritmos Genéticos 3.1. Introducción En esta sección se aborda el uso de Algoritmos Genéticos (GA del inglés Genetic Algorithms) para selección de características. Así como Más detalles PONTIFICIA UNIVERSIDAD CATÓLICA DEL PERÚ FACULTAD DE CIENCIAS E INGENIERÍA
TESIS PUCP Esta obra ha sido publicada bajo la licencia Creative Commons Reconocimiento-No comercial-compartir bajo la misma licencia 2.5 Perú. Para ver una copia de dicha licencia, visite http://creativecommons.org/licenses/by-nc-sa/2.5/pe/ Más detalles Metaheurísticas basadas en Scatter Search y Path Relinking para resolver el Problema del Fuzzy Job Shop Scheduling
FACULTAD DE CIENCIAS UNIVERSIDAD DE CANTABRIA Proyecto Fin De Carrera Metaheurísticas basadas en Scatter Search y Path Relinking para resolver el Problema del Fuzzy Job Shop Scheduling (Scatter Search Más detalles Representación, Codificación en un AG Población Inicial. Aptitud. Estrategia de Selección. Cruce, Mutación, Reemplazo. Condición de Parada.
Computación n Evolutiva: Algoritmos Genéticos 1.- Metaheurísticos. Computación Evolutiva: Algoritmos Genéticos 2.- Conceptos principales de un Algoritmo Genético 3.- Estructura de un Algoritmo Genético Más detalles 2.2.- Puntos de renovación de pedidos. Punto de re orden = Margen de tiempo en días x uso diario Tiempo = 16 días
2.2.- Puntos de renovación de pedidos. Una vez que la empresa ha calculado la cantidad económica de pedido, debe determinar el momento adecuado para efectuar los pedidos. Se requiere un punto de re orden Más detalles PLANEACIÓN DE SISTEMAS INFORMÁTICOS ING. KARINA RAMÍREZ DURÁN
PLANEACIÓN DE SISTEMAS INFORMÁTICOS ING. KARINA RAMÍREZ DURÁN Diagrama de Gantt Fue desarrollada por Henry L. Gantt, durante la primera guerra mundial. Con estas graficas Gantt procuro resolver el problema Más detalles Computación Evolutiva: Algoritmos Genéticos
Computación Evolutiva: Apuntes de la asignatura: Inteligencia Artificial Razonamiento Aproximado (Máster) Daniel Manrique Gamo Profesor Titular de Universidad Índice 1. Introducción 5 1.1. Bases de la Más detalles Propuesta de una arquitectura para la generación de mutantes de orden superior en WS-BPEL
Propuesta de una arquitectura para la generación de mutantes de orden superior en WS-BPEL Emma Blanco Muñoz, Antonio García Domínguez, Juan José Domínguez Jiménez, Inmaculada Medina Bulo Escuela Superior Más detalles Propuesta de un algoritmo evolutivo aplicado a problemas de optimización
Propuesta de un algoritmo evolutivo aplicado a problemas de optimización Javier Izetta Riera 1 y Nilda M. Pérez Otero 1 1 Grupo de Investigación y Desarrollo en Informática Aplicada, Facultad de Ingeniería, Más detalles Tema 2. Ingeniería del Software I feliu.trias@urjc.es
Tema 2 Ciclo de vida del software Ingeniería del Software I feliu.trias@urjc.es Índice Qué es el ciclo de vida del Software? El Estándar 12207 Modelos de proceso Qué es el Ciclo de Vida del SW? Definición Más detalles OPTIMIZACIÓN DE TRANSFORMACIONES LINEALES DE DATOS MEDIANTE BUSQUEDA LOCAL
OPTIMIZACIÓN DE TRANSFORMACIONES LINEALES DE DATOS MEDIANTE BUSQUEDA LOCAL INGENIERIA INFORMATICA AUTOR: FRANCISCO GODOY MUÑOZ-TORRERO TUTOR: JOSE MARIA VALLS FERRAN CO-DIRECTOR: RICARDO ALER MUR Contenidos Más detalles GANTT, PERT y CPM. Figura 5.3: Carta GANTT 3.
GANTT, PERT y CPM Características Conseguir una buena programación es un reto, no obstante es razonable y alcanzable. Ella debe tener el compromiso del equipo al completo, para lo cual se recomienda que Más detalles Un modelo híbrido de inteligencia computacional para resolver el problema de Job Shop Scheduling
Un modelo híbrido de inteligencia computacional para resolver el problema de Job Shop Scheduling Jacob Meneses Angel, Marcela Rivera Martínez, Luis René Marcial Castillo, Sandoval Solís Lourdes Benemérita Más detalles 1.- DATOS DE LA ASIGNATURA. Nombre de la asignatura: Investigación de Operaciones. Carrera: Ingeniería en Sistemas Computacionales
1.- DATOS DE LA ASIGNATURA Nombre de la asignatura: Carrera: Clave de la asignatura: (Créditos) SATCA 1 Investigación de Operaciones SCC-1013 2-2 - 4 Ingeniería en Sistemas Computacionales 2.- PRESENTACIÓN Más detalles 2017 © DocPlayer.es Política de privacidad | Condiciones del servicio | Feedback

References: resolución 
 resolución 
 resolución 
 RESOLUCIÓN 
 RESOLUCIÓN 
 resolución 
 resolución 
 resolución