Source: http://docplayer.es/1260174-Capitulo-vi-metodos-de-solucion-para-job-shop-scheduling.html
Timestamp: 2017-04-24 23:35:00+00:00

Document:
Capítulo VI MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING - PDF
Download "Capítulo VI MÉTODOS DE SOLUCIÓN PARA JOB SHOP SCHEDULING"
José Ignacio Muñoz Flores
1 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 combinatoria más duros, por lo tanto existen métodos de aproximación que producen soluciones aceptables empleando un tiempo razonable. Los procedimientos heurísticos para un problema de job shop se pueden clasificar en dos clases: 9 Heurísticas de una pasada: construyen una única solución fijando una operación por vez en el schedule basándose en reglas de prioridad de despacho. Hay muchas reglas para elegir una operación de un subconjunto para ser asignada próximamente. Esta heurística es rápida. 9 Heurísticas de múltiples pasadas: se construyen al repetir una heurística de una pasada para obtener schedules mejores incurriendo en algún costo extra de computación HEURÍSTICAS DE PRIORIDAD DE DESPACHO 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 [133]. Giffler y Thompsom han propuesto dos algoritmos para generar schedules: procedimientos de generación de schedules activos y schedules nondelay [72]. Un schedule nondelay tiene la propiedad de que ninguna máquina permanece ociosa si hay un job disponible para su procesamiento. Un schedule activo tiene la propiedad de que ninguna operación se puede iniciar tempranamente sin retrasar otro2 job. 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 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. Los procedimientos de generación trabajan con un conjunto de operaciones planificables en cada etapa. Las operaciones planificables son aquellas que no se han asignado y que tienen predecesoras planificadas; este conjunto se puede determinar desde la estructura de precedencia. El número de etapas para un procedimiento de una pasada es igual al número de operaciones m n. En cada etapa, se selecciona una operación para agregar al schedule parcial. Los conflictos entre operaciones se resuelven por reglas de prioridad de despacho. Para un schedule parcial activo dado, el posible tiempo de inicio σ i se determina por el tiempo de finalización del antecesor directo de la operación i y el tiempo de finalización sobre la máquina requerida por la operación i. La mayor de esas dos cantidades es σ i. El posible tiempo de finalización es simplemente σ i + t i, donde t i es el tiempo de procesamiento de la operación i. Dada la siguiente notación: 9 PS t -un schedule parcial conteniendo t operaciones ya planificadas. 9 S t - el conjunto de operaciones planificables en la etapa t, correspondiente al PS t dado. 9 σ i - el tiempo más temprano en el cual puede comenzar la operación i S t. 9 φ i - el tiempo más temprano en el cual la operación i S t puede finalizar. el procedimiento para generar un schedule activo consta de los siguientes pasos: 1. Sea t = 0 y comenzar con PS t como el schedule parcial nulo. Inicialmente S t incluye todas las operaciones sin antecesoras. 803 2. Determinar φ * t = min i St { φ i }y la máquina m * sobre la cual se puede realizar φ * t. 3. Para cada operación i S t que necesita la máquina m * y para la cual σ i < φ * i, calcular un índice de prioridad de acuerdo a la regla de prioridad. Hallar la operación con el índice más pequeño y agregarla a PS t tan pronto como sea posible, creando así un nuevo schedule parcial PS t Para PS t+1 actualizar los datos como sigue: 1. Eliminar la operación i desde S t. 2. Formar S t+1 al adicionar el sucesor inmediato de la operación j a S t. 3. Incrementar t en uno. 5. Retornar al paso 2 hasta que se haya generado un schedule completo. El problema que resta es identificar una regla de prioridad efectiva. A continuación se listan algunas de las reglas más comúnmente usadas en la práctica [69]: 9 SPT (shortest processing time): seleccionar una operación con el tiempo de procesamiento más corto. 9 LPT (longest processing time): seleccionar una operación con el tiempo de procesamiento más largo. 9 MWR (most work remaining): seleccionar una operación para el job con el mayor tiempo de procesamiento pendiente. 9 LWR (least work remaining): seleccionar una operación para el job con el menor tiempo de procesamiento pendiente. 9 MOR (most operations remaining): seleccionar una operación para el job con el mayor número de operaciones pendientes. 9 LOR (least operations remaining): seleccionar una operación para el job con el menor número de operaciones pendientes. 9 EDD (earliest due date): seleccionar un job con la fecha de entrega más temprana. 9 FCSF (first come, first served): seleccionar la primer operación en la cola de jobs para la misma máquina. 9 RND (random): seleccionar una operación en forma aleatoria. 814 HEURÍSTICA DE DESPACHO ALEATORIO Mientras las heurísticas de una pasada se limitan a la construcción de una única solución, las heurísticas de multipasada (también denominadas heurísticas de búsqueda) tratan de obtener muchas soluciones al generar varias de ellas, usualmente a expensas de mucho tiempo de computación. Técnicas tales como branch-and-bound y programación dinámica pueden garantizar una solución óptima, pero no son prácticas para problemas a gran escala. Las heurísticas aleatorias son un intento para proveer soluciones más exactas [12]. La idea de despacho aleatorio es comenzar con una familia de reglas de despacho. Por cada selección de una operación para ejecutar, se elige la regla de despacho en forma aleatoria, esto se repite a lo largo de la generación del schedule. El proceso se reitera varias veces y se elige el mejor resultado. El procedimiento para generar un schedule activo tiene los siguientes pasos: 0. Sea BS el mejor schedule, iniciarlo como un schedule nulo. 1. Sea t = 0 y PS t el schedule parcial nulo. Inicialmente S t incluye todas las operaciones sin antecesoras. 2. Determinar φ * t = min i St { φ i } y la máquina m * sobre la cual se realizará φ * t. 3. Seleccionar una regla de despacho aleatoriamente desde la familia de reglas. Para cada operación i S t que necesita la máquina m * y para la cual σ i < φ * i, calcular un índice de prioridad de acuerdo a la regla de prioridad específica. Hallar la operación con el índice más pequeño y agregar esta operación a PS t tan pronto como sea posible, creando así un nuevo schedule parcial PS t Para PS t+1 actualizar los datos como sigue: 1. Eliminar la operación i desde S t. 2. Formar S t+1 al adicionar el sucesor directo de la operación j a S t. 3. Incrementar t en uno. 5. Retornar al paso 2 hasta que se haya generado un schedule completo. 6. Si el schedule generado es los pasos anteriores es mejor que el mejor hallado hasta el momento, copiar éste en BS. Regresar al paso 1 hasta que la cantidad de iteraciones iguale las veces predeterminadas. 825 Varios investigadores han tratado de obtener mejoras a la opción aleatoria. Un cambio es introducir un proceso de aprendizaje de modo que las reglas de despacho más exitosas tengan más chances de ser seleccionadas en el futuro ALGORITMOS EVOLUTIVOS PARA EL PROBLEMA DE JOB SHOP SCHEDULING REPRESENTACIÓN Por la existencia de restricciones de precedencia de las operaciones, en JSSP no es tan fácil determinar una representación natural como en el problema del viajante (traveling salesman problem - TSP). No hay una buena representación que utilice un sistema de desigualdades para las restricciones de precedencia. Así, la opción con penalidades no es de fácil aplicación para manejar esos tipos de restricciones. Orvosh y Davis [112] han mostrado que para muchos problemas de optimización combinatoria, es relativamente fácil reparar un cromosoma ilegal o no factible, y la estrategia de reparación realmente supera estrategias tales como la de rechazo o la de penalización. La mayoría de los investigadores de JSSP y de algoritmos genéticos prefieren usar la estrategia de reparación para manejar la no factibilidad o ilegalidad. Una muy buena opción para la construcción de un algoritmo evolutivo para el problema de job shop scheduling es inventar una representación apropiada de soluciones junto con operadores genéticos específicos del problema, de manera tal que todos los cromosomas generados en la fase inicial o en el proceso evolutivo produzcan schedules factibles. Durante los últimos años se han propuesto varias representaciones para el problema de job shop scheduling, las cuales se pueden clasificar en: 9 Opciones directas: un schedule (la solución al JSSP) se codifica en un cromosoma, y el algoritmo genético se usa para evolucionar esos cromosomas a fin de determinar un schedule mejor. Dentro de esta clase se encuentran las siguientes representaciones: Representación basada en operaciones. Representación basada en jobs. Representación basada en relación de pares de jobs. Representación basada en tiempo de finalización. 836 Representación random key. 9 Opciones indirectas: tal como la representación basada en reglas de prioridad, dentro del cromosoma se codifica una secuencia de reglas de despacho, los algoritmos genéticos se usan para determinar una mejor secuencia de reglas de despacho. Un schedule se construye con la secuencia de reglas de despacho. A esta clase pertenecen las siguientes representaciones: Representación basada en lista de preferencias. Representación basada en reglas de prioridad. Representación basada en grafos disjunctivas. Representación basada en máquinas REPRESENTACIONES DIRECTAS REPRESENTACIÓN BASADA EN OPERACIONES Esta representación codifica un schedule como una secuencia de operaciones, cada gen representa una operación. Hay dos posibles formas de nombrar cada operación. Una forma natural es usar números naturales para nombrar cada operación. Desafortunadamente, por la existencia de restricciones de precedencia, no todas las permutaciones de números naturales definen schedules factibles. Gen, Tsujimura, y Kubota propusieron una forma alternativa: nombrar a todas las operaciones de un mismo job con el mismo símbolo y entonces interpretarlas de acuerdo al orden de ocurrencia en la secuencia para un cromosoma dado [30, 92]. Para un problema de n jobs y m máquinas, un cromosoma contiene n m genes. Cada job aparece en el cromosoma m veces, y cada repetición no indica una operación concreta de un job sino que se refiere a una operación la cuál es dependiente del contexto. Es fácil ver que cualquier permutación del cromosoma siempre produce un schedule factible. Consideremos el problema de tres jobs y tres máquinas utilizado en [69] y presentado en la tabla 6.1. Supongamos el siguiente cromosoma [ ], donde 1 indica el job j 1, 2 el job j 2, 3 el job j 3. Como cada job tiene tres operaciones, tiene exactamente tres ocurrencias en el cromosoma. Por ejemplo, en el cromosoma hay tres 2, lo cual representa las tres operaciones del job j 2 : 9 el primer 2 corresponde a la primer operación del job j 2 la cual se procesará sobre la máquina 1, 847 Tiempo de Procesamiento Secuencia de Máquinas Operaciones Operaciones Job Job j j 1 m 1 m 2 m 3 j j 2 m 1 m 3 m 2 j j 3 m 2 m 1 m 3 Tabla 6.1 Ejemplo de un problema de tres jobs y tres máquinas. 9 el segundo 2 corresponde a la segunda operación del job j 2 la cual se procesará sobre la máquina 3, y 9 el tercer 2 corresponde a la tercer operación del job j 2 la cual se procesará sobre la máquina 2. Como se puede observar, todas las operaciones para el job j 2 se denominan con el mismo símbolo 2 y se interpretan acorde al orden de ocurrencia en la secuencia del cromosoma. Las relaciones de ocurrencia correspondientes de las operaciones de jobs y máquinas de procesamiento se muestran en la figura 6.1. Acorde a esas relaciones, podemos obtener la lista de máquinas [ ], como se muestra en la figura 6.2. De esta figura se puede ver que el orden de procesamiento de jobs para la máquina 1 es (indicado con el sombreado), para la máquina 2 es 3 1 2, y para máquina 3 es En la figura 6.3, se muestra un schedule factible. Cromosoma: [ ] [ ] [ ] Máquinas (a) para el job 1. (b) para el job 2. (c) para el job 3. Figura 6.1 Operaciones de los jobs y correspondencia con las máquinas. cromosoma [ ] máquinas Figura 6.2 El orden de procesamiento de los jobs sobre la máquina 1. m 1 j 2 j 1 j 3 m 2 j 3 j 1 j 2 m 3 j 2 j 1 j t Figura 6.3 Un schedule factible. 858 REPRESENTACIÓN BASADA EN JOBS Esta representación consiste de una lista de n jobs y un schedule se construye en función de la secuencia de jobs. Para una secuencia de jobs dada, todas las operaciones del primer job se planifican primero, luego se consideran las operaciones del segundo job, y así sucesivamente. La primer operación del job en cuestión se asigna en el mejor tiempo de procesamiento disponible en la máquina que la operación necesite; luego se asigna la segunda operación, y así sucesivamente, hasta que se asignan todas las operaciones del job. El proceso se repite con cada uno de los jobs en la lista considerada en la secuencia apropiada. Toda permutación de jobs corresponde a schedules factibles. Usando el mismo ejemplo del problema de tres jobs y tres máquinas enunciado en la tabla 6.1, se supone el cromosoma [2 3 1]. El primer job a ser procesado es el job j 2. Las restricciones de precedencia de operaciones para j 2 son [m 1, m 3, m 2 ] y el tiempo de procesamiento correspondiente a cada máquina es [1 5 3]. El job j 2 se asigna como se muestra en la figura 6.4(a). Luego se procesa al job j 3, su precedencia de operaciones en las máquinas es [m 2, m 1, m 3 ] y los tiempos de procesamiento correspondientes en cada máquina son [3 2 3]. Cada una de sus operaciones se planifican en el mejor tiempo de procesamiento disponible en las máquinas que las operaciones necesitan, como se muestra en la figura 6.4(b). Finalmente, se planifica el job j 1 como se muestra en la figura 6.4(c). m 1 j 2 m 2 j 2 m 3 j t (a) para el primer job j 2. m 1 j 2 j 3 m 2 j 3 j 2 m 3 j 2 j t (b) para el segundo job j 3.. m 1 j 2 j 3 j 1 m 2 j 3 j 2 j 1 m 3 j 2 j 3 j t (c) para el último job j 1. Figura 6.4 Deducir un schedule desde una codificación basada en jobs. 869 Precedencia de Operaciones Schedule Factible job Secuencia de Máquinas máq. Secuencia de Jobs j 1 m 1 m 2 m 3 m 1 j 2 j 1 j 3 j 2 m 1 m 3 m 2 m 2 j 3 j 1 j 2 j 3 m 2 m 1 m 3 m 3 j 2 j 1 j 3 Tabla 6.2 Ejemplo de un problema de tres jobs y tres máquinas REPRESENTACIÓN BASADA EN LA RELACIÓN ENTRE PARES DE JOBS. Nakano y Yamada usan una matriz binaria para codificar un schedule, la cual se determina sobre la base de la relación de precedencia entre pares de jobs sobre las máquinas correspondientes [108]. Considerando el problema de scheduling de tres máquinas y tres jobs (tabla 6.1), en la tabla 6.2 se muestran las restricciones de precedencia de las operaciones de los jobs y un schedule factible para el problema. Se define una variable binaria para indicar la relación de precedencia entre un par de jobs: x ijm 1, si el job i es procesado antes al job j sobre la máquina m = 0, en cualquier otro caso. Examinando la relación de precedencia para el par de jobs (j 1, j 2 ) sobre las máquinas (m 1, m 2, m 3 ), de acuerdo al schedule dado, se tiene (x 121 x 122 x 123 ) = (0 1 0). Para el par (j 1, j 3 ) se tiene (x 131 x 132 x 133 ) = (1 0 1). Para un par de jobs (j 2, j 3 ) la relación de precedencia sobre las máquinas (m 1, m 3, m 2 ) son (x 231 x 233 x 232 ) = (1 0 1). El orden de la variable x ijm para un par de jobs deberá guardar consistencia con el orden de las operaciones del primer job i. Por ejemplo, para el par de jobs (j 2, j 3 ), la secuencia de operaciones del job j 2 es (m 1, m 3, m 2 ), por lo tanto la secuencia de las variables relativas son (x 231 x 232 x 233 ). Para resumir los resultados, se muestra la matriz binaria para el schedule factible: ( j ( j ( j 1 1 2, j, j 2 3, j 3 ) sobre ( m ) sobre ( m 1 1 ) sobre ( m 1, m, m 2, m 2 3, m, m, m ) x ) : x ) x x x x x x x = 1 1 Esta representación es tal vez la más compleja. Es altamente redundante [53]. Además de su complejidad, los cromosomas producidos por procedimientos de inicialización o por operadores genéticos son, en general, ilegales10 REPRESENTACIÓN BASADA EN TIEMPOS DE FINALIZACIÓN Yamada y Nakano propusieron la representación basada en tiempo de finalización [148]. Un cromosoma es una lista ordenada de tiempos de finalización de las operaciones. Para el mismo ejemplo dado en la tabla 6.1, el cromosoma se puede representar como: [c 111 c 122 c 133 c 211 c 223 c 232 c 312 c 312 c 333 ] donde c jir indica el tiempo de finalización para la operación i del job j sobre la máquina r. Tal representación no es adecuada para la mayoría de los operadores genéticos porque se producirán schedules ilegales. Yamada y Nakano diseñaron un operador de crossover especial para esta representación REPRESENTATION RANDOM KEY La representacion random key fue introducida por Bean [14]. Con esta técnica, las operaciones genéticas pueden producir hijos factibles sin producir overhead adicional en una amplia variedad de problemas de optimización y de secuenciamiento. Norman y Bean generalizaron con éxito la opción para el problema de job shop scheduling [109, 110]. Esta representación codifica una solución con un número random. Esos valores se utilizan como claves de ordenamiento para decodificar la solución. Para un problema de scheduling de n jobs y m máquinas, cada gen consiste de dos partes: un entero en el conjunto {1, 2,..., m} y una fracción generada aleatoriamente en el rango (0,1). La parte entera de cualquier clave random se interpreta como la asignación de máquina para ese job. El ordenamiento de las partes fraccionarias provee la secuencia de jobs en cada máquina. Consideremos el ejemplo dado en la tabla 6.1. Supongamos que el cromosoma es: [ ] Al ordenar las claves (dentro de cada máquina) en orden ascendente se obtienen las siguentes secuencias de jobs en cada máquina: 9 máquina 1: secuencia de jobs 2 1 3, 9 máquina 2: secuencia de jobs 3 1 2, 9 máquina 3: secuencia de jobs11 El cromosoma se puede trasladar a una única lista de operaciones ordenados como sigue: [ o 21 o 11 o 31 o 32 o 12 o 22 o 23 o 13 o 33 ] donde o jm indica el job j sobre la máquina m. La secuencias de jobs dados puede violar las restricciones de precedencia REPRESENTACIONES INDIRECTAS REPRESENTACIÓN BASADA EN LISTAS DE PREFERENCIA Esta representación fue propuesta en primer término por Davis para una clase de problema de scheduling [26]. Falkenauer y Bouffoix usaron esta representación para tratar un problema de job shop scheduling con tiempos de vencimiento [53]. Croce, Tadei y Volta aplicaron esta representación al problema de scheduling clásico [23]. Para un problema de job shop scheduling de n jobs y m máquinas, un cromosoma consiste de m subcromosomas, uno por máquina. Cada subcromosoma es un string de símbolos de longitud n, cada símbolo identifica una operación a ser procesada sobre la máquina correspondiente. Los subcromosomas no describen una secuencia de operaciones sobre la máquina sino que son listas de preferencia, cada máquina tiene su propia lista de preferencia. El schedule actual se deduce del cromosoma a través de una simulación, la cual analiza el estado de la cola de espera frente a cada máquina y, si es necesario, usa la lista de preferencia para determinar el schedule; es decir, se elige aquella operación que aparece primero en la lista de preferencia. En el siguiente ejemplo se muestra cómo deducir un schedule desde un cromosoma tomando como base el ejemplo presentado en la tabla 6.1. Se supone que el cromosoma es [(2 3 1) (1 3 2) (2 1 3)]. El primer gen (2 3 1) es la lista de preferencia para la máquina m 1, (1 3 2) es la lista para la máquina m 2 y (2 1 3) para la máquina m 3. Desde esas listas de preferencia se puede ver que las primeras operaciones preferenciales son: job j 2 sobre la máquina m 1, j 1 sobre m 2, j 2 sobre m 3. Acorde a las restricciones de preferencia de las operaciones sólo se puede planificar j 2 sobre m 1, de este modo el primer schedule es el que se muestra en la figura 6.5(a). La próxima operación planificable es j 2 sobre la máquina m 3 como se muestra en la figura 6.5(b). En este punto, las operaciones preferenciales son j 3 sobre la máquina m 1 y j 1 sobre m 2 y m 3. Como no son planificables en este momento, se toma la segunda operación preferencial 8912 en cada lista: j 1 sobre m 1 y j 3 sobre m 2.y m 3. Las operaciones a planificar son j 1 sobre m 1 y j 3 sobre m 2 y Se asignan como se muestra en la figura 6.5(c). Las próximas operaciones planificables son j 3 sobre m 1 y j 1 sobre m 2, como lo muestra la figura 6.5(d). Luego, las operaciones planificables son j 2 sobre m 2 y j 1 sobre m 3 como se muestra en la figura 6.5(e). La última operación planificable es j 3 sobre m 3 (figura 6.5(f)). Ahora se completa la deducción de un schedule desde el cromosoma y se obtiene un schedule factible con un makespan de 12 unidades de tiempo. Con el procedimiento de decodificación, todos los posibles cromosomas producen un schedule factible REPRESENTACIÓN BASADA EN REGLAS DE PRIORIDAD Dorndorg y Pesch propusieron un algoritmo evolutivo basado en reglas de prioridad [32], un cromosoma se codifica como una secuencia de reglas de despacho para una asignación de jobs. Un schedule se construye con heurísticas de despacho de prioridad en base a la secuencia de reglas de despacho. Los algoritmos evolutivos se usan para evolucionar esos cromosomas que ayudarán a producir una mejor secuencia de reglas de despacho. m 1 j 2 m 1 j 2 m 2 m 2 m 3 m 3 j t t (a) asignar job 2 sobre máq. 1. (b) asignar job 2 sobre máq. 3. m 1 j 2 j 1 m 1 j 2 j 1 j 3 m 2 j 3 m 2 j 3 j 1 m 3 j 2 m 3 j t t (c) asignar job 1 sobre máq. 1 (d) asignar job 3 sobre máq. 1 y job 3 sobre máq. 2. y job 1 sobre máq. 2. m 1 j 2 j 1 j 3 m 1 j 2 j 1 j 3 m 2 j 3 j 1 j 2 m 2 j 3 j 1 j 2 m 3 j 2 j 1 m 3 j 2 j 1 j t t (e) asignar job 2 sobre máq. 2 y job 1 sobre máq. 3. (f) schedule final. Figura 6.5 Deducir un schedule desde una codificación basada en listas de preferencias. 9013 Las reglas de prioridad de despacho son las heurísticas que se usan con mayor frecuencia para resolver problemas de scheduling en la práctica, debido a su fácil implementación y a su bajo tiempo de complejidad. Los algoritmos de Giffler y Thompson se pueden considerar como la base para todas las heurísticas de reglas de prioridad [72, 133]. El problema es identificar una regla de prioridad efectiva. Para un problema de n jobs y m máquinas, un cromosoma es un string de n m entradas (p 1, p 2,..., p nm ). Una entrada p i representa una regla de un conjunto de reglas de prioridades de despacho. La entrada en la posición i-ésima indica que un conflicto en la iteración i-ésima del algoritmo de Giffler y Thompson se resolverá usando la regla de prioridad p i. Una operación desde el conjunto de conflicto se selecciona por la regla p i ; en caso de existir más de una operación dentro de ese conjunto de conflicto, la decisión se hace en forma aleatoria. Dada la siguiente notación: 9 PS t - un schedule parcial conteniendo t operaciones asignadas. 9 S t - el conjunto de operaciones asignables en la etapa t, correspondiente al PS t. 9 σ i - el tiempo más temprano en el cual se deberá iniciar la operación i S t. 9 φ i -el tiempo más temprano en el cual se deberá completar la operación i S t 9 C t -el conjunto de operaciones en conflicto en la iteración t el procedimiento para deducir un schedule desde un cromosoma dado (p 1, p 2,..., p nm ) es el siguiente: 1. Sea t = 1 y comenzar con PS t como el schedule parcial nulo. Inicialmente S t incluye todas las operaciones sin predecesoras. 2. Determinar φ * t = min i St { φ i }y la máquina m * sobre la cual se realizará φ * t. Si existe más de una máquina, la selección se determina en forma aleatoria. 3. Formar el conjunto C t el cual incluye todas las operaciones i S t que necesita la máquina m *. Seleccionar una operación de C t usando la regla de prioridad p t y adicionar esta operación a PS t tan pronto como sea posible, creando así un nuevo schedule parcial PS t+1. Si existe más de una operación acorde a la prioridad p t, entonces esta situación se resuelve en forma aleatoria. 4. Actualizar PS t+1 al sacar la operación seleccionada desde S t y agregar el sucesor directo de la operación j a S t. Incrementar t en uno. 5. Retornar al paso 2 hasta que se haya generado un schedule completo. 9114 Ejemplo. Dado [69]: las reglas SPT, LPT, MWR, LWR, con identificadores 1, 2, 3 y 4 respectivamente, el cromosoma [ ] e indicando las operaciones como o jom (donde el índice jom se refiere a job, operación, máquina). En el paso inicial (t = 1), se tiene: S 1 = { o 111, o 211, o 312 } * φ 1 = min {3, 1, 3}= 1 m* = 1 C 1 ={ o 111, o 211 } Las operaciones o 111 y o 211 compiten por m 1. Como el primer gen del cromosoma es 1 (el cual significa la regla de prioridad SPT), la operación 211 es planificada en m 1, como se muestra en la figura 6.6(a). Después de actualizar tenemos (t =2), S 2 = { o 111, o 223, o 312 } φ = min {4, 6, 3} = 3 * 2 m* = 2 C 2 ={ o 312 } Se planifica la operación o 312 en m 2 como se muestra en la figura 6.6(b). Después de actualizar tenemos (en t =3), S 3 = { o 111, o 223, o 321 } φ = min {4, 6, 5} = 5 * 3 m* = 1 C 3 ={ o 111, o 321 } Las operaciones o 111 y o 321 compiten por m 1. Como el tercer gen del cromosoma es 2 (el cual representa a la regla de prioridad LPT), la operación o 111 gana y se la planifica en m 1, como se muestra en la figura 6.6(c). Estos pasos se repiten hasta que se forma el schedule desde el cromosoma (figura 6.6(d)). m m m 2 m m 3 m t t (a) planificación de la operación 211 en m 1. (b) planificación de la operación 312 en m 1. m m m m m 3 m t t (c) planificación de la operación 211 en m 1. (d) schedule final. Figura 6.6 Deduciendo un schedule desde una codificación basada en reglas de prioridad. 9215 REPRESENTACIÓN BASADA EN GRAFOS DISJUNCTIVOS. Tamaki y Nishikawa proponen una representación basada en grafos disjunctivos [135], la cual se puede considerar como una clase de la representación basada en pares de jobs. El problema de job shop scheduling se puede representar con un grafo disjunctivo [13, 121]. El grafo disjunctivo G = (N, A, E) se define como: 9 N: contiene los nodos representado todas las operaciones. 9 A: contiene los arcos que conectan operaciones consecutivas del mismo job. 9 E: contiene los arcos disjuntos que conectan las operaciones a ser procesadas por la misma máquina. Las restricciones disjunctivas se representan por un eje en E. Se puede establecer un arco disjunctivo por sus dos posibles orientaciones. La construcción de un schedule establece las orientaciones de todos los arcos disjunctivos así como también determina la secuencia de operaciones sobre la misma máquina. Una vez que se determina una secuencia para una máquina se reemplazan los arcos disjunctivos por arcos conjunctivos normales. La figura 6.7, muestra el grafo disjunctivo para el ejemplo de tres jobs y tres máquinas introducido en la tabla 6.1. Un cromosoma consiste de un string binario correspondiente a una lista de orden de arcos disjunctivos en E como se muestra en la figura 6.8, donde e ij indica el arco disjunctivo entre los nodos i y j y se define como sigue: e ij 1, = 0, establecer la orientación del arco disjunctive desde el nodo establecer la orientación del arco disjunctive desde el nodo i j al nodo al nodo i j Figura 6.7 Grafo disjunctivo para el problema de tres máquinas y tres jobs. 9316 Lista de orden de arcos disjunctivos e 15 e 19 e 59 e 24 e 28 e 48 e 36 e 37 e 67 cromosoma Figura 6.8 Representación basada en grafos disjunctivos. El problema de job shop es encontrar un orden en las operaciones sobre cada máquina, es decir, fijar la orientación de los arcos disjunctivos tal que el grafo resultante no contenga ciclos para garantizar la no existencia de conflictos de precedencia entre las operaciones. Un cromosoma arbitrario puede provocar un grafo cíclico, lo cual significa que el schedule no es factible. Durante el proceso de deducción, cuando ocurre un conflicto de dos nodos (operaciones) sobre una máquina, se usa el bit correspondiente del cromosoma para fijar el orden de procesamiento de dos operaciones, es decir, fijar la orientación del arco disjunctive entre dos nodos REPRESENTACIÓN BASADA EN MÁQUINAS Dornforf y Pesch propusieron un algoritmo evolutivo basado en máquinas [32] donde un cromosoma se codifica como una secuencia de máquinas y un schedule se construye con una heurística basada en corrimientos del cuello de botella sobre la secuencia. La heurística de corrimiento del cuello de botella, propuesto por Adams, Balas y Zawack [1], es probablemente el procedimiento más poderoso entre todas las heurísticas para el problema de job shop scheduling. Las máquinas se secuencian una a una, sucesivamente, tomando aquella máquina identificada como el cuello de botella entre las máquinas aún no secuenciadas. Cuando se secuencia una nueva máquina, todas las secuencias establecidas previamente se reoptimizan localmente. Tanto los procedimientos de identificación del cuello de botella y de reoptimización local se basan en la resolución repetida de un cierto problema de scheduling de una única máquina que es una simplificación del problema original. La principal contribución de esta opción es la forma en que se usa esta simplificación para decidir respecto del orden en el cual se secuencian las máquinas. Las heurísticas de corrimiento del cuello de botella se basan en la idea de dar prioridad a las máquinas con cuellos de botella. La calidad de los schedules obtenidos 94 Mostrar más
&$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 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 Scheduling Problem. Cuándo y dónde debo hacer cada trabajo?
Scheduling Problem Cuándo y dónde debo hacer cada trabajo? Ejemplos de problemas de asignación de recursos Fabricación de varios tipos de productos Asignación de turnos de trabajo Inversión financiera Más detalles Algoritmos sobre Grafos
Sexta Sesión 27 de febrero de 2010 Contenido Deniciones 1 Deniciones 2 3 4 Deniciones sobre Grafos Par de una lista de nodos y una lista de enlaces, denidos a su vez como pares del conjunto de nodos. 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 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 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 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 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 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 METAHEURISTICAS Ideas, Mitos, Soluciones
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 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 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 Sistema Incremental Generador de Oraciones y de Descodificación Lingüística. José Luciano Maldonado. luzmalvy@telcel.net.ve maldonaj@faces.ula.
Sistema Incremental Generador de Oraciones y de Descodificación Lingüística. José Luciano Maldonado. luzmalvy@telcel.net.ve maldonaj@faces.ula.ve Resumen: se describe la implementación experimental de 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 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 GESTIÓN DEL TIEMPO. La Gestión del Tiempo del Proyecto incluye los procesos necesarios para lograr la conclusión del proyecto a tiempo.
GESTIÓN DEL TIEMPO La Gestión del Tiempo del Proyecto incluye los procesos necesarios para lograr la conclusión del proyecto a tiempo. DEFINICIÓN DE LAS ACTIVIDADES Definir las actividades del cronograma 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 Computación Evolutiva - Mutación: Cruza, Inversión y Mutación para Permutaciones
Computación Evolutiva - Mutación: Cruza, Inversión y Mutación para Permutaciones Dr. Gregorio Toscano Pulido Laboratorio de Tecnologías de Información Centro de Investigación y de Estudios Avanzados del 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 Sistemas de producción y búsqueda de soluciones. Area de Computación e Inteligencia Artificial 1
Sistemas de producción y búsqueda de soluciones Area de Computación e Inteligencia Artificial 1 Técnicas de búsqueda Resolución de problemas en Inteligencia Artificial. En general, podemos afirmar que 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 Problemas indecidibles
Capítulo 7 Problemas indecidibles 71 Codificación de máquinas de Turing Toda MT se puede codificar como una secuencia finita de ceros y unos En esta sección presentaremos una codificación válida para todas 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 Arboles Binarios de Búsqueda
Arboles Binarios de Búsqueda Algoritmos y Estructuras de Datos Departamento de Electricidad y Electrónica (UPV/EHU) Arboles Binarios de Búsqueda p.1/52 Arboles Binarios Arbol binario: árbol ordenado de Más detalles RAID. Los detalles de las características segunda y tercera, cambian según los distintos niveles RAID. RAID 0 no soporta la tercera característica.
RAID Como se dijo anteriormente, el ritmo de mejora de prestaciones en memoria secundaria ha sido considerablemente menor que en procesadores y en memoria principal. Esta desigualdad ha hecho, quizás, 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 El modelo de ciclo de vida cascada, captura algunos principios básicos:
Ciclo de Vida del Software Un modelo de ciclo de vida define el estado de las fases a través de las cuales se mueve un proyecto de desarrollo de software. El primer ciclo de vida del software, "Cascada", 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 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 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 GRAFOS. Prof. Ing. M.Sc. Fulbia Torres
ESTRUCTURAS DE DATOS 2006 Prof. DEFINICIÓN Un grafo consta de un conjunto de nodos(o vértices) y un conjunto de arcos (o aristas). Cada arco de un grafo se especifica mediante un par de nodos. Denotemos Más detalles La gestión de proyectos es la rama de la ciencia de la administración que trata de la planificación y el control de proyectos.
DEFINICIÓN DE PROYECTO Un proyecto es un conjunto de acciones No repetitivas Únicas De duración determinada Formalmente organizadas Que utilizan recursos Podremos considerar un proyecto, a efectos de aplicarle Más detalles Primer Parcial de Programación 3 (1/10/2009)
Primer Parcial de Programación (/0/009) Instituto de Computación, Facultad de Ingeniería Este parcial dura horas y contiene carillas. El total de puntos es 0. En los enunciados llamamos C* a la extensión Más detalles Tipos Abstractos de Datos
Objetivos Repasar los conceptos de abstracción de datos y (TAD) Diferenciar adecuadamente los conceptos de especificación e implementación de TAD Presentar la especificación algebraica como método formal Más detalles Taller de sistemas operativos PLANIFICADOR
Taller de sistemas operativos PLANIFICADOR Agenda Introducción Clases de planificación Prioridades Timeslice Prioridad dinámica Estructuras del planificador Planificador en funcionamiento Nuevo planificador 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 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 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 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 Planificación de Procesos. Módulo 5. Departamento de Informática Facultad de Ingeniería Universidad Nacional de la Patagonia San Juan Bosco
Planificación de Procesos Módulo 5 Departamento de Informática Facultad de Ingeniería Universidad Nacional de la Patagonia San Juan Bosco Planificación de Procesos Conceptos Básicos Criterios de Planificación Más detalles Sistemas operativos avanzados. 1.3 Algoritmos de planificación del procesador
Sistemas operativos avanzados 1.3 Algoritmos de planificación del procesador Parámetros Cuando tenemos más de un proceso en condiciones de ejecutar, debemos escoger uno de entre ellos. Para escogerlo empleamos Más detalles Capítulo IV ALGORITMOS GENÉTICOS
Capítulo IV ALGORITMOS GENÉTICOS 4.1. INTRODUCCIÓN La estructura de un algoritmo genético simple se corresponde con la estructura de cualquier programa evolutivo (ver figura 1.1). Durante la iteración Más detalles Soluciones de los ejercicios de la primera Unidad. Dr. Jorge Martín Dr. José Antonio Carrillo
Soluciones de los ejercicios de la primera Unidad Dr. Víctor Hernández Dr. Jorge Martín Dr. José Antonio Carrillo 5 de marzo de 0 Índice general Ejercicio.. Manejo del formalismo de los sucesos............. Más detalles PLANIFICACIÓN DE PROYECTOS
Pert - CPM: Uno de los primeros casos documentados de la epoca actual sobre la administración y planificacion de proyectos se refiere al proyecto de armamentos del Polaris, empezando 1958. Así surgió el Más detalles Algoritmos Genéticos. Introduccion a la Robótica Inteligente
Algoritmos Genéticos Introduccion a la Robótica Inteligente 7 Marzo 2014 (IRIN) AGs 7/03/2014 1 / 43 Índice 1 Introducción 2 Algoritmos Genéticos 3 Algunos Fundamentos Matemáticos 4 Conclusiones (IRIN) Más detalles Estructuras de Datos y Algoritmos Práctica I - Curso 2012/13
Estructuras de Datos y Algoritmos Práctica I - Curso 2012/13 Rompiendo el Código Enigma Introducción y objetivos Como un pequeño homenaje a Alan Turing en su año conmemorativo, las prácticas de este curso 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 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 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 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 Tema 1: Implementación del sistema de archivos
Tema 1: Implementación del sistema de archivos 1. Introducción 2. Implementación 3. Estructura del almacenamiento secundario Dpto. Tema Lenguajes 1: Implementación y Sistemas del Informáticos. sistema 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 La memoria principal. Los subsistemas de E/S. Los buses del sistema
GUIA 23: MEMORIA E/S La estructura básica de la mayoría de los ordenadores actuales se representa mediante los siguientes elementos básicos: La Unidad Central de Procesamiento, CPU La memoria principal Más detalles Apuntes de Grafos. 1. Definiciones
Apuntes de Grafos Un grafo es una entidad matemática introducida por Euler en 736 para representar entidades (vértices) que pueden relacionarse libremente entre sí, mediante el concepto de arista Se puede Más detalles RECURSION. Se deben hacer cuatro preguntas para construir una solución recursiva:
puntes teóricos ño 2013 RECURSION Veremos un nuevo mecanismo, una nueva técnica de diseño, para resolver problemas: L RECURSIÓN. La recursión es una alternativa a la iteración o repetición, y aunque en Más detalles Metaheurísticas basadas en Scatter Search y Path Relinking para resolver el Problema del Fuzzy Job Shop Scheduling
FACULTAD DE CIENCIAS UNIVERSIDAD DE CANTABRIA Proyecto Fin De Carrera Metaheurísticas basadas en Scatter Search y Path Relinking para resolver el Problema del Fuzzy Job Shop Scheduling (Scatter Search Más detalles MODELOS DE PLANIFICACIÓN
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 Investigación Operacional I EII 445
Investigación Operacional I EII 445 Programación Lineal Método Simple Gabriel Gutiérrez Jarpa. Propiedades Básicas de Programación Lineal Formato Estándar Un problema de programación lineal es un programa Más detalles Sistemas de Numeración Operaciones - Códigos
Sistemas de Numeración Operaciones - Códigos Tema 2 1. Sistema decimal 2. Sistema binario 3. Sistema hexadecimal 4. Sistema octal 5. Conversión decimal binario 6. Aritmética binaria 7. Complemento a la Más detalles Procesamiento Digital de Imágenes. Compresión de imágenes
FICH, UNL - Departamento de Informática - Ingeniería Informática Procesamiento Digital de Imágenes Guía de Trabajos Prácticos 8 Compresión de imágenes 2010 1. Objetivos Analizar las características y el Más detalles Escuela Politécnica Superior. Planificación y Control de Proyectos. Capítulo 11. daniel.tapias@uam.es. Dr. Daniel Tapias Curso 2014 / 15 PROYECTOS
Escuela Politécnica Superior Planificación y Control de Proyectos. Capítulo 11 Dr. Daniel Tapias Curso 2014 / 15 daniel.tapias@uam.es PROYECTOS PROGRAMA DE LA ASIGNATURA Capítulo 1: Introducción. Capítulo Más detalles Ampliación de Estructuras de Datos
Ampliación de Estructuras de Datos Amalia Duch Barcelona, marzo de 2007 Índice 1. Diccionarios implementados con árboles binarios de búsqueda 1 2. TAD Cola de Prioridad 4 3. Heapsort 8 1. Diccionarios 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 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 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 Genética
Programación Genética Programación Genética consiste en la evolución automática de programas usando ideas basadas en la selección natural (Darwin). No sólo se ha utilizado para generar programas, sino 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 Introducción a la Teoría de Probabilidad
Capítulo 1 Introducción a la Teoría de Probabilidad Para la mayoría de la gente, probabilidad es un término vago utilizado en el lenguaje cotidiano para indicar la posibilidad de ocurrencia de un evento Más detalles Unidad 2: Gestión de Procesos
Unidad 2: Gestión de Procesos Tema 5: Planificación de procesos. 5.1 Criterios y tipos de planificación. 5.2 Algoritmos de planificación. 5.3 Métodos multicolas y multiprocesadores. 5.4 Evaluación de políticas Más detalles PLANIFICACIÓN Y PROGRAMACIÓN DE PROYECTOS METODOS PERT Y GANTT
PLANIFICACIÓN Y PROGRAMACIÓN DE PROYECTOS METODOS PERT Y GANTT [Escriba aquí una descripción breve del documento. Normalmente, una descripción breve es un resumen corto del contenido del documento. Escriba Más detalles Árboles. Cursos Propedéuticos 2015. Dr. René Cumplido M. en C. Luis Rodríguez Flores
Árboles Cursos Propedéuticos 2015 Dr. René Cumplido M. en C. Luis Rodríguez Flores Contenido de la sección Introducción Árbol genérico Definición y representación Árboles binarios Definición, implementación, 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 SOFTWARE CON CALIDAD PARA UNA EMPRESA
DESARROLLO DE SOFTWARE CON CALIDAD PARA UNA EMPRESA Resumen AUTORIA CARLOS CABALLERO GONZÁLEZ TEMATICA INFORMÁTICA ETAPA ESO-BACHILLERATO-CFGM(ESI,ASI,DSI) Se describe la revolución que supuso la incursión Más detalles 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 Búsqueda heurística Prof. Constantino Malagón
Búsqueda heurística Prof. Constantino Malagón Area de Computación e Inteligencia Artificial 1 Búsqueda heurística Los métodos de búsqueda heurística disponen de alguna información sobre la proximidad de 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 Ingeniería Energética E-ISSN: 1815-5901 orestes@cipel.ispjae.edu.cu. Instituto Superior Politécnico José Antonio Echeverría. Cuba
Ingeniería Energética E-ISSN: 1815-5901 orestes@cipel.ispjae.edu.cu Instituto Superior Politécnico José Antonio Echeverría Cuba Carvajal- Pérez, Raúl Nicolás Un Algoritmo Genético Especializado en Planeamiento Más detalles Fundamentos de Investigación de Operaciones Investigación de Operaciones 1
Fundamentos de Investigación de Operaciones Investigación de Operaciones de agosto de 200. Estandarización Cuando se plantea un modelo de LP pueden existir igualdades y desigualdades. De la misma forma Más detalles Capítulo V Operaciones Booleanas
85 Capítulo V Operaciones Booleanas 5.1 Introducción Es muy posible que en muchos casos sea necesario comparar dos objetos y determinar cuál es su parte común. Esto implica intersectar los dos objetos Más detalles FORMULACIÓN DE UN ALGORITMO GENÉTICO PARA EL PROBLEMA DE PROGRAMACIÓN DE ÓRDENES DE TRABAJO DE UNA EMPRESA DE ARTES GRÁFICAS
FORMULACIÓN DE UN ALGORITMO GENÉTICO PARA EL PROBLEMA DE PROGRAMACIÓN DE ÓRDENES DE TRABAJO DE UNA EMPRESA DE ARTES GRÁFICAS PROYECTO DE GRADO Javier mauricio gamboa salgado Código: 544004 John alexander Más detalles PESTAÑA DATOS - TABLAS EN EXCEL
PESTAÑA DATOS - TABLAS EN EXCEL Una tabla en Excel es un conjunto de datos organizados en filas o registros, en la que la primera fila contiene las cabeceras de las columnas (los nombres de los campos), Más detalles Cómo ordenar una lista de números?
Cómo ordenar una lista de números? Germán Ariel Torres Resumen. Este trabajo trata acerca de métodos y técnicas usadas para el ordenamiento eficiente de listas de números. Se analizan los métodos básicos, Más detalles Probabilidad y sus aplicaciones en ingeniería informática
Probabilidad y sus aplicaciones en ingeniería informática Víctor Hernández Eduardo Ramos Ildefonso Yáñez c Víctor Hernández, Eduardo Ramos, Ildefonso Yánez EDICIONES CDÉMICS Probabilidad y sus aplicaciones Más detalles CÁLCULO ALGEBRAICO. Dra. Patricia Kisbye Dr. David Merlo
CÁLCULO ALGEBRAICO Dra. Patricia Kisbye Dr. David Merlo INTRODUCCIÓN Estas notas han sido elaboradas con el fin de ofrecer al ingresante a las carreras de la FaMAF herramientas elementales del cálculo Más detalles Tema 5: Teoría de colas. Ezequiel López Rubio Departamento de Lenguajes y Ciencias de la Computación Universidad de Málaga
Tema 5: Teoría de colas Ezequiel López Rubio Departamento de Lenguajes y Ciencias de la Computación Universidad de Málaga Sumario Conceptos básicos Cola M M Cola M M c Cola M M k Redes de colas Redes de Más detalles Fundamentos de Investigación de Operaciones Investigación de Operaciones 1
Fundamentos de Investigación de Operaciones Investigación de Operaciones 1 1 de agosto de 2003 1. Introducción Cualquier modelo de una situación es una simplificación de la situación real. Por lo tanto, 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 Procesos. Bibliografía. Threads y procesos. Definiciones
Procesos Prof. Mariela Curiel Bibliografía A. Tanembaum & M. Van Steen. Sistemas Distribuidos. Principios y Paradigmas. 2da. Edición. Smith & Nair. The Architecture of Virtual Machines. IEEE Computer. Más detalles Modelos y Optimización I
Modelos y Optimización I María Inés Parnisari 7 de enero de 2012 Índice 1. Deniciones 2 2. Método Simplex 2 3. Problemas 4 4. Modelización 10 5. Heurísticas 10 1 1 Deniciones Investigación operativa: aplicación 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 Estas visiones de la información, denominadas vistas, se pueden identificar de varias formas.
El primer paso en el diseño de una base de datos es la producción del esquema conceptual. Normalmente, se construyen varios esquemas conceptuales, cada uno para representar las distintas visiones que los Más detalles Examen de Redes de Datos Tecnólogo en Telecomunicaciones (ROCHA)
Examen de Redes de Datos Tecnólogo en Telecomunicaciones (ROCHA) SOLUCIÓN (más completa que el mínimo requerido para obtener los máximos puntajes) Pregunta 1 En el sistema de nombre de dominio (DNS): a) Más detalles Material de Apoyo 5 ADMINISTRACIÓN DE PROYECTOS CON PERT / CPM (Hillier & Liberman Capítulo 10)
Material de Apoyo 5 ADMINISTRACIÓN DE PROYECTOS CON PERT / CPM (Hillier & Liberman Capítulo 10) Antes de comenzar a analizar cada una de las técnicas, recordemos la definición del glosario del Material 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 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 INVESTIGACION OPERATIVA

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