La programación de Flow-Shop es un problema de optimización en la investigación de operaciones y ciencias de la computación . Es una variante de la programación de trabajos óptima . En un problema general de programación de trabajos, se nos asignan n trabajos J 1 , J 2 , ..., J n de diferentes tiempos de procesamiento, que deben programarse en m máquinas con diferente potencia de procesamiento, mientras intentamos minimizar el tiempo de fabricación - la duración total de la programación (es decir, cuando todos los trabajos han terminado de procesarse). En la variante específica conocida como programación flow-shop, cada trabajo contiene exactamente m operaciones. La i -ésima operación del trabajo debe ejecutarse en la i -ésima máquina. Ninguna máquina puede realizar más de una operación simultáneamente. Para cada operación de cada trabajo, se especifica el tiempo de ejecución.
La programación de taller de flujo es un caso especial de programación de taller de trabajo donde hay un orden estricto de todas las operaciones que deben realizarse en todos los trabajos. La programación de Flow-Shop puede aplicarse tanto a las instalaciones de producción como a los diseños informáticos . Un tipo especial de problema de programación de flujo-taller es el problema de programación de flujo-taller de permutación en el que el orden de procesamiento de los trabajos en los recursos es el mismo para cada paso subsiguiente del procesamiento.
En la notación estándar de tres campos para problemas de programación de trabajos óptimos , la variante del taller de flujo se indica con F en el primer campo. Por ejemplo, el problema denotado por " F3 ||"es un problema de taller de flujo de 3 máquinas con tiempos de procesamiento unitario, donde el objetivo es minimizar el tiempo máximo de finalización.
Definicion formal
Hay n máquinas y m trabajos. Cada trabajo contiene exactamente m operaciones. La i -ésima operación del trabajo debe ejecutarse en la i -ésima máquina. Ninguna máquina puede realizar más de una operación simultáneamente. Para cada operación de cada trabajo, se especifica el tiempo de ejecución.
Las operaciones dentro de un trabajo deben realizarse en el orden especificado. La primera operación se ejecuta en la primera máquina, luego (cuando finaliza la primera operación) la segunda operación en la segunda máquina, y así sucesivamente hasta la n -ésima operación. Sin embargo, los trabajos se pueden ejecutar en cualquier orden. La definición del problema implica que esta orden de trabajo es exactamente la misma para cada máquina. El problema es determinar la disposición óptima de este tipo, es decir, la que tiene la menor duración posible de ejecución total del trabajo.
Secuenciación de medidas de rendimiento (γ)
El problema de secuenciación se puede plantear como la determinación de una secuencia S de manera que se optimicen uno o varios objetivos de secuenciación.
- (Promedio) Tiempo de flujo,
- Makespan, C máx.
- Tardanza (media),
- ....
Se puede encontrar un análisis detallado de la medición del desempeño en Malakooti (2013). [1]
Complejidad de la programación del taller de flujo
Según lo presentado por Garey et al. (1976), [2] la mayoría de las extensiones de los problemas de programación de flujo-taller son NP-hard y pocas de ellas pueden resolverse de manera óptima en O (nlogn); por ejemplo, F2 | prmu | C max se puede resolver de manera óptima utilizando la regla de Johnson . [3]
Taillard proporciona importantes problemas de referencia para programar talleres de flujo, talleres abiertos y talleres de trabajo. [4]
Métodos de solución
Los métodos propuestos para resolver problemas de programación de flujo-taller se pueden clasificar como algoritmo exacto , como ramificación y enlace, y algoritmo heurístico , como algoritmo genético .
Minimización de la capacidad de producción, C max
F2 | prmu | C max y F3 | prmu | C max se pueden resolver de manera óptima usando la regla de Johnson [3] pero para el caso general no existe un algoritmo que garantice la optimización de la solución.
El taller de flujo contiene n trabajos disponibles simultáneamente en el tiempo cero y para ser procesados por dos máquinas dispuestas en serie con almacenamiento ilimitado entre ellas. El tiempo de procesamiento de todos los trabajos se conoce con certeza. Es necesario programar n trabajos en las máquinas para minimizar la capacidad de producción. La regla de Johnson para programar trabajos en un taller de flujo de dos máquinas se da a continuación.
En un horario óptimo, el trabajo i precede al trabajo j si min {p 1i , p 2j }
Para el algoritmo de Johnson:
- Sea p 1j el tiempo de procesamiento del trabajo j en la máquina 1
- y p 2j el tiempo de procesamiento del trabajo j en la máquina 2
Algoritmo de Johnson:
- Form set1 que contiene todos los trabajos con p 1j 2j
- Formulario set2 que contiene todos los trabajos con p 1j > p 2j , los trabajos con p 1j = p 2j pueden colocarse en cualquier conjunto.
- Forme la secuencia de la siguiente manera:
- (i) El trabajo en set1 va primero en la secuencia y van en orden creciente de p 1j (SPT)
- (ii) Los trabajos en set2 siguen en orden decreciente de p 2j (LPT). Los lazos se rompen arbitrariamente.
Este tipo de horario se conoce como horario SPT (1) –LPT (2).
Malakooti (2013) proporciona una discusión detallada de los métodos de solución disponibles . [1]
Ver también
Referencias
- ↑ a b Malakooti, B (2013). Sistemas de Operaciones y Producción con Múltiples Objetivos. John Wiley e hijos. ISBN 978-1-118-58537-5 .
- ^ Garey, MR, Johnson, DS y Sethi, R. (1976). La complejidad de la programación de FlowShop y Jobshop .
Matemáticas de la investigación de operaciones, 1 (2), 117-129.
- ↑ a b Johnson, SM (1954). Programas de producción óptimos en dos y tres etapas con tiempos de preparación incluidos .
Logística de investigación naval trimestralmente, 1 (1), 61–68.
- ^ Taillard, E. (enero de 1993). "Benchmarks para problemas básicos de programación" . Revista europea de investigación operativa . 64 (2): 278-285. doi : 10.1016 / 0377-2217 (93) 90182-M .