La programación de flujo continuo es un problema de optimización en informática e investigación de operaciones . Es una variante de la programación óptima de trabajos . En un problema general de programación de trabajos, se nos dan n trabajos J 1 , J 2 , ..., J n de tiempos de procesamiento variables, que deben programarse en m máquinas con potencia de procesamiento variable, mientras se intenta minimizar el makespan – la longitud total de la programación (es decir, cuando todos los trabajos han terminado de procesarse). En la variante específica conocida como programación de flujo continuo , 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 flujo de trabajo es un caso especial de programación de flujo de trabajo en el que existe un orden estricto de todas las operaciones que se deben realizar en todos los trabajos. La programación de flujo de trabajo se puede aplicar tanto a instalaciones de producción como a diseños informáticos . Un tipo especial de problema de programación de flujo de trabajo es el problema de programación de flujo de trabajo de permutación en el que el orden de procesamiento de los trabajos en los recursos es el mismo para cada paso posterior del procesamiento.
En la notación estándar de tres campos para problemas de programación óptima de trabajos , la variante de taller de flujo se denota con F en el primer campo. Por ejemplo, el problema denotado con " F3| | " es un problema de taller de flujo de tres máquinas con tiempos de procesamiento unitarios, donde el objetivo es minimizar el tiempo máximo de finalización.
Hay m máquinas y n 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 la primera operación termina) la segunda operación en la segunda máquina, y así sucesivamente hasta la operación m -ésima. Sin embargo, los trabajos se pueden ejecutar en cualquier orden. La definición del problema implica que este orden de trabajo es exactamente el mismo para cada máquina. El problema es determinar la disposición óptima, es decir, la que tenga el menor tiempo posible de ejecución total del trabajo.
El problema de secuenciación puede plantearse como la determinación de una secuencia S tal que se optimicen uno o varios objetivos de secuenciación.
Se puede encontrar una discusión detallada sobre la medición del desempeño en Malakooti (2013). [1]
Como lo presentaron Garey et al. (1976), [2] la mayoría de las extensiones de los problemas de programación de flujo de trabajo son NP-duras y pocas de ellas se pueden resolver 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]
Los métodos propuestos para resolver problemas de programación de flujo de trabajo se pueden clasificar como algoritmos exactos, como el algoritmo de ramificación y límite , y algoritmos heurísticos , como el algoritmo genético .
F2|prmu|C max y F3|prmu|C max se pueden resolver de manera óptima utilizando la Regla de Johnson [3], pero para el caso general no existe un algoritmo que garantice la optimalidad de la solución.
El taller de flujo contiene n trabajos disponibles simultáneamente en el momento cero y que deben 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 de manera de minimizar el tiempo de fabricación. La regla de Johnson para programar trabajos en un taller de flujo de dos máquinas se presenta a continuación.
En un cronograma óptimo, el trabajo i precede al trabajo j si min{p 1i ,p 2j } < min{p 1j ,p 2i } . Donde p 1i es el tiempo de procesamiento del trabajo i en la máquina 1 y p 2i es el tiempo de procesamiento del trabajo i en la máquina 2. De manera similar, p 1j y p 2j son los tiempos de procesamiento del trabajo j en la máquina 1 y la máquina 2 respectivamente.
Para el algoritmo de Johnson:
Algoritmo de Johnson:
Este tipo de programación se denomina programación SPT(1)–LPT(2).
Malakooti (2013) ofrece una discusión detallada de los métodos de solución disponibles . [1]
