Source: http://docplayer.es/1260272-Busqueda-heuristica-para-problemas-de-scheduling.html
Timestamp: 2017-01-22 02:27:34+00:00

Document:
⭐Búsqueda Heurística para Problemas de Scheduling *
Download "Búsqueda Heurística para Problemas de Scheduling *"
Celia Sandoval Ponce
1 IX Congreso de Ingeniería de Organización Gijón, 8 y 9 de septiembre de 2005 Búsqueda Heurística para Problemas de Scheduling * María Sierra Sánchez 1, Ramiro Varela Arias 2 1 Dpto. de Informática. Campus de Viesques, Gijón (Asturias). 2 Dpto. de Informática. Campus de Viesques, Gijón (Asturias). Resumen En este artículo presentamos una aplicación del algoritmo A* al problema Job Shop Scheduling (JSS). Explotamos el espacio de búsqueda de las planificaciones activas y un heurístico basado en relajaciones del problema. Estudiamos experimentalmente el límite hasta el cual se pueden obtener soluciones óptimas de esta forma y también algunas extensiones para obtener soluciones semi-óptimas. Y comparamos los resultados con los obtenidos por otros sistemas similares bien conocidos. Finalmente proponemos algunas mejoras para realizar en un trabajo futuro. Palabras clave: Scheduling, búsqueda heurística, optimización, satisfacción de restricciones 1. Introducción El algoritmo A* propuesto en Nilsson (1980) y Pearl (1983) es un algoritmo de búsqueda heurística en espacios de estados. En este trabajo presentamos una aplicación del algoritmo A* para resolver el problema Job Shop Scheduling (JSS). El JSS es un paradigma de la familia de problemas de Scheduling que ha interesado a muchos investigadores en las últimas tres décadas; en consecuencia, se han aplicado un gran número de técnicas a este problema. En Jain y Meeran (1999) se realiza una extensa revisión de las aproximaciones más importantes. A la hora de resolver un problema empleando el algoritmo A*, es necesario tomar dos decisiones fundamentales: la primera es definir un espacio de búsqueda completo, y después considerar una buena función heurística. En este trabajo hemos elegido como espacio de búsqueda el espacio de planificaciones activas y hemos considerado como estrategia heurística una, obtenida de relajaciones del problema, basada en el cálculo de la planificación denominada Jackson s Preemptive Schedule (JPS), planificación propuesta en Brucker, Jurisch y Sievers (1994) y Carlier (1994). Con esta aproximación hemos estudiado el límite del tamaño de problemas que se pueden resolver de forma óptima y proponemos un método para obtener, en un tiempo limitado, soluciones no óptimas. Además hemos comparado el algoritmo A* con otros conocidos paradigmas como son el método de Backtracking propuesto por Sadeh y Fox (1996) y el método de Branch and Bound (B&B) propuesto en Brucker, Jurisch y Sievers (1994). En lo referente a la búsqueda de soluciones óptimas, los resultados experimentales muestran que la versión de A* propuesta es mucho mejor que el algoritmo de Backtracking propuesto en Sadeh y Fox (1996), pero peor que el algoritmo de B&B propuesto en Brucker, Jurisch y * Este trabajo ha sido financiado por el proyecto FEDER-MCYT TIC y por la beca FICYT BP04-21.2 Sievers (1994). Sin embargo el algoritmo A* se comporta mucho mejor en la famosa instancia FT20 de este problema. En este caso el algoritmo A* alcanza una solución óptima en pocos segundos, mientras que el B&B no es capaz de obtener una solución óptima después de varios días. Aquí es importante resaltar que el algoritmo de B&B considerado es hoy por hoy la aproximación más eficiente para obtener soluciones óptimas para el problema JSS. Puede resolver casi siempre instancias hasta un tamaño de 15 trabajos y 15 máquinas. Este algoritmo realiza una búsqueda dirigida también por la JPS y, a diferencia de la versión de A*, explota un método de propagación de restricciones que permite reducir el espacio de búsqueda sin perder la completud. Este método de propagación de restricciones podría utilizarse también en combinación con el algoritmo A*, con lo que cabría esperar que ambos métodos fuesen realmente comparables, ya que el algoritmo A* puede resolver instancias que resultan difíciles para el algoritmo B&B. Con respecto a la búsqueda de soluciones semi-óptimas, hemos utilizado un método de reducción del espacio de búsqueda que no garantiza la completud, junto con un método de ponderación de la función heurística. Además hemos combinado el algoritmo A* con un algoritmo voraz, guiado también por los valores de la JPS. Este algoritmo voraz se aplica a partir de la situación que representa un estado intermedio y proporciona una solución heurística en un tiempo polinomial. Como tiene un coste no despreciable, no se aplica a todos los nodos sino a unos pocos con una probabilidad que depende de la profundidad del nodo. El resto del trabajo está organizado como sigue. En la sección 2, se formula el problema JSS. La sección 3 resume las principales características y propiedades del algoritmo A*. En la sección 4, describimos la aplicación propuesta del algoritmo A* al problema JSS, en particular el espacio de búsqueda de planificaciones activas. La sección 5 describe la estrategia heurística empleada que se basa en dos relajaciones del problema. En la sección 6, se muestran los resultados y conclusiones del estudio experimental. Por último, en la sección 7 proponemos algunas las ideas para futuros trabajos. 2. El Problema Job Shop Scheduling El problema Job Shop Scheduling consiste en planificar un conjunto de N trabajos {J 1,...,J N } sobre un conjunto de M recursos o maquinas físicas {R 1,...,R M }. Cada trabajo Ji consta de un conjunto de tareas {θ i1,...,θ im } que han de ser ejecutadas de forma secuencial. Cada tarea θ lj tiene un tiempo de procesamiento sin interrupción de du ij unidades de tiempo durante el cual requiere el uso exclusivo de un único recurso. Cada trabajo tiene un tiempo de inicio más temprano y en ocasiones se considera también un tiempo de finalización más tardío, lo que obliga a que los tiempos de inicio de las tareas tomen valores en dominios finitos. El objetivo es encontrar una planificación factible, es decir una asignación de tiempos de inicio st ij a cada una de las tareas, que minimice el makespan, es decir el tiempo de finalización de la última tarea. Este problema se conoce como JSS//Cmax en la literatura. 3. El Algoritmo A* El algoritmo A* es un método heurístico de búsqueda BF (Best First, o Primero el Mejor) en grafos propuesto en Nilsson (1980) y Pearl (1983), aunque cuando el espacio de búsqueda es un árbol, el algoritmo es mucho más simple. El algoritmo parte de un estado inicial s, tiene una serie de estados objetivo y un operador de transición SCS tal que para cada estado n del espacio de búsqueda, SCS(n) proporciona el conjunto de estados sucesores de n. La transición de un estado n a su sucesor n tiene asociado un coste positivo c(n,n ). El objetivo de la3 búsqueda es encontrar un camino solución, desde el estado inicial s a uno de los estados objetivo. El algoritmo mantiene una lista, ABIERTA, con los estados candidatos a ser expandidos. En cada iteración se expande siempre el estado de ABIERTA con menor valor de la función de evaluación f, definida como f(n) = g(n) + h(n); donde g(n) es el coste mínimo, conocido hasta el momento, desde el estado inicial s hasta el estado actual n, (por supuesto si el espacio de búsqueda es un árbol, el valor de g(n) no cambia una vez que el nodo es visitado); y h(n) es la función heurística y proporciona una estimación positiva de la distancia mínima desde el estado actual hasta el estado objetivo más cercano. El algoritmo A* tiene una serie de propiedades interesantes, la mayoría de ellas dependen de la función heurística h. La primera de todas es que el algoritmo es completo. Por otro lado, si la función heurística subestima el coste mínimo, h * (n), desde n a los objetivos, es decir h(n) h * (n), para todos los estados, el algoritmo es admisible, es decir siempre encuentra una solución óptima. La función heurística h(n) representa el conocimiento disponible sobre el dominio del problema, por lo tanto si se dispone del conocimiento completo con un coste computacional asumible (polinomial en el tamaño del problema), es decir h(n) = h * (n), se puede encontrar la mejor solución expandiendo el menor número de estados posible. Desafortunadamente esto no suele ocurrir, y en los casos prácticos hemos de buscar la mejor subestimación cuyo coste computacional sea razonable. Esto se debe a otra interesante propiedad que dice que si tenemos dos heurísticos admisibles h1 y h2, tales que h1(n) < h2(n) para todos los estados no terminales n, h2 se dice que está mejor informado que h1 y se puede demostrar que, en este caso, todo estado expandido por h2 es también expandido por h1. Cuando ocurre esto podemos decir también que el algoritmo que emplea h2 domina al que emplea h1. Finalmente si h(n) h(n ) + c(n,n ) para todo par de estados n y n, el heurístico es monótono. La monotonía tiene también consecuencias relevantes. La primera de ellas es que todo heurístico monótono es admisible. Además si tenemos dos heurísticos monótonos h1 y h2, tales que h1(n) h2(n) para todo estado n, h2 puede ser considerado mejor que h1 debido a que todo estado n expandido por h2 pero no por h1 debe cumplirse que h1(n) = h2(n) = C * - h * (n), siendo C* el coste de la solución óptima, y puede considerarse poco probable que estas igualdades se cumplan para un número elevado de estados. Para instancias de problemas largos la búsqueda de soluciones óptimas es inabordable incluso si disponemos del heurístico mejor informado. En estos casos el algoritmo A* puede ser modificado para obtener soluciones semi-óptimas con un coste razonable. En esta línea podemos encontrar en la literatura varias aproximaciones que se basan, normalmente, en el uso de heurísticos no admisibles, por ejemplo en Nilsson (1980), Nilsson (1998), Russell y Norving (1995). 4. Aplicación del algoritmo A* al problema JSS El espacio completo de planificaciones factibles es muy grande y además contiene muchas soluciones que no son realmente interesantes. Por a ello se han buscado espacios de búsqueda alternativos con un tamaño mucho más pequeño, pero con la condición de que sean completos. Bajo estas condiciones existen tres espacios de búsqueda de interés: espacios de planificaciones semiactivas, activas y de no-retraso. Una planificación es semiactiva si para adelantar el tiempo de inicio de una tarea en una máquina, es necesario modificar el orden de al menos dos tareas. Una planificación es activa si para adelantar el tiempo de inicio de una tarea, al menos otra debe ser retrasada. Finalmente una planificación es de no-retraso si nunca se da la situación de que una máquina esté desocupada en el mismo instante en el que una tarea puede ser procesada en dicha máquina. Las planificaciones de no-retraso son un4 subconjunto de las planificaciones activas las cuales son a su vez son un subconjunto de las planificaciones semiactivas. La experiencia muestra que el valor medio del makespan es mucho mayor para las planificaciones semiactivas que para las planificaciones activas; y que también, es mucho mayor para las planificaciones activas que para las planificaciones de noretraso. Pero al mismo tiempo sólo los espacios de planificaciones semiactivas y activas garantizan contener, al menos, una planificación óptima. Por lo tanto parece que el espacio más interesante es el de planificaciones activas. Este hecho se ve reforzado por la existencia del conocido algoritmo G&T propuesto por Giffler y Thomson (1960). Este algoritmo es un algoritmo voraz que produce planificaciones activas en N*M pasos. En cada paso el algoritmo G&T realiza una elección no determinista sobre un conjunto B de tareas que pueden ser planificadas a continuación. Cada planificación activa puede ser alcanzada tomando la secuencia apropiada de elecciones. Por otra parte si en cada paso consideramos todas las elecciones posibles tenemos un grafo de búsqueda completo, apropiado para estrategias de búsqueda heurística en espacios de estados tales como Branch and Bound (B&B), Backtracking o A*. Esta es la aproximación adoptada por Storer y Talbot (1992), Hatzikonstantis y Besant (1992), por Varela y Soto (2002) y por Sierra (2003). Basándonos en estos trabajos, como algoritmo de expansión hemos empleado un método basado en el algoritmo G&T en su versión híbrida, propuesto por Bierwirth y Mattfeld (1999). El algoritmo G&T híbrido introduce un mecanismo que permite reducir el número de tareas del conjunto B en cada iteración. Esta reducción viene controlada por el parámetro de reducción δ [0,1]; cuando δ=1 la reducción tiene un efecto nulo con lo que se obtendría el mismo espacio que con el algoritmo G&T original. En esta situación, es posible encontrar una secuencia de elecciones de tareas, que de lugar a una solución óptima, ya que se genera el espacio de planificaciones activas completo. En otro caso, si δ<1, el espacio de búsqueda se restringe a un subconjunto de las planificaciones activas; lo que hace imposible garantizar tal secuencia y por lo tanto garantizar que se pueda alcanzar una solución óptima. Tal y como se indica en Bierwirth y Mattfelf (1999), el algoritmo produce planificaciones de no-retraso en el extremo δ=0. Algoritmo SCS(estado n) 1. A = Conjunto con las primeras tareas sin planificar de cada trabajo en el estado n; 2. Determinar la tarea θ A que si se planificase en el estado n, tiene el menor tiempo de fin, es decir stθ +duθ stθ + duθ, θ A; 3. Seleccionar la máquina M que requiere la tarea θ, y construir el conjunto B con las tareas de A que requieren la máquina M ; 4. Eliminar de B las tareas que no puedan comenzar antes del tiempo de fin de la tarea θ, stθ +duθ ; 5. Reducir el conjunto B a B B ={ θ B / tθ < tθ +δ(( tθ +duθ ) - tθ ) }, δ [0,1]}; 6. Mientras (B ) hacer 7. Seleccionar una tarea θ B y planificarla en su menor tiempo de inicio posible para construir la planificación parcial correspondiente al próximo estado n ; 8. Añadir n a los sucesores; finmientras; 9. retornar sucesores; end. Figura 1. Algoritmo de expansión de un estado n5 La (Figura 1) muestra el algoritmo de expansión que hemos empleado. Este algoritmo es en realidad una extensión del algoritmo G&T híbrido en el que para cada estado intermedio se consideran todas las posibilidades de expansión, en lugar de realizar una única elección no determinista. Este algoritmo genera el espacio de planificaciones activas, completo (δ=1) o no (δ<1) cuando es aplicado sucesivamente desde el estado inicial. El estado inicial se corresponde con la situación en la que ninguna tarea del problema esta planificada. Mientras que en el resto de estados ya están planificadas un subconjunto de tareas. El coste c(n,n ) se obtiene de la diferencia C max (PS(n )) C max (PS(n)), donde C max (PS(n)) es el tiempo máximo de fin de una tarea en la planificación parcial, PS(n), correspondiente al estado n. Es sencillo probar que el espacio de estados generado de este modo es un árbol. 5. Estrategias heurísticas para el problema JSS La técnica más común para obtener heurísticos monótonos es la relajación del problema, Pearl (1983). Esta técnica consiste en relajar algunas de las restricciones con el fin de obtener un problema simplificado que pueda ser resuelto óptimamente en un tiempo polinomial. Luego, el coste de la solución para el problema relajado se toma como estimación del coste del problema real. En el caso del problema JSS, las restricciones que pueden ser relajadas son las secuenciales, de capacidad y de no-expulsión. En este trabajo se ha empleado un heurístico basado en la relajación del problema en dos pasos. Primero se relajan todas las restricciones de capacidad, excepto las restricciones de capacidad correspondientes a una máquina m, obteniendo el problema de Secuenciación de una Máquina (OMS, One Machine Sequencing) para la máquina m. La segunda relajación consiste en relajar la restricción de no-expulsión en el problema OMS para esa máquina m. i r i p i q i a) Instancia de un problema OMS b) El JPS Primal El makespan es 50, se obtiene del tiempo de completud para el trabajo 5( ) Figura 2. Ejemplo de una instancia OMS y de su correspondiente JPS Primal El problema de secuenciación de una máquina puede formularse de la siguiente forma: tenemos un conjunto de trabajos {J 1,,J N }; cada trabajo J i debe ser procesado sin interrupción sobre una máquina m durante p i unidades de tiempo. La máquina m solo puede procesar una tarea a la vez. Además cada trabajo J i tiene un tiempo de procesamiento previo r i y un tiempo de procesamiento posterior q i en otras máquinas que no tienen restricciones de capacidad. El objetivo es planificar todos los trabajos de forma que el makespan sea mínimo. El problema OMS es un problema NP-completo, por ello se hace una nueva simplificación: se relajan las restricciones de no-expulsión de la máquina m. De este modo la solución óptima del problema resultante, tras esta última relajación, se obtiene de la Planificación con Expulsión de Jackson (JPS, Jackson s Preemptive Schedule ) propuesta en Brucker, Jurisch y Sievers (1994). El método para calcular la JPS comienza asignando a cada trabajo J i una prioridad proporcional a su q i. Después en cada instante de tiempo t, desde el trabajo con menor r i hasta que todos los trabajos son procesados en la máquina m, se planifica el trabajo con mayor prioridad, sobre la6 máquina m, durante el intervalo [t,t+1[. El makespan es el máximo, de entre todos los trabajos, del tiempo de fin sobre m más el correspondiente q i. La (Figura 2) muestra un problema de OMS para 6 trabajos y su correspondiente JPS. Debido a la simetría entre los tiempos previos y posteriores de procesamiento r i y q i, el problema dual es también interesante. Este es el problema en el que r i y q i son intercambiados. Es fácil ver que la solución del problema primal es también solución del problema dual. Sin embargo el coste del JPS Dual (DJPS) puede ser diferente del coste del problema JPS Primal (PJPS). Ambas JPSs pueden ser calculadas en O(N*log 2 N) pasos. Del modelo relajado anterior para el problema JSS, obtenemos un nuevo heurístico que implica los siguientes cálculos. Para cada estado n tomamos el problema JSS definido por las tareas no planificadas en n, con los tiempos de inicio de las tareas no planificadas del trabajo J tomadas como el máximo de C J max ( PS( n) ) y el tiempo de fin de la última tarea planificada en el estado n en la máquina correspondiente. El heurístico, denominado h JPS, se calcula de la siguiente forma: h JPS = m Maquinas max (1) ( n) MAX MAX ( PJPS ( m), DJPS ( m) ) C ( PS ( n) ) Donde PJPS(m) y DJPS(m) representan las planificaciones JPS Primal y Dual, respectivamente, para el problema correspondiente al estado n relajado de modo que la única restricción de capacidad que se considera es la correspondiente a la máquina m. Máquinas se refiere a las máquinas con al menos una tarea sin planificar en el estado n. Aunque el heurístico h JPS es claramente una subestimación del coste óptimo, no es de esperar que la diferencia h * (n)- h JPS (n) sea uniforme para todos los estados a lo largo del proceso de búsqueda. Sin embargo, se espera que esta diferencia sea grande al principio de la búsqueda, disminuya a medida que la búsqueda avanza y que tienda a ser nula al final de ésta. Esto nos induce a emplear una técnica heurística de ponderación dinámica: se introduce un factor de ponderación P(n) que se aplica a la componente h de la función f, de tal manera que esta función pasa a ser f(n)=g(n)+p(n)h(n). El valor P(n) depende de la profundidad del nodo n. En este trabajo proponemos el siguiente valor: ( n) profundida d P ( n) = K K + 1 (2) N M Donde K 0 es el parámetro de ponderación que permite controlar la función de ponderación P(n) tal como se describe en Nilsson (1980), profundidad(n) es el número de tareas planificadas en el estado n, N es el número de trabajos y M el número de máquinas. Se ve claramente que para valores de K>0, no se puede garantizar que la función f, mencionada anteriormente, sea admisible ya que la componente P(n)h(n) puede sobreestimar el valor de h * (n). Sin embargo, para algunos valores de K, se espera que este componente sea una buena aproximación de h * (n). Tal y como se prueba en Polh (1977) este método de ponderación garantiza que la solución que se encuentra tiene un coste no superior a C*(1+K). En Bonet y Geffner (2001), se propone un método estático que emplea un factor de ponderación constante W para problemas de planificación de actuaciones; este método garantiza una solución con coste no superior a C*(1+W). En Hatzikonstantis y Besant (1992) se emplea un método dinámico similar al que empleamos en este trabajo para el problema JSS combinado con un7 esquema de memoria limitado y un heurístico no admisible obtenido de una regla de prioridad (dispatching rule) clásica que sobreestima el coste óptimo. En este trabajo para obtener soluciones semi-óptimas hemos empleado valores de K>0, combinados con valores para el parámetro de reducción del espacio de búsqueda δ<1. 6. Estudio Experimental En esta sección mostramos los resultados del estudio experimental realizado sobre varios conjuntos de problemas JSS. Hemos empleado un prototipo de A* implementado en lenguaje C++ y desarrollado en Builder C para Windows. En el primer conjunto de experimentos hemos considerado los problemas propuestos por Sadeh y Fox (1996). Se trata de un conjunto de problemas de tamaño 10 5 que está organizado en 6 grupos de 10 problemas cada uno. Cada grupo está caracterizado por 2 parámetros: BK y RG. BK es el parámetro de cuello de botella, este parámetro controla el número de recursos que son cuello de botella. Un recurso es un cuello de botella si aparece en la misma posición en la secuencia de tareas de todos los trabajos y además las tareas que requieren el recurso, tienen en promedio, un tiempo de procesamiento más grande que el resto. RG es el parámetro de rango que controla la distribución de los tiempos más tempranos de inicio y los tiempos más tardíos de fin de los trabajos. Tabla 1. Resultados experimentales de A* con el heurístico h JPS sobre los problemas de Sadeh (tamaño 10 5) Subconjunto de Problemas Número de problemas resueltos óptimamente Numero de problemas resueltos expandiendo 51 estados Número medio de estados expandidos Tiempo Medio (s.) BK = 1, RG = 0, BK = 2, RG = 0, BK = 1, RG = 0, BK = 2, RG = 0, BK = 1, RG = 0, BK = 2, RG = 0, Tabla 2. Resultados experimentales sobre los problemas LA01-15 y FT20 A*( h JPS.) B&B Instancias Tamaño Problemas Resueltos Tiempo Medio (s.) Problemas Resueltos Tiempo Medio (s.) La of of 5 < 1 La of of 5 < 1 La of of 5 < 1 FT of of 1 > 3 days La (Tabla 1) resume los resultados obtenidos con el heurístico h JPS para los 60 problemas. Como podemos observar todas las instancias se resuelven óptimamente. De estos resultados se puede concluir que los problemas con BK=2 son más difíciles de resolver que los que sólo tienen 1. Sin embargo parece que el parámetro RG no tiene relevancia desde el punto de vista de la dificultad del problema. Sadeh y Fox (1996) muestran los resultados de aplicar un algoritmo de Backtracking dirigido por un heurístico de ordenación de valores y variables diseñado para hacer frente a los problemas con recursos que son cuellos de botella. En este estudio no se trataba de alcanzar soluciones óptimas, sino solamente soluciones no peores en8 un 20% a la solución óptima. Incluso dentro de este límite la búsqueda del Backtracking sólo en 52 de los 60 problemas alcanzaba una solución factible; aunque el tiempo medio requerido para los casos resueltos es de aproximadamente 2 segundos en un DECstation5000/200. La (Tabla 2) resume los resultados del algoritmo A* junto con el heurístico h JPS y del algoritmo B&B sobre un conjunto de problemas tomados del repositorio OR-library. Como podemos observar A* resuelve todas las instancias de tamaño 10 5, sin embargo para las instancias de tamaños 15 5 y 20 5 sólo se resolvieron 4 de 5 (las 2 no resueltas son el LA10 y LA11). En general A* requiere mucho más tiempo que B&B; sin embargo hay una excepción, el problema FT20. En este caso el A* alcanza la solución óptima en 30 segundos, mientras que el B&B no es capaz de encontrar una solución óptima después de 3 días de procesamiento. En la (Tabla 3) resumimos los resultados de 3 conjuntos de 10 problemas cada uno, generados de forma aleatoria por nosotros. Aquí podemos concluir que el prototipo de A* es capaz de resolver, con un coste razonable, problemas cuadrados de hasta un tamaño de 9 9. Tabla 3. Resultados experimentales del A* y B&B, sobre 3 conjuntos de 10 problemas cuadrados Tamaño de los Problemas Prob. Resueltos A* (h JPS ) B&B Nro. Medio de Nodos Exp. Tiempo Medio (s.) Prob. Resueltos Nro. Medio de Nodos Exp. Tiempo Medio (s.) < < < 1 Una vez alcanzado el límite de tamaño de problemas resolubles óptimamente, hemos intentado resolver de forma semi-óptima, tanto los problemas no resueltos óptimamente en los experimentos anteriores, como una batería de problemas de tamaño tomados del repositorio OR-library (problemas ORB). Para ello hemos empleado la técnica de reducción del espacio de búsqueda combinada con la técnica de ponderación de la estimación heurística. Nuestro objetivo es encontrar soluciones buenas, óptimas o no, en un tiempo razonable (1200 segundos); para ello se emplea una técnica de construcción de soluciones heurísticas que proporciona cotas superiores de la solución óptima, y en consecuencia permite podar el espacio de búsqueda del algoritmo A* evitando expandir nodos que superen el coste de la mejor solución calculada hasta el momento. La técnica de construcción de soluciones heurísticas consiste en emplear el algoritmo G&T híbrido, aplicando a la lista de sucesores de cada nodo n tres reducciones, la primera tomando un factor de reducción δ=0,5; la segunda dejando en el conjunto de sucesores sólo aquellos nodos n tales que tienen el mejor valor de c(n,n ) + JPS(n,M ); donde JPS(n,M ) es el valor del JPS para las tareas que requieren la máquina M y no están planificadas en el estado n ; y M es la máquina requerida por la tarea planificada para pasar de n a n. Y por último se eliminan aquellos sucesores con una estimación de coste superior a la cota superior actual. Cuando el conjunto de sucesores resultante tiene una tamaño mayor que 1 se elije de forma aleatoria el siguiente sucesor; en caso de que tenga tamaño 0 se para el proceso de construcción de la solución heurística, manteniéndose la mejor encontrada hasta el momento. El primer paso de esta técnica consiste en obtener una solución inicial (se calcula para el estado inicial), por lo que no se aplica la última reducción. Por tratarse de una técnica costosa sólo se aplicará con una probabilidad 0,3 a los nodos que superen una profundidad del 80% de la profundidad máxima del espacio de búsqueda (N*M+1), ya que cuanto más cerca nos9 encontramos de obtener una solución, es de esperar que las soluciones calculadas con esta técnica sean mejores. El tiempo máximo de ejecución se fija en 1200 s y δ=0.5 en el algoritmo de cálculo de soluciones heurísticas. Problema Tabla 4. Resultados experimentales sobre los problemas ORB δ=0 en A*( h JPS ) K=0,1 K=0,2 K=0,3 Solución Óptima Solución Tiempo (s.) Solución Tiempo (s.) Solución Tiempo (s.) ORB ORB ORB ORB ORB ORB ORB ORB ORB ORB LA LA p09x09_ p09x09_ Problema Tabla 5. Resultados experimentales sobre los problemas ORB01-10, δ=0,5 en A*( h JPS ) K=0,1 K=0,2 K=0,3 Solución Óptima Solución Tiempo (s.) Solución Tiempo (s.) Solución Tiempo (s.) ORB ORB ORB ORB ORB ORB ORB ORB ORB ORB LA LA p09x09_ p09x09_ Tabla 6. Resultados experimentales sobre los problemas ORB01-10, δ=1 en A*( h JPS ) Problema K=0,1 K=0,2 K=0,3 Solución Óptima Solución Tiempo (s.) Solución Tiempo (s.) Solución Tiempo (s.) ORB ORB ORB ORB ORB ORB ORB ORB ORB ORB LA LA p09x09_ p09x09_10 En estas condiciones hemos dado al parámetro de reducción δ los valores 0, 0,5 y 1, variando para cada uno de ellos el factor de ponderación de 0,1 a 0,3 con un incremento de 0,1. Las tablas (Tabla 4), (Tabla 5) y (Tabla 6) muestran los resultados. Lo primero que se observa para todos los valores de δ es que a medida que se incrementa K las soluciones son en general peores pero el coste de la búsqueda disminuye, pudiendo considerar que la mejor relación entre el coste de la búsqueda y la calidad de la solución se obtiene para K=0,2. En lo que respecta al parámetro de reducción, se observa que el valor de δ con mejor comportamiento es δ=0,5, valor para el que se resuelven de forma óptima los problemas LA10, LA11, p09x09_08. Este resultado es análogo al obtenido en Bierwirth y Mattfeld (1999) dónde se utiliza un algoritmo genético que realiza búsqueda en el espacio de planificaciones activas y se utiliza también la reducción del mismo a través del parámetro δ. 7. Trabajo Futuro Como principal idea proponemos incorporar en el prototipo de A* los métodos de propagación de restricciones que se utilizan, por ejemplo, en Brucker, Jurisch y Sievers (1994). De este modo se espera conseguir un algoritmo comparable a los métodos más eficientes de ramificación y poda. Referencias Bierwirth, Ch.; Mattfeld, D. C. (1999). Production Scheduling and Rescheduling with Genetic Algoritms. Evolutionary Computation 7 (1), Bonet, B.; Geffner, H. (2001). Planning as Heuristic Search. Art. Intelligence 129, Brucker, P.; Jurisch, B.; Sievers, B. (1994). A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics 49, Carlier, J.; Pinson, E. (1994). Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research 78, Giffler, B.; Thomson, G. L. (1960). Algorithms for Solving Production Scheduling Problems. Operations Reseach 8, Hatzikonstantis, L.; Besant, C. B. (1992). Job-Shop Scheduling Using Certain Heuristic Search Algorithms. Int. J. Adv. Manuf. Tecnol. 7, Jain, A. S.; Meeran, S. (1999). Deterministic job-shop scheduling: Past, present and future. European Journal of Operational Research 113, Nilsson, N. (1980). Principles of Artificial Intelligence. Tioga, Palo Alto, CA. Nilsson, N. (1998). Artificial Intelligence. A New Synstesis. Morgan Kaufmann Publishers. Pearl, J. (1983). Heuristics. Morgan Kauffman, San Francisco, CA. Pohl, I. (1977) Practical and theoretical considerations in heuristic search algorithms. Machine Intelligence 8. Ed. E. W. Elcock and D. Michie, Ellis H. Ltd., Chich., G.B. Russell, S.; Norving, P. (1995). Artificial Intelligence, A Modern Approach. Prentice-Hall International. Sadeh, N.; Fox, M.S. (1996). Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem. Artificial Intelligence 86, Sierra, M. (2003). Resolución de Problemas de Scheduling con el Algoritmo A*. Proyecto Fin de Carrera, EPSIG, Universidad de Oviedo. Storer, R.; Talbot, F. (1992). New search spaces for sequencing problems with application to job shop scheduling. Management Science 38, Varela, R.; Soto, E. (2002). Scheduling as Heuristic Search with State Space Reduction. Ed. Springer, LNAI 2527, pp Documentos relacionados
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 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 UNIVERSIDAD DE OVIEDO
UNIVERSIDAD DE OVIEDO DEPARTAMENTO DE INFORMÁTICA Mejora de Algoritmos de Búsqueda Heurística mediante Poda por Dominancia. Aplicación a Problemas de Scheduling Tesis Doctoral Autor: María Rita Sierra 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 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 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 Evolutionary Computation for CSP s. Camino R. Vela, Jorge Puente, Cesar L. Alonso, Ramiro Varela
ARTÍCULO Evolutionary Computation for CSP s Camino R. Vela, Jorge Puente, Cesar L. Alonso, Ramiro Varela Centro de Inteligencia Artificial University of Oviedo. Campus de Viesques Gijón, 71 e-mail: {camino, Más detalles SECUENCIACIÓN DE SISTEMAS DE TIPO JOB SHOP MEDIANTE APRENDIZAJE AUTOMÁTICO
SECUENCIACIÓN DE SISTEMAS DE TIPO JOB SHOP MEDIANTE APRENDIZAJE AUTOMÁTICO Paolo Priore Moreno Raúl Pino Diez Alberto Gómez Gómez UNIVERSIDAD DE OVIEDO Una forma habitual de secuenciar de modo dinámico 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 Capítulo VI MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING
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 Flow-Shop Dinámico. Por: Juan Carlos Rivera Samuel De Greiff
Flow-Shop Dinámico Por: Juan Carlos Rivera Samuel De Greiff 1 Configuración tipo Flow- Shop Disposición lineal de los equipos. Productos con altos niveles de estandarización. Varios productos en volúmenes 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 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 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 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 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 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 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 Resumen de técnicas para resolver problemas de programación entera. 15.053 Martes, 9 de abril. Enumeración. Un árbol de enumeración
5053 Martes, 9 de abril Ramificación y acotamiento () Entregas: material de clase Resumen de técnicas para resolver problemas de programación entera Técnicas de enumeración Enumeración completa hace una Más detalles 7. Conclusiones. 7.1 Resultados
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 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 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 Métodos Heurísticos en Inteligencia Artificial
Representación con Restricciones de Medidas Cualitativas: Aplicación a un Problema de Scheduling Salvador E. Ayala-Raggi German Cuaya-Simbro Modesto G. Medina-Melendrez Angélica Muñoz-Meléndez Instituto 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 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 Ingeniería Técnica en Informática de Gestión
Departamento de Informática Universidad Carlos III de Madrid Ingeniería Técnica en Informática de Gestión Inteligencia Artificial Febrero 2006. 1 a parte Normas generales del examen El tiempo para realizar Más detalles Tema 5: Problemas de satisfacción de restricciones
Tema 5: Problemas de satisfacción de restricciones José Luis uiz eina José Antonio Alonso Franciso J. Martín Mateos María José Hidalgo Departamento de Ciencias de la Computación e Inteligencia Artificial Más detalles Programación de la producción en talleres de flujo con máquinas sin interrupción. Algoritmos y aplicaciones *
3 rd International Conference on Industrial Engineering and Industrial Management XIII Congreso de Ingeniería de Organización Barcelona-Terrassa, September 2nd-4th 2009 Programación de la producción en Más detalles El proyecto realizado consiste en un resolutor de sudokus mediante CSP.
Búsqueda en Inteligencia Artificial Fernando Berzal, berzal@acm.org Búsqueda en I.A. Introducción Espacios de búsqueda Agentes de búsqueda Uso de información en el proceso de búsqueda Búsqueda sin información Más detalles HEURISTIC FOR SCHEDULING OF PROJECTS WITH RESTRICTION OF RESOURCES UN HEURÍSTICO PARA PLANEACIÓN DE PROYECTOS CON RESTRICCIÓN DE RECURSOS
HEURISTIC FOR SCHEDULING OF PROJECTS WITH RESTRICTION OF RESOURCES UN HEURÍSTICO PARA PLANEACIÓN DE PROYECTOS CON RESTRICCIÓN DE RECURSOS Juan C. Rivera, Luis F. Moreno, F. Javier Díaz, Gloria E. Peña 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 Problemas de Satisfacción de Restricciones
Problemas de Satisfacción de estricciones José Luis uiz eina José Antonio Alonso Jiménez Franciso J. Martín Mateos María José Hidalgo Doblado Dpto. Ciencias de la Computación e Inteligencia Artificial Más detalles Desarrollo de un nuevo algoritmo para resolver programas lineales enteros y su aplicación práctica en el desarrollo económico.
Desarrollo de un nuevo algoritmo para resolver programas lineales enteros y su aplicación práctica en el desarrollo económico. 7071 Febrero, 2014 Resumen Es importante señalar que en un entorno social Más detalles Complejidad - Problemas NP-Completos. Algoritmos y Estructuras de Datos III
Complejidad - Problemas NP-Completos Algoritmos y Estructuras de Datos III Teoría de Complejidad Un algoritmo eficiente es un algoritmo de complejidad polinomial. Un problema está bien resuelto si se conocen Más detalles METAHEURÍSTICA ACO APLICADA A PROBLEMAS DE PLANIFICACIÓN
METAHEURÍSTICA ACO APLICADA A PROBLEMAS DE PLANIFICACIÓN EN ENTORNOS DINÁMICOS de San Pedro M., Pandolfi D., Lasso M., Villagra A. Laboratorio de Tecnologías Emergentes (LabTEm) Proyecto UNPA-29/B084/1 Más detalles Programación de Grúas para Mantención y Construcción de Buques en un Astillero Naval. Uso de Modelo Matemático.
Revista Ingeniería de Sistemas Volumen XXV, Septiembre 2011 Programación de Grúas para Mantención y Construcción de Buques en un Astillero Naval. Uso de Modelo Matemático. Marcelo Guiñez * Lorena Pradenas Más detalles Programación Lineal Entera
Programación Lineal Entera P.M. Mateo y David Lahoz 2 de julio de 2009 En este tema se presenta un tipo de problemas formalmente similares a los problemas de programación lineal, ya que en su descripción Más detalles Inteligencia Artificial. Visiones: Árboles de Búsqueda Técnicas Look-Back Técnicas Look-Ahead. Elizabeth Montero Ureta.
Inteligencia Artificial Elizabeth Montero Ureta Departamento de Informática Universidad Técnica Federico Santa María Campus Santiago 1 1er Semestre 2009 1/18 2/18 Visiones: Tiene una solución? Encontrar Más detalles Algoritmo de dispatching para la programación de la producción en una planta de fabricación Pág. 1. Resumen
Algoritmo de dispatching para la programación de la producción en una planta de fabricación Pág. 1 Resumen Este proyecto tiene por objetivo resolver un problema real de secuenciación de operaciones de Más detalles DISEÑO DE METAHEURÍSTICOS HÍBRIDOS PARA PROBLEMAS DE RUTAS CON FLOTA HETEROGÉNEA (2 Parte) : GRASP Y CONCENTRACIÓN HEURÍSTICA
DISEÑO DE METAHEURÍSTICOS HÍBRIDOS PARA PROBLEMAS DE RUTAS CON FLOTA HETEROGÉNEA (2 Parte) : GRASP Y CONCENTRACIÓN HEURÍSTICA Cristina R. Delgado Serna Departamento de ECONOMÍA (Área de Economía Aplicada) 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 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 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 Algoritmos de planificación basados en restricciones para la sustitución de componentes defectuosos Irene Barba Rodríguez, 48861238S irenebr@us.
Algoritmos de planificación basados en restricciones para la sustitución de componentes defectuosos Irene Barba Rodríguez, 48861238S irenebr@us.es Supervised by Prof. Dr. Carmelo del Valle Sevillano Thesis Más detalles Metodologías Analíticas y Heurísticas para la Solución del Problema de Programación de Tareas con Recursos Restringidos (RCPSP): una revisión.
Ingeniería y Ciencia ISSN:1794-9165 ISSN-e: 2256-4314 ing. cienc., vol. 10, no. 19, pp. 247 271, enero-junio. 2014. http://www.eafit.edu.co/ingciencia This a open-access article distributed under the terms Más detalles ENTORNO PARA LA PLANIFICACION DE LA PRODUCCION DE SISTEMAS DE FABRICACION FLEXIBLES
ENTORNO PARA LA PLANIFICACION DE LA PRODUCCION DE SISTEMAS DE FABRICACION FLEXIBLES Mercedes E. Narciso Farias, Miquel Angel Piera i Eroles Unidad de Ingeniería de Sistemas y Automática. Universidad Autónoma Más detalles Razonamiento. con. Restricciones. Esquema Global. Tutorial CAEPIA 2003. 1. Introducción - Definiciones - Ejemplos
Esquema Global Razonamiento con Restricciones Tutorial CAEPIA 2003 Javier Larrosa Dep. LSI, UPC, Barcelona Pedro Meseguer IIIA, CSIC, Bellaterra 1. Introducción - Definiciones - Ejemplos 2. Métodos de Más detalles 3. Consideremos el puzzle-8 descrito en clase y sea el estado objetivo, como de costumbre,
E.T.S.I. INFORMÁTICA 4º CURSO. INTELIGENCIA ARTIFICIAL. UNIVERSIDAD DE MÁLAGA Dpto. Lenguajes y Ciencias de la Computación RELACIÓN DE PROLEMAS. ÚSQUEDAS CON ÁROL.. Un móvil puede situarse en los nodos Más detalles ASALBP: Alternative Subgraphs Assembly Line Balancing Problem *
IX Congreso de Ingeniería de Organización Gijón, 8 y 9 de septiembre de 2005 ASALBP: Alternative Subgraphs Assembly Line Balancing Problem * Liliana Capacho Betancourt 1, Rafael Pastor Moreno 2 1 Dpto Más detalles MODELO JERÁRQUICO PARA EL JOB SHOP FLEXIBLE
!#"$%$$ %!& '($! *)!!#% $)$ +-,/.103254 687/9:6(;=1.1?A@50 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 EL PROBLEMA DE PROGRAMACIÓN Y SECUENCIAMIENTO DE TAREAS EN EL PROCESO DE SECADO EN UN ASERRADERO
Theoria, Vol. 16 (1): 15-22, 2007 ISSN 0717-196X Artículo / Article EL PROBLEMA DE PROGRAMACIÓN Y SECUENCIAMIENTO DE TAREAS EN EL PROCESO DE SECADO EN UN ASERRADERO THE PROBLEM OF TASK SCHEDULING AND SEQUENCING 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 Algoritmo para la secuenciación en el ensamblaje de estructuras mediante robots
Algoritmo para la secuenciación en el ensamblaje de estructuras mediante robots S. Vera Universidad de Sevilla, Sevilla, España, svera@us.es I. Maza Universidad de Sevilla, Sevilla, España, imaza@cartuja.us.es 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 6th International Conference on Industrial Engineering and Industrial Management. XVI Congreso de Ingeniería de Organización. Vigo, July 18-20, 2012
6th International Conference on Industrial Engineering and Industrial Management. XVI Congreso de Ingeniería de Organización. Vigo, July 18-20, 2012 Un algoritmo genético híbrido para el equilibrado de Más detalles Optimización de la programación (scheduling) en Talleres de Mecanizado
UNIVERSIDAD POLITÉCNICA DE MADRID ESCUELA TÉCNICA SUPERIOR DE INGENIEROS AGRÓNOMOS Optimización de la programación (scheduling) en Talleres de Mecanizado TESIS DOCTORAL D. José Eduardo Márquez Delgado Más detalles PREPROCESADO DE DATOS PARA MINERIA DE DATOS
Ó 10.1007/978-3-319-02738-8-2. PREPROCESADO DE DATOS PARA MINERIA DE DATOS Miguel Cárdenas-Montes Frecuentemente las actividades de minería de datos suelen prestar poca atención a las actividades de procesado 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 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 Selección Sexual Discriminatoria en un Algoritmo Evolutivo con una Matriz de Preferencias para la mejora de calidad de los Horarios de Trabajo
Algoritmo de Colonias de Abejas Artificiales para la composición de equipos médicos * José A. Delgado-Osuna 1, Manuel Lozano 2, and Carlos García-Martínez 3 1 H.U. Reina Sofía jantonio.delgado.sspa@juntadeandalucia.es, Más detalles Programación de la producción en sistemas de manufactura tipo taller con el algoritmo combinado cuello de botella móvil y búsqueda tabú
Programación de la producción en sistemas de manufactura tipo taller con el algoritmo combinado cuello de botella móvil y búsqueda tabú Production Programming in Manufacturing Systems (Workshop Type) with Más detalles Un modelo de integración de técnicas de CLAUSURA y CSP de restricciones temporales: Aplicación a problemas de Scheduling
UNIVERSIDAD DE ALICANTE Departamento de Ciencia de la Computación e Inteligencia Artificial Un modelo de integración de técnicas de CLAUSURA y CSP de restricciones temporales: Aplicación a problemas de Más detalles Implementación y análisis de rendimiento de un sistema de planeamiento lineal basado en el modelo MPBH
Implementación y análisis de rendimiento de un sistema de planeamiento lineal basado en el modelo MPBH Tesis para obtener el Título Profesional de Ingeniero de Sistemas Christian Danniel Paz Trillo Miembros Más detalles Planificación y secuenciamiento de procesos por lotes. Prof. Cesar de Prada ISA-UVA
Planificación secuenciamiento de procesos por lotes Prof. Cesar de Prada ISA-UVA Indice Procesos plantas batch Conceptos básicos de secuenciamiento Formulación de problemas de secuenciamiento Resolución 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 GUÍA DOCENTE DE LA ASIGNATURA
GUÍA DOCENTE DE LA ASIGNATURA G655 - Introducción a los Sistemas Inteligentes Grado en Ingeniería Informática Obligatoria. Curso Grado en Matemáticas Optativa. Curso Curso Académico 2014-2015 1 1. DATOS Más detalles Resolución de problemas
Inteligencia en Redes de Comunicaciones Resolución de problemas Julio Villena Román jvillena@it.uc3m.es El problema de resolver problemas La resolución de problemas es uno de los procesos básicos de razonamiento 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 UNIVERSIDAD CATÓLICA DEL NORTE PROGRAMA DE ESTUDIOS I. IDENTIFICACIÓN DE LA ASIGNATURA II. OBJETIVOS GENERALES
UNIVERSIDAD CATÓLICA DEL NORTE PROGRAMA DE ESTUDIOS I. IDENTIFICACIÓN DE LA ASIGNATURA Nombre: Administración de la Producción II Código: CC-983 Fecha Actualización: Marzo 2005 Unidad Responsable: Departamento Más detalles Restricciones. Inteligencia Artificial. Ingeniería Superior en Informática, 4º Curso académico: 2011/2012 Profesores: Ramón Hermoso y Matteo Vasirani
Restricciones Ingeniería Superior en Informática, 4º Curso académico: 2011/2012 Profesores: Ramón Hermoso y Matteo Vasirani 1 Tema 2: Agentes basados en Búsqueda Resumen: 2. Agentes basados en búsqueda Más detalles Análisis Comparativo de Heurísticas para el Problema de Calendarización de Trabajos con Transferencia Cero
Análisis Comparativo de Heurísticas para el Problema de Calendarización de Trabajos con Transferencia Cero Beatriz Pérez Rojas Departamento de Sistemas Computación Instituto Tecnológico de Puebla am120@cs.buap.m Más detalles Resolución del Problema de Set-Covering utilizando un Algoritmo Genético
Resolución del Problema de Set-Covering utilizando un Algoritmo Genético Pablo Itaim Ananias Valparaíso, 20 de Junio del 2005 Resumen El Set Covering Problem (SCP)es un problema clásico, que consiste en Más detalles FLEXIPLAN: UN SISTEMA DE PLANIFICACIÓN DE LA PRODUCCIÓN
27 Congreso Nacional de Estadística e Investigación Operativa Lleida, 8-11 de abril de 2003 FLEXIPLAN: UN SISTEMA DE PLANIFICACIÓN DE LA PRODUCCIÓN Vicente Valls 1, Jose Manuel Belenguer 1, Pilar Lino Más detalles UNIVERSIDAD TECNOLÓGICA DE PEREIRA FACULTAD DE INGENIERÍA ELÉCTRICA PROGRAMA DE MAESTRÍA EN INGENIERÍA ELÉCTRICA
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 1. Introducción RESUMEN
27 Congreso Nacional de Estadística e Investigación Operativa Lleida, 8-11 de abril de 2003 ANÁLISIS COMPARATIVO DEL RENDIMIENTO DE REGLAS DE DESPACHO TRADICIONALES EN UN TALLER DE FLUJO HÍBRIDO CON TIEMPOS Más detalles TEMA 6 PLANIFICACIÓN Y PROGRAMACIÓN DEL PROYECTO
TEMA 6 PLANIFICACIÓN Y PROGRAMACIÓN DEL PROYECTO 99 100 6.1 PREPARACIÓN DEL PROYECTO Una vez que el cliente ha aceptado la oferta presentada y le ha sido notificada la adjudicación del proyecto, la empresa Más detalles Secuenciación de una línea mixed-model mediante un algoritmo exacto Pág. 1. Resumen
Secuenciación de una línea mixed-model mediante un algoritmo exacto Pág. 1 Resumen En una línea de montaje de productos mixtos, aquella que es responsable de la producción de diversas variaciones de un 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 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 CAPÍTULO 2 METODOS PROBABILÍSTICOS
CAPÍTULO 2 METODOS PROBABILÍSTICOS La planeación de movimientos tiene aplicaciones en muchas áreas tales como la robótica, sistemas de realidad virtual y diseño asistido por computadora. Aunque muchos Más detalles Una heurística basada en memoria para el problema del diseño de recorridos en transporte público urbano
Una heurística basada en memoria para el problema del diseño de recorridos en transporte público urbano Antonio Mauttone María E. Urquhart Departamento de Investigación Operativa, Instituto de Computación, Más detalles Investigación de Operaciones (IO) Operations Research
Investigación de Operaciones (IO) Operations Research Dr. Ricardo Soto [ricardo.soto@ucv.cl] [http://www.inf.ucv.cl/ rsoto] Escuela de Ingeniería Informática Pontificia Universidad Católica de Valparaíso Más detalles Algoritmo genético aplicado a la programación en talleres de maquinado
Ingeniería Mecánica. Vol. 15. No. 3, septiembre-diciembre, 2012, p. 201-212 ISSN 1815-5944 Algoritmo genético aplicado a la programación en talleres de maquinado Genetic algorithm applied to scheduling Más detalles Tema 3: Problemas de Satisfacción de Restricciones
Tema 3: Problemas de Satisfacción de Restricciones Universidad de Granada Tema 3: Satisfacción de Restricciones Contenido Problemas de satisfacción de restricciones Métodos de búsqueda Búsqueda local para Más detalles Estrategia evolutiva para el problema de la supersecuencia común más corta
Estrategia evolutiva para el problema de la supersecuencia común más corta Marcela Rivera Martínez Facultad de Ciencias de la Computación, Benemérita Universidad Autónoma de Puebla mrivmar@hotmail.com Más detalles Análisis del NSGA-II para el TSALBP-1/3 cuando existe variación de demanda en una producción mixta
Análisis del NSGA-II para el TSALBP-1/3 cuando existe variación de demanda en una producción mixta Manuel Chica, Óscar Cordón, Sergio Damas y Joaquín Bautista Resumen En este trabajo introducimos la aplicación Más detalles www.fundibeq.org Además, se recomienda su uso como herramienta de trabajo dentro de las actividades habituales de gestión.
DIAGRAMA DE FLECHAS 1.- INTRODUCCIÓN Este documento sirve de guía para el proceso de planificación de proyectos. Describe desde la visualización de la secuencia de acciones a desarrollar en dichos proyectos Más detalles III. BÚSQUEDA Y RESOLUCIÓN DE PROBLEMAS. III.3.
III. BÚSQUEDA Y RESOLUCIÓN DE PROBLEMAS. III.3. Búsquedas con retroceso. III.3.1. Búsquedas con retroceso a ciegas. III.3.1.1. Procedimientos con retroceso. La búsqueda con retroceso, o backtracking, es Más detalles LECCIÓN 6 "TÉCNICAS DE PLANIFICACIÓN Y PROGRAMACIÓN"
LECCIÓN 6 "TÉCNICAS DE PLANIFICACIÓN Y PROGRAMACIÓN" ÍNDICE 6.1. NECESIDAD DE LA PLANIFICACIÓN Y PROGRAMACIÓN. 6.2. PROGRAMACIÓN CLÁSICA: DIAGRAMAS DE GANTT. 6.3. TÉCNICAS BASADAS EN EL USO DE REDES. 6.4. Más detalles Tema 1 Introducción a los Sistemas Basados en el Conocimiento
Tema 1 Introducción a los Sistemas Basados en el Conocimiento Sistemas Basados en el Conocimiento Grado en Ingeniería Informática 1 Referencias Ingeniería del Conocimiento. A. Gómez, N. Juristo, C. Montes, Más detalles Estado del arte en políticas de ubicación de productos en almacén
II International Conference on Industrial Engineering and Industrial Management XII Congreso de Ingeniería de Organización September 3-5, 2008, Burgos, Spain Estado del arte en políticas de ubicación de 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 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 
 resolución 
 Resolución 

Resolución 
 RESOLUCIÓN 
 RESOLUCIÓN