Metodo posicional

Solo disponible en BuenasTareas
  • Páginas : 5 (1237 palabras )
  • Descarga(s) : 0
  • Publicado : 9 de septiembre de 2010
Leer documento completo
Vista previa del texto
1. Introducción

Trabajos en una máquina

• Determinar la secuencia óptima de procesar n trabajos en una máquina.
• Todas las secuencias tienen el mismo makespan.
• Minimizar el mean flow time es el criterio a satisfacer.
• Representemos los tiempos de proceso de los trabajos i como pi (i = 1,n).
• La secuencia que minimiza el criterio es aquella en la que los trabajos se ordenan delmenor tiempo al mayor.
• Ésta secuencia también minimiza el tiempo promedio de espera y la tardanza promedio (mean lateness).
• Cuando los trabajos tienen diferente prioridad o peso, el objetivo puede ser el de minimizar el tiempo de flujo promedio ponderado.
• A mayor valor del índice, el trabajo es mas importante.
• [pic]La secuencia óptima sería ordenando los trabajos de menor pi/wi almayor.
• Minimizar el promedio ponderado del tiempo de flujo.

La secuencia óptima es (2,5,3,6,1,4).

Trabajos En 2 Máquinas

• Los n trabajos se procesan en 2 máquinas con el mismo órden. El criterio es el de minimizar el makespan.
• El procedimiento a utilizar es el de Johnson.
• Si pij es el tiempo de procesodel trabajo i en la máquina j, seleccione el mínimo y si éste correspondea la máquina 1, asígnelo a la primera posición de la secuencia.
• Si corresponde a la máquina 2, el trabajo se asigna a la última posición de la secuencia.
• Elimine el trabajo asignado del set y repita el procedimiento con los trabajos no asignados.

Procedimiento de Jonson

• Determine la secuencia de proceso que minimice el makespan

[pic]

La secuencia es (2,4,5,3,1).
Trabajoscon Ruta Diferente en 2 Máquinas

• Usar algoritmo de Jackson.
• Formar 4 sets de trabajos;
• {A} = Los procesados solamente en la máquina 1.
• {B} = Los procesados en máquina 2 solamente.
• {AB} = Los procesados primero en máquina 1 y luego en la 2.
• {BA} = Los procesados primero en máquina 2 y luego en la 1.
• Secuenciar los trabajos de {AB} y {BA}, por separado, con algoritmo deJohnson.
• Defina secuencias arbitrarias para los trabajos {A} y {B}.
• Combine las secuencias de la siguiente manera.
• Máquina 1: {AB} antes de {A} antes de {BA}.
• Máquina 2: {BA} antes de {B} antes de {AB}.

 Trabajos en 3 Máquinas

• Todos los trabajos tienen la misma secuencia de proceso.
• Puede resolverse con el algoritmo de Johnson si:
• min {pi1} > máx { pi2 }, o
• min{ pi3 } >máx { pi2 }.
• La máquina 2 es dominada completamente por la máquina 1 o 3.
• Se aplica el procedimiento formando 2 máquinas dummy, 1´y 2´, con tiempos de proceso:
• pi1´ = pi1 + pi2 y pi2´ = pi2 + pi3.
• El procedimiento proporciona una secuencia factible y "buena" aún cuando no se cumplan las condiciones

Secuenciar los siguientes trabajos.

[pic][pic]

[pic]

Secuenciaóptima
es {2,1,4,3}.

Trabajos en m máquinas

• No existe un método eficiente que proporcione una solución exacta.
• Se utilizan métodos heurísticos tales como las Reglas de Despacho.
• Éstas son reglas que determinan qué trabajo procesar al quedar éste disponible de manera secuencial en el tiempo, en lugar de suponer que todos los trabajos están disponibles.
• Se maneja el conceptode prioridad en los trabajos.

Secuenciación Dinámica de Trabajos

• Trabajos llegan a procesarse al azar durante un intervalo de tiempo.
• Su secuencia se determina mediante el uso de reglas de despacho que proporcionan prioridades a los mismos.
• Las reglas se derivan a través de análisis de líneas de espera, experimentación y simulación.
• La regla de secuenciación y despacho masimportante es la del tiempo de proceso mas corto (SPT).
• Otras reglas se derivan del SPT , así como del tamaño de las líneas de espera y la fecha prometida a los clientes.

Otras Reglas de Despacho

• Basadas en tiempo de proceso.
• Menor Trabajo Remanente (LWKR): Considera la suma de los tiempos de proceso para todas las operaciones por realizarse en el trabajo.
• Trabajo Total (TWK):...
tracking img