Source: http://docplayer.es/1260159-Estado-del-arte-del-job-shop-scheduling-problem.html
Timestamp: 2017-02-28 10:24:32+00:00

Document:
Estado del Arte del Job Shop Scheduling Problem - PDF
Download "Estado del Arte del Job Shop Scheduling Problem"
Ana Correa Maidana
1 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 17 de mayo de 2006 Resumen En el siguiente trabajo se presenta el estado del arte de uno de los problemas clásicos de la optimización combinatoria y la investigación de operaciones: el Job Shop Scheduling Problem. Se define el problema formalmente y se plantean las principales técnicas de resolución utilizadas desde sus orígenes hace más de 40 años, entre las cuales destacan múltiples algoritmos y heurísticas del campo de la inteligencia artificial. También se introduce un modelo de programación lineal, que hará más fácil la comprensión del problema. Palabras clave: Job shop, scheduling, branch & bound, simulated annealing, tabu search, algoritmos genéticos, heurísticas, local search, bottleneck, priority rules, CSP. 1. Introducción El problema del Job Shop, y en general cualquier problema de scheduling, es un problema de optimización combinatoria. La función del scheduling es la asignación de recursos limitados a tareas a lo largo del tiempo y tiene como finalidad la optimización de uno o más objetivos. Los recursos pueden ser máquinas en un taller, pistas en un aeropuerto, ladrillos en una construcción, unidades de procesamiento en un ambiente computacional, etc. Como tareas se pueden tener operaciones de un proceso de producción, despegues y aterrizajes en un aeropuerto, etapas de un proyecto de ingeniería, ejecuciones de un programa computacional, etc. Cada tarea puede tener diferentes niveles de prioridad, así como tiempos de posibles inicios. Los objetivos pueden tomar varias formas: minimizar los tiempos de finalización de la última tarea, minimizar el número de tareas luego de una fecha de entrega acordada, etc. El Job Shop puede ser un problema difícil (de hecho cae en la categoría de los problemas NPdifícil 1 ) desde el punto de vista técnico como de implementación. El tipo de dificultades encontradas en los aspectos técnicos son similares a las encontradas en otras ramas de optimización combinatoria y modelado estocástico. Las dificultades encontradas desde el punto de vista de la implementación son de distintas clases y están relacionadas al modelado de problemas de scheduling del mundo real y la recuperación de información. La programación de tareas apoya a las principales áreas funcionales de una empresa: El departamento de Producción necesita conocer la secuencia real de productos a fabricar en el día. Por ello, su personal ha de consultar la programación de tareas que resulta tras la planificación maestra de los diferentes productos a fabricar. 1 NP-difícil es el conjunto de los problemas de decisión que contiene los problemas H tales que todo problema L en NP puede ser transformado polinomialmente en H. Esta clase puede ser descrita como conteniendo los problemas de decisión que son al menos tan difíciles como un problema de NP. 12 El departamento de Contabilidad, a partir de la información de la programación y de las fechas de entrega a los clientes, prevé la entrada de ingresos, los costos de cada trabajo y realiza un análisis del cash-flow de la empresa. El departamento de Marketing puede establecer medidas de la eficiencia de la programación para determinar si los tiempos de cumplimentación de los pedidos están aportando una ventaja competitiva y si las entregas se están realizando a tiempo. El conocimiento de los tiempos de entrega de cada pedido permite al departamento de Marketing ofrecer tiempos de entrega más ajustados. Un sistema de información se puede encargar de mantener en base de datos el tiempo de comienzo de cada tarea así como el enrutamiento de las mismas por cada uno de los recursos disponibles. También se puede encargar de realizar el seguimiento de movimiento del producto a través del proceso. Todo lo anterior, dado el mundo globalizado en que vivimos, tiene como objetivo mejorar la rentabilidad y competitividad de empresas y organizaciones, incrementando la eficiencia en la toma de decisiones, pues lo que se busca es la optimización de la asignación de recursos limitados a la ejecución de tareas. Este artículo se estructura de la siguiente forma: la sección 2 presenta una explicación del problema del Job Shop, indicando en qué consiste y sus respectivas variables, restricciones y objetivos de manera general. Además se indican las variantes más conocidas que existen. La siguiente sección contiene lo más importante que se ha hecho hasta ahora con relación al problema, los métodos que se han usado para resolverlo y los mejores algoritmos que se han creado hasta la fecha, mientras que la sección 4 presenta al lector un modelo matemático para el problema. La última parte corresponde a las conclusiones y referencias utilizadas para el desarrollo del texto. 2. Definición del Problema El problema del Job Shop Scheduling, corresponde a un tipo de problema de planificación de tareas, y es un problema de optimización con dichas características; en donde uno de los objetivos principales es la disminución de tiempos en la tarea de planificación. Consiste básicamente en planificar un conjunto de N trabajos {J 1,..., J N } sobre un conjunto de M recursos o máquinas físicas {R 1,..., R M }. Cada trabajo J i consta de un conjunto de operaciones o tareas {θ i1,..., θ im } que deben ser ejecutadas de forma secuencial. Cada tarea θ ij tiene asociado un tiempo de procesamiento sin interrupción de du ij unidades de tiempo durante el cual requiere del 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 término más tardío, lo que obliga a que los tiempos de inicio de las tareas tomen valores en dominios finitos. Cabe considerar que las operaciones de un mismo trabajo deben ejecutarse en un orden determinado, de forma que θ (i+1)j no puede comenzar hasta que θ ij haya terminado completamente. Además, las operaciones que comparten una misma máquina son no interrumpibles y mutuamente exclusivas. Las restricciones del problema se pueden resumir de la siguiente manera: Una tarea no puede visitar una misma máquina dos veces. No hay restricciones de precedencia entre operaciones de distintas tareas. Las operaciones no se pueden interrumpir. Cada máquina puede procesar sólo una tarea a la vez. No se especifican ni release times (fecha de tarea lista a ser procesada) ni due dates (fecha de entrega). El objetivo consiste en encontrar una planificación factible, es decir, una asignación de tiempos de inicio st ij para cada una de las tareas, que minimice el makespan (C max) o tiempo de finalización de la última tarea. El job shop se representa a través de un grafo conocido como grafo disyuntivo 2, el que se muestra en la figura 1. Las variantes para el problema del scheduling se relacionan con la secuencia de ordenación de las operaciones, denominada patrón de flujo. Si todos los trabajos tienen la misma secuencia de ordenación 2 En inglés disjunctive graph. 23 Figura 1: Representación gráfica de un problema con 3 trabajos de 3 tareas. El tiempo mínimo de inicio es 0 para todos ellos y el tiempo máximo de fin es 15. Los arcos están etiquetados con el costo de la tarea de origen. de las operaciones, el problema se conoce como flow-shop, mientras que si existe una ordenación determinada para cada uno de los trabajos y también hay un orden de uso de cada uno de los recursos por parte de las operaciones, el problema se denomina permutation flow-shop. Si no existe ninguna restricción de ordenamiento, el problema pasa a llamarse open-shop. El job-shop corresponde al problema en el cual cada trabajo tiene una ordenación determinada. 3. Estado del Arte La investigación en teoría de scheduling ha venido desarrollándose en los últimos 40 años y ha sido objeto de mucha literatura con técnicas que van desde reglas de despacho (dispatching) no refinadas, hasta algoritmos paralelos de ramificación y poda altamente sofisticados, heurísticas basadas en cuellos de botella (bottleneck based heuristics), y algoritmos genéticos paralelos. Además, dichas técnicas han sido formuladas desde un amplio espectro de investigadores, desde científicos de gestión, hasta expertos en producción. No obstante, con la aparición de nuevas metodologías, como redes neuronales y computación evolutiva, investigadores de campos como la biología, genética y neurofisiología han tenido también contribuciones regulares a la teoría de scheduling, poniendo de manifiesto la naturaleza multidisciplinar de este campo. Diversas opiniones existen con respecto al origen del Job Shop Scheduling Problem. B. Roy y B. Sussman en 1964 fueron los primeros en proponer la representación mediante el grafo disyuntivo y Egon Balas en 1959 fue el primero en aplicar un acercamiento enumerativo basado en este grafo. Sin embargo existen trabajos anteriores: B. Giffler y G. L. Thompson propusieron en 1960 un algoritmo de reglas de despacho de prioridad, J. R. Jackson en 1956 generalizó el algoritmo del flow-shop de S. M. Johnson de 1954 al algoritmo del job-shop y en 1955, S. B. Akers y J. Friedman aplicaron un modelo de álgebra booleana para representar secuencias de procesamiento. Estas investigaciones trataron con un problema consistente de n trabajos, m máquinas y relaciones de precedencia, por lo cual cada trabajo se procesa a través de las máquinas en un orden diferente. Aunque no está claro quién debería llevarse el crédito por haber propuesto por primera vez el Job Shop Problem, se acepta que el libro Industrial Scheduling editado en 1964 por Muth y Thompson, constituye la base para la mayoría de las investigaciones que siguieron. Las técnicas de resolución del Job Shop Problem se pueden dividir en dos categorías; las técnicas de optimización, que producen una solución globalmente óptima, pero requiere un tiempo de computación muy alto, y las técnicas de aproximación, que proporcionan una buena solución en un tiempo aceptable. A continuación se describen las técnicas más importantes. 34 3.1. Técnicas de optimización En las técnicas de optimización, en general, la complejidad temporal crece exponencialmente con respecto al tamaño de la entrada. Los métodos obtenidos construyen una solución óptima a partir de los datos del problema siguiendo una serie de reglas que determinan de manera exacta el orden de procesamiento Programación lineal entera mixta Propuesto inicialmente en 1960 por Alan Manne, este es un procedimiento muy utilizado en otros contextos de la programación matemática, sin embargo no resulta apropiado en este ámbito ya que su formulación lineal entera mixta da lugar a tiempos de ejecución elevados en problemas de tamaño real, lo cual la hace poco aconsejable Ramificación y poda (Branch & Bound) Las técnicas de ramificación y poda hacen uso de una estructura de árbol construida dinámicamente, como forma de representar el espacio de todas las secuencias posibles. La búsqueda comienza en el nodo raíz y se continúa hasta llegar a un nodo hoja. Cada nodo en un nivel p de la búsqueda representa una secuencia parcial de p operaciones. Desde un nodo no seleccionado, la operación de ramificación determina el siguiente conjunto de posibles nodos a partir del cual puede progresar la búsqueda. Las dos estrategias de ramificación más comunes son la Generación de Agendas Activas (Generating Active Schedules: GAS), y Ajuste de Conflictos Secuenciales (Settling Essential Conflicts: SEC). Cada nodo consiste en un secuenciamiento parcial de las operaciones sobre los recursos, pero mientras que la primera estrategia de ramificación fija el conjunto de operaciones siguientes a secuenciar, en la segunda se determina si una operación debería secuenciarse antes o después de otra. El procedimiento de poda selecciona la operación con la que continuará la búsqueda y se basa en una estimación de una cota inferior y la mejor cota superior alcanzada hasta el momento. En los métodos de ramificación y poda es esencial afinar las cotas, ya que eso previene la necesidad de buscar en secciones grandes del espacio de soluciones Recocido simulado (Simulated Annealing) La denominación del algoritmo, Recocido Simulado, o Simulated Annealing, proviene de la estrecha analogía que guarda con el proceso del Recocido tal y como se usa en metalurgia. Éste consiste en que un metal fundido se va enfriando lentamente de manera que sus moléculas van adoptando poco a poco una configuración de mínima energía. Cuando comienza el proceso, a alta temperatura, las moléculas vibran y se desplazan caóticamente adoptando todo tipo de configuraciones en la estructura del metal de la que forman parte. A medida que la temperatura disminuye se va ralentizando el movimiento de las moléculas y éstas, de acuerdo con la Termodinámica, tienden a adoptar paulatinamente las configuraciones de menor energía, siendo ésta nula en el cero absoluto. El Recocido Simulado intenta realizar numéricamente un proceso análogo al del recocido metalúrgico. El espacio de configuraciones no vendrá ya dado por las posiciones de las moléculas, sino por los valores de una variable de interés, que en el caso del Job Shop será la secuencia de tareas que se desean procesar, mientras que el papel de la energía lo asumirá la función que se intenta minimizar, costo o tiempo de realización de tareas, por ejemplo Búsqueda tabú (Tabu Search) Es una técnica de optimización iterativa global, que consiste en un procedimiento determinístico que restringe la búsqueda y evita los mínimos locales, almacenando la historia de búsqueda en memoria. Se prohiben movimientos entre vecinos que cumplan ciertas propiedades, con objeto de guiar el proceso de búsqueda para no duplicar soluciones previamente obtenidas. Una función de memoria a corto plazo permite olvidos estratégicos convirtiendo en prohibido los t movimientos más recientes. Sin embargo, el estado de un movimiento no es absoluto, ya que es posible seleccionar un movimiento tabú si alcanza un determinado nivel de calidad. También se dispone de funciones de memoria a largo plazo que pueden aplicarse para proporcionar una exploración más amplia del espacio de búsqueda. Finalmente existen estrategias a medio plazo o intermedias basadas en la modificación de las reglas de elección que favorecen 45 la elección de movimientos y soluciones consideradas buenas históricamente, de forma que crean zonas de atracción del dominio de búsqueda e intensifican la búsqueda en dichas regiones. Los métodos a largo plazo diversifican la búsqueda en áreas no exploradas previamente. El algoritmo de búsqueda tabú aplicada al Job Shop Problem genera vecinos mediante la inversión de arcos que unen tareas adyacentes en el camino crítico. Después de que un arco (v w) ha sido invertido, se introduce el paso inverso (w v) en la lista tabú, consistente en una lista de longitud definida que contiene los desplazamientos prohibidos. Cada vez que se realiza un número n de iteraciones, se modifica aleatoriamente la longitud de la lista tabú. En cada iteración se evalúan todas las soluciones del vecindario que no se encuentran en la lista tabú, calculando para cada una el valor de C max y seleccionándose la más prometedora Algoritmos genéticos (Genetic algorithms) Los algoritmos genéticos imitan el procedimiento de la selección natural sobre el espacio de soluciones del problema considerado. Se basan en la creación de generaciones sucesivas de individuos representativos de posibles soluciones al problema. Los nuevos individuos se generan cruzando parejas seleccionadas dando mayor probabilidad a aquéllas soluciones que mejor valor de la función objetivo han obtenido en la generación anterior (individuos más adaptados al entorno). En la literatura existen numerosas propuestas que resuelven el Job Shop Problem mediante el uso de Algoritmos Evolutivos. Bierwirth y Mattfeld proponen varios Algoritmos Genéticos con distintas estrategias de evolución y un esquema de codificación denominado permutaciones con repetición. De acuerdo con este esquema un cromosoma es en principio una permutación del conjunto de tareas en el que cada tarea viene representada simplemente por el número del trabajo al que pertenece. Por ejemplo, si tenemos un problema con 3 trabajos de 3 tareas cada uno, un cromosoma puede ser el siguiente ( ). En esta codificación el primer 1 representa la primera tarea del primer trabajo, el segundo 1 la segunda y así sucesivamente. De este modo las tareas de cada trabajo aparecen representadas en el orden de ejecución secuencial, mientras que las tareas que requieren al mismo recurso pueden aparecer en cualquier orden. La ventaja principal que presenta este esquema de codificación es que permite diseñar operadores genéticos eficientes, de cruce y mutación, que producen cromosomas factibles Técnicas de aproximación Si bien los métodos de aproximación no garantizan una solución exacta, son capaces de obtener soluciones muy cercanas al óptimo, con unos tiempos de cálculo moderados, y por ello más adecuados para problemas grandes. La importancia de los métodos de aproximación radica en que las heurísticas inspiradas en fenómenos naturales y resolución inteligente de problemas resultan muy apropiadas para problemas combinatorialmente difíciles, proporcionando un adecuado enlace bilateral entre la investigación de operaciones y la inteligencia artificial Reglas de prioridad de despacho (Priority dispatch rules) Las reglas de prioridad son probablemente las reglas heurísticas aplicadas con mayor frecuencia para resolver problemas de scheduling, esto se debe a su fácil implementación y a su baja complejidad de tiempo. Los algoritmos de Giffler y Thompson se pueden considerar como la base de todas las heurísticas basadas en reglas de prioridad. Giffler y Thompson han propuesto dos algoritmos para generar schedules: procedimientos de generación de schedules activos y schedules nondelay. Un schedule nondelay tiene la propiedad de que ninguna máquina permanece ociosa si hay un trabajo disponible para su procesamiento. Un schedule activo tiene la propiedad de que ninguna operación se puede iniciar tempranamente sin retrasar otro trabajo. Los schedules activos forman un conjunto más grande que incluye como subconjunto a los schedules nondelay. El procedimiento de generación de Giffler y Thompson explora el espacio de búsqueda por medio de una estructura de árbol. Los nodos en el árbol representan los schedules parciales, los arcos representan las posibles elecciones, y las hojas del árbol son el conjunto de schedules. Para un schedule parcial, el algoritmo esencialmente identifica todos los conflictos de procesamiento, es decir, identifica operaciones que compiten por la misma máquina, y en cada etapa usa un procedimiento de enumeración para resolver esos conflictos bajo todas las formas posibles. En contraste, las heurísticas resuelven esos 56 conflictos con reglas de prioridad de despacho; las heurísticas especifican una regla de prioridad para seleccionar una operación entre las operaciones en conflicto Heurísticas basadas en cuellos de botella (Bottleneck based heuristics) Si bien durante bastante tiempo los únicos métodos de aproximación viables han sido las reglas de prioridad de despacho, recientemente con la llegada de computadores más potentes, así como en el énfasis puesto en nuevas técnicas cuidadosamente analizadas, diseñadas e implementadas, ha dado lugar a aproximaciones más sofisticadas, llamadas heurísticas basadas en cuellos de botella. Un ejemplo de esta aproximación es el Shifting bottleneck procedure (SBP). Un SBP se caracteriza por las siguientes tareas: identificación del subproblema, selección del cuello de botella, solución del subproblema, y reoptimización del scheduling. La estrategia real implica relajar el problema de scheduling n m, en m problemas de 1 máquina y resolver cada subproblema cada vez de forma iterativa usando la aproximación de Carlier. Cada una de las soluciones se compara con las demás y se ordenan las máquinas según su solución. La máquina no secuenciada que tiene la solución mayor se identifica como la máquina que provoca el cuello de botella. SPB secuencia dicha máquina basándose en las que ya han sido calculadas, ignorando el resto de máquinas no secuenciadas. La selección de la máquina que constituye el cuello de botella viene motivada por la conjetura de que el scheduling en etapas posteriores podría deteriorar el tiempo de realización del scheduling (makespan). Cada vez que una máquina se identifica como de cuello de botella, todas las máquinas que yan han sido secuenciadas, y que son susceptibles de mejoras, se reoptimizan localmente resolviendo el problema de una máquina de nuevo. La principal contribución de esta aproximación es la forma en que se usa la relajación de una máquina para decidir el orden en el que las máquinas deben ser secuenciadas Métodos de búsqueda local (Local search methods) Este procedimiento está basado en la suposición de que es posible encontrar una secuencia de soluciones entre la solución inicial y la final tal que cada una de ellas es ligeramente diferente a la inmediatamente anterior. Tiene la ventaja de que en poco tiempo puede encontrar soluciones suficientemente buenas para un conjunto amplio de problemas combinatoriales. Este procedimiento puede ofrecer una medida de la bondad de la solución encontrada, pero no garantiza que la solución obtenida sea el óptimo global del problema considerado. Un concepto asociado a la búsqueda local es la descripción del conjunto de soluciones parecidas a una dada, denominado vecindario. Dos soluciones son vecinas si una puede ser obtenida a partir de la otra intercambiando el orden entre dos tareas consecutivas en un mismo recurso perteneciendo ambas al camino crítico. Una estrategia de búsqueda local bastante utilizada es la denominada avariciosa, la cual parte de una solución inicial generada aleatoriamente o mediante un algoritmo heurístico y evalúa todas las soluciones que se encuentran en su vecindario, escogiendo de entre las que mejoren el valor de la función objetivo la más prometedora. La repetición de este proceso terminaría en un óptimo, local o global, pero en todo caso una solución mejor que cualquiera de las de su vecindario y lógicamente mejor que la solución inicial Clausura y satisfacción de restricciones (CSP) Un problema de scheduling puede caracterizarse como un conjunto de restricciones temporales, y por lo tanto, las técnicas desarrolladas en el marco de los problemas de Satisfacción de restricciones (CSP - Constraint Satisfaction Problems), y más concretamente, sobre restricciones temporales, pueden aplicarse para resolver problemas de scheduling. Principalmente se utilizan dos procesos típicos: la clausura, como técnica deductiva de nuevas restricciones derivadas, y técnicas de búsqueda CSP, guiadas por heurísticas. Una propuesta reciente consiste en un nuevo modelo de resolución de restricciones temporales que integra ambas técnicas (clausura y CSP) de forma efectiva, intentando aprovechar las ventajas de cada una de ellas. Adicionalmente, el modelo propuesto permite la definición y aplicación de nuevas heurísticas que, por una parte, permiten limitar considerablemente el número de disyunciones de la red y, por otra, permiten dirigir más eficientemente el proceso de búsqueda. 67 Numerosas son las pruebas que se han realizado para determinar qué algoritmo es mejor frente a otros ante determinados parámetros y circunstancias, concluyéndose que -por lo general- los algoritmos genéticos y las técnicas de búsqueda local presentan una ventaja con respecto a los demás. 4. Modelo Matemático Muchos investigadores reconocen que los problemas de scheduling pueden ser resueltos óptimamente utilizando técnicas de programación matemática y uno de los modelos matemáticos más comunes del Job Shop Problem es la programación lineal entera mixta, propuesto por Alan Manne en Se compone de un conjunto de restricciones lineales y una función objetivo lineal, pero con la restricción adicional que algunas variables de decisión (y ipk ) son enteras. Las variables enteras son binarias y se usan para implementar las restricciones disyuntivas, es decir, que ninguna máquina pueda realizar más de una operación y ninguna operación pueda ser realizada en más de una máquina al mismo tiempo. K corresponde a un valor arbitrario grande que debe ser mayor que la suma de los tiempos de procesamiento de todas las operaciones menos el tiempo más pequeño. El modelo se representa de la siguiente manera: Sea t ik : tiempo de inicio de cada operación. J: conjunto de n trabajos a ser procesados. M: conjunto de m recursos o máquinas. O ik : operación del trabajo J i que debe ser procesado en la máquina M k por un período ininterrumpido de tiempo τ ik. Minimizar C max = max(t ik + τ ik ) : J i J, M k M sujeto a: tiempos de inicio t ik 0 {i, p} J {k, h} M restricción de precedencia t ik t ih τ ih si O ih precede a O ik restricción disyuntiva t pk t ik + K(1 y ipk ) τ ik y ipk = 1, si O ik precede a O pk, t ik t pk + K(y ipk ) τ pk y ipk = 0, en otro caso! nx mx donde K > τ ik min(τ ik ) i=1 k=1 En este modelo existen 2nm + n(n 1)m 2 variables, de las cuales n(n 1)m 2 son binarias. El número de restricciones es n(m 1) + n(n 1)m + 2nm. Si n tareas son realizadas por m máquinas, entonces existen potencialmente (n!) m secuencias, aunque muchas de ellas serán infactibles debido a las varias restricciones. De esta manera, un problema con n = 20 y m = 10 tiene 7, posibles soluciones. 5. Conclusiones En este trabajo se ha dado una motivación del problema del Job Shop Scheduling, el cual surge en una amplia variedad de ámbitos, tales como la programación de procesos en una industria, horarios de despegues y aterrizajes en un aeropuerto, los tiempos de entrega de pedidos en una empresa, etc. Es muy importante destacar que un problema que a simple vista parece tan sencillo es uno de los problemas que mayor tiempo se le ha dedicado a su estudio e investigación durante las últimas décadas. Se dieron a conocer algunas metodologías, categorizándolas según su método de resolución en técnicas de optimización y técnicas de aproximación. Entre las técnicas de optimización se encuentran la programación lineal entera mixta, ramificación y poda, recocido simulado, búsqueda tabú y algoritmos genéticos. Por su parte, entre las técnicas de aproximación se hallan las reglas de prioridad de despacho, las heurísticas basadas en cuellos de botella, los métodos de búsqueda local y las técnicas de clausura y satisfacción de restricciones. También existen varias técnicas híbridas que rescatan lo mejor de los algoritmos y heurísticas señaladas. Numerosas son las pruebas que se han realizado para determinar qué algoritmo es mejor frente a otros ante determinados parámetros y circunstancias, concluyéndose que -por lo general- los algoritmos genéticos y las técnicas de búsqueda local presentan una ventaja con respecto a los demás. 78 A pesar de los varios años que se lleva estudiando este problema, aún queda mucho por hacer. Se ha expuesto al lector una base para el desarrollo de futuros trabajos en este apasionante tema. Referencias Alan S. Manne. On the Job-Shop Scheduling Problem. [http://cowles.econ.yale.edu/p/ cp/p01a/p0145.pdf] Anant Singh Jain, Sheik Meeran. A state of the art review of the job-shop scheduling techniques. [http://www.cs.umbc.edu/671/fall01/papers/jain.ps] Anant Singh Jain, Sheik Meeran. Deterministic Job-Shop Scheduling: Past, Present and Future. [http://citeseer.ist.psu.edu/jain98deterministic.html] Anant Singh Jain, Sheik Meeran. Job-Shop scheduling using neural networks. [http://citeseer. ist.psu.edu/ html] Christian Artigues, Dominique Feillet. A branch and bound method for the job-shop problem with sequence-dependent setup times. [http://www.lia.univ-avignon.fr/fich_art/673-aor_ MISTA.pdf] Dirk C. Mattfeld, Christian Bierwirth. A Search Space Analysis of the Job Shop Scheduling Problem. [http://citeseer.ifi.unizh.ch/mattfeld99search.html] Juan Ángel Álvarez Vázquez. Un algoritmo Branch & Bound para problemas de Job Shop Scheduling. [http://www.chapingo.mx/cr/acad/jangel/examengradomcc.ppt] María Isabel Alfonso Galipienso. Un modelo de integración de técnicas de CLAUSURA y CSP de restricciones temporales: Aplicación a problemas de Scheduling. [http://www.dccia.ua.es/ eli/tesis.pdf] María Isabel Alfonso Galipienso, Federico Barber. Combinación de procesos de clausura y CSP para la resolución de problemas de scheduling. [http://ltcs.uned.es:8080/aepia/uploads/ 9/154.pdf] María Isabel Alfonso Galipienso, Federico Barber. Nuevas heurísticas y medidas de textura para resolver problemas de scheduling mediante clausura y CSP. [http://www.dsic.upv.es/ users/ia/gps/papers/caepia 01-csp.pdf] María Sierra Sánchez, Ramiro Varela Arias. Búsqueda Heurística para Problemas de Scheduling. [http://io.us.es/cio2005/items/ponencias/188.pdf] P. Pongcharoen, C. Hicks, P.M. Braiden, D.J. Stewardson. Determining optimum Genetic Algorithm parameters for scheduling the manufacturing and assembly of complex products. [http: //rogue.ncl.ac.uk/file_store/nclep_ pdf] Pedro Sánchez Martín, Santiago López de Haro. Programación de tareas, un reto diario en la empresa. [http://www.iit.upco.es/ santilh/pfc_sec/proyecto/articulo_tecnico.pdf] Ramiro Varela, Javier Blanco, Camino Rodríguez, Jorge Puente, César Alonso. Combinación de Algoritmos Evolutivos y Técnicas Heurísticas para Problemas de Scheduling. [http://decsai. ugr.es/ lcv/rnpst/eventos/wsib02-papers/3ramirovarela.pdf] Santiago López de Haro, Pedro Sánchez Martín, Javier Conde Collado. Secuenciación de tareas mediante metaheurísticos. [http://www.iit.upcomillas.es/docs/iit a.pdf] Welf G. Schneider. Job shop scheduling with stochastic job precedence constraints. [http://www. ubka.uni-karlsruhe.de/cgi-bin/psview?document=1995/wiwi/1&format=1&search= %2f1995%2fwiwi%2f1] Zuleyka Díaz Martínez, José Fernández Menéndez, Paloma Martínez Almodóvar. Secuenciación de tareas en el ámbito de la producción: Una aplicación del algoritmo de recocido simulado. [http:// 8 Documentos relacionados
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 Scheduling Problem. Cuándo y dónde debo hacer cada trabajo?
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 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 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 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 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 Búsqueda Heurística para Problemas de Scheduling *
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 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 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 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 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 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 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 TÉCNICAS DE PLANIFICACIÓN Y CONTROL DE PROYECTOS 1
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 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 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 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 Algoritmos Genéticos Y
&$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 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 ALGORITMOS GENÉTICOS PARA LA RESOLUCIÓN DE PROBLEMAS PRÁCTICOS DE SCHEDULING
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 Programación de Sistemas Productivos
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 Metaheurísticas: una visión global *
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 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 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 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 Fundamentos de Investigación de Operaciones Asignación y Vendedor Viajero
Fundamentos de Investigación de Operaciones y Vendedor Viajero 23 de mayo de 2004 Si bien la resolución del problema de transporte mediante tableau parece ser muy expedita, existen ciertos tipos de problemas Más detalles Métodos Heurísticos en Inteligencia Artificial
Métodos Heurísticos en Inteligencia Artificial Javier Ramírez rez-rodríguez Ana Lilia Laureano-Cruces Universidad Autónoma Metropolitana Métodos Heurísticos en Inteligencia Artificial Los problemas de 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 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 Nombre de la asignatura: Inteligencia Artificial. Créditos: 2-2 - 4. Aportación al perfil
Nombre de la asignatura: Inteligencia Artificial Créditos: 2-2 - 4 Aportación al perfil Diseñar e implementar interfaces hombre- máquina y máquinamáquina para la automatización de sistemas. Identificar Más detalles Inteligencia Artificial para desarrolladores Conceptos e implementación en C#
Introducción 1. Estructura del capítulo 19 2. Definir la inteligencia 19 3. La inteligencia de los seres vivos 22 4. La inteligencia artificial 24 5. Dominios de aplicación 26 6. Resumen 28 Sistemas expertos 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 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 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 Optimización de consultas Resumen del capítulo 14
Optimización de consultas Resumen del capítulo 14 Libro: Fundamentos de Bases de Datos Silberschatz et al. 5ed. Dr. Víctor J. Sosa Agenda 1. Visión general 2. Estimación de las estadísticas de los resultados 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 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 Diseño de redes viales urbanas usando algoritmos genéticos. M. Angélica Pinninghoff J.* Eduardo Matthews D. * Héctor Díaz C.
Diseño de redes viales urbanas usando algoritmos genéticos M. Angélica Pinninghoff J.* Eduardo Matthews D. * Héctor Díaz C. e-mail: mapinnin@inf.udec.cl * Departamento de Ingeniería Informática y Ciencias 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 Algoritmos para CSP 1
Algoritmos para CSP 1 1. Técnicas de Consistencia, o Inferenciales I. Inferencia, o consistencia completa Proceso que permite la síntesis de todas las restricciones de un problema en una única restricción 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 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 Resolución de Problemas
Introducción Resolución de Problemas La resolución de problemas es una capacidad que consideramos inteligente Somos capaces de resolver problemas muy diferentes Encontrar el camino en un laberinto Resolver Más detalles ETSIINGENIO 2009 DIBUJO DE GRAFOS MEDIANTE ALGORITMOS GENÉTICOS
ETSIINGENIO 2009 DIBUJO DE GRAFOS MEDIANTE ALGORITMOS GENÉTICOS EtsiIngenio Inteligencia Artificial 1 Raposo López Alejandro Sánchez Palacios Manuel Resumen dibujo de grafos mediante algoritmos genéticos 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 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 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 Descripción inicial del sistema. Descripción final del sistema. Estado 1 Estado 2 Estado n
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 BALANCEO DE CARGA ACADÉMICA EN EL DISEÑO DE UN CURRÍCULUM BASADO EN COMPETENCIAS
BALANCEO DE CARGA ACADÉMICA EN EL DISEÑO DE UN CURRÍCULUM BASADO EN COMPETENCIAS Martín G. Solar Monsalves Facultad de Ciencias de la Ingeniería Universidad Austral de Chile, Valdivia, Chile. Casilla 567, Más detalles 9.1.Los sistemas expertos. 9.2.Las redes neuronales artificiales. 9.3.Sistemas de inducción de reglas y árboles de decisión.
TEMA 9 TÉCNICAS DE INTELIGENCIA ARTIFICIAL PARA EL ANÁLISIS DE LA INFORMACIÓN CONTABLE 9.1.Los sistemas expertos. 9.2.Las redes neuronales artificiales. 9.3.Sistemas de inducción de reglas y árboles de 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 Simulación ISC. Profr. Pedro Pablo Mayorga
Simulación ISC Profr. Pedro Pablo Mayorga Ventajas 1. Es un proceso relativamente eficiente y flexible. 2. Puede ser usada para analizar y sintetizar una compleja y extensa situación real, pero no puede 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 Algoritmos Genéticos
Introducción a la Computación Evolutiva Tercera Clase: Algoritmos Genéticos Algoritmos Genéticos Desarrollados en USA durante los años 70 Autores principales: J. Holland, K. DeJong, D. Goldberg Aplicados 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 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 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 PLANIFICACIÓN TEMPORAL DE PROYECTOS
PLNIFIIÓN TEMPORL E PROYETOS 1. Introducción. La planificación temporal según los estándares 3. Técnicas de descomposición estructurada (ver presentación específica) 4. Métodos de planificación temporal Más detalles DEPARTAMENTO DE INGENIERÍA EN SISTEMAS Y COMPUTACIÓN OPCIÓN I
1INSTITUTO TECNOLÓGICO DE CIUDAD MADERO DEPARTAMENTO DE INGENIERÍA EN SISTEMAS Y COMPUTACIÓN OPCIÓN I TESIS: Desarrollo de Algoritmos de Retroceso Aplicados a la solución del Problema del Diseño de la Más detalles INGENIERIA EN INGENIERÍA EN SISTEMAS COMPUTACIONALES CLAVE MATERIA OBJETIVO
INGENIERIA EN INGENIERÍA EN SISTEMAS COMPUTACIONALES CLAVE MATERIA OBJETIVO SCE - 0418 SCM - 0414 SCC-0428 ACM - 0403 SCB - 0421 SCV - 0407 ACU-0402 Introducción a la ingeniería en sistemas computacionales 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 ALGORITMOS EVOLUTIVOS APLICADOS A PROBLEMAS DE DISEÑO DE REDES CONFIABLES
ALGORITMOS EVOLUTIVOS APLICADOS A PROBLEMAS DE DISEÑO DE REDES CONFIABLES Autor: Ing. Héctor Enrique Magnago Director Local: Lic. Francisco Javier Díaz Director Externo: Mg. José Luís Hernández Tesis presentada Más detalles Unidad Académica Profesional UAEM Tianguistenco, Paraje El Tejocote, San Pedro Tlaltizapán, Tianguistenco, México CP 52640
Estudio de Tres Algoritmos Heurísticos para Resolver un Problema de Distribución con Ventanas de Tiempo: Sistema por Colonia de Hormigas, Búsqueda Tabú y Heurístico Constructivo de una Ruta Manuel González Más detalles Modelado de flujo en redes. Jhon Jairo Padilla A., PhD.
Modelado de flujo en redes Jhon Jairo Padilla A., PhD. Conceptos básicos Demanda o volumen de Demanda: Es el tráfico que están requiriendo los usuarios de una red. Para transportar el volumen de demanda 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 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 Apuntes de Matemática Discreta 6. Relaciones
Apuntes de Matemática Discreta 6. Relaciones Francisco José González Gutiérrez Cádiz, Octubre de 2004 Universidad de Cádiz Departamento de Matemáticas ii Lección 6 Relaciones Contenido 6.1 Generalidades..................................... 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 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 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 ADM-OPERACIONES: PERT - CPM
1. Definición Conceptual : ADMINISTRACIÓN DE PROYECTOS PERT - CPM Un Proyecto es la búsqueda de la solución inteligente al planeamiento de un problema tendente a resolver una necesidad humana. En forma Más detalles Redes de Kohonen y la Determinación Genética de las Clases
Redes de Kohonen y la Determinación Genética de las Clases Angel Kuri Instituto Tecnológico Autónomo de México Octubre de 2001 Redes Neuronales de Kohonen Las Redes de Kohonen, también llamadas Mapas Auto-Organizados Más detalles Estructuras de Control - Diagrama de Flujo
RESOLUCIÓN DE PROBLEMAS Y ALGORITMOS Ingeniería en Computación Ingeniería en Informática UNIVERSIDAD NACIONAL DE SAN LUIS DEPARTAMENTO DE INFORMÁTICA AÑO 2015 Índice 1. Programación estructurada 2 1.1. 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 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 LA INVESTIGACIÓN OPERATIVA EN LAS LICENCIATURAS DE ECONOMÍA Y DE ADMINISTRACIÓN Y DIRECCIÓN DE EMPRESAS
LA INVESTIGACIÓN OPERATIVA EN LAS LICENCIATURAS DE ECONOMÍA Y DE ADMINISTRACIÓN Y DIRECCIÓN DE EMPRESAS Ibar Alonso, Raquel Dpto. Métodos Cuantitativos para la Economía Facultad de Ciencias Económicas 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 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 Optimización n Tradicional Problemas 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 Optimización de la producción en máquinas en paralelo de inyección de plástico por I.Q. Miguel Más detalles Unidad II: Análisis de Redes
Unidad II: Análisis de Redes 2.1 Conceptos Básicos Un problema de redes es aquel que puede representarse por: LA IMPORTANCIA DE LOS MODELOS DE REDES: Muchos problemas comerciales pueden ser resueltos a Más detalles CREACIÓN DE UNA PLATAFORMA INFORMÁTICA DE SECUENCIACIÓN DE TAREAS PARA PYMES
UNIVERSIDAD PONTIFICIA COMILLAS ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA (ICAI) INGENIERO EN INFORMÁTICA PROYECTO FIN DE CARRERA CREACIÓN DE UNA PLATAFORMA INFORMÁTICA DE SECUENCIACIÓN DE TAREAS PARA PYMES 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 ESCUELA SUPERIOR POLITÉCNICA DEL LITORAL INSTITUTO DE CIENCIAS MATEMÁTICAS ESCUELA DE GRADUADOS PROYECTO DE GRADUACIÓN
ESCUELA SUPERIOR POLITÉCNICA DEL LITORAL INSTITUTO DE CIENCIAS MATEMÁTICAS ESCUELA DE GRADUADOS PROYECTO DE GRADUACIÓN PREVIO A LA OBTENCIÓN DEL TITULO DE: MAGÍSTER EN CONTROL DE OPERACIONES Y GESTIÓN Más detalles Investigación Operativa
Investigación Operativa Ingeniería Informática Curso 08/09 Introducción Programación lineal Programación entera Programación combinatoria y en redes Simulación Sistemas de colas Introducción: Qué es la 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 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 Tema 7: Optimización sobre Redes Muchos de los problemas de Investigación Operativa pueden modelizarse y resolverse sobre un grafo: conjunto de
Tema 7: Optimización sobre Redes Muchos de los problemas de Investigación Operativa pueden modelizarse y resolverse sobre un grafo: conjunto de vértices o nodos conectados con arcos y/o aristas. Diseñar Más detalles Motores de Búsqueda Web Tarea Tema 2
Motores de Búsqueda Web Tarea Tema 2 71454586A Motores de Búsqueda Web Máster en Lenguajes y Sistemas Informáticos - Tecnologías del Lenguaje en la Web UNED 30/01/2011 Tarea Tema 2 Enunciado del ejercicio 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 Principios y criterios para la evaluación del ciclo de vida de desarrollo de sistemas Se pueden enunciar algunos principios para desarrollar Más detalles Doctorado en Ingeniería Informática
1.- Acceso y admisión. Doctorado en Ingeniería Informática Código D021 Los estudiantes que soliciten su admisión a este Programa de Doctorado, deberán acreditar que cumplen los requisitos previos para 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 PONTIFICIA UNIVERSIDAD CATÓLICA DEL PERÚ FACULTAD DE CIENCIAS E INGENIERÍA

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 
 resolución 

RESOLUCIÓN