La programación de flow-shop es un problema de optimización en informática e investigación de operaciones . Es una variante de la programación óptima del trabajo . 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 intervalo de tiempo – la duración total del programa (es decir, cuando todos los trabajos hayan terminado de procesarse). En la variante específica conocida como programación de taller de flujo , 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 existe un orden estricto de todas las operaciones que se realizarán en todos los trabajos. La programación de taller de flujo 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 de taller es el problema de programación de flujo de permutación en el que el orden de procesamiento de los trabajos en los recursos es el mismo para cada paso posterior de 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 indicado por " F3| | " es un problema de taller de flujo de 3 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 finaliza la primera operación) la segunda operación en la segunda máquina, y así sucesivamente hasta la ené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 cuál es la disposición óptima, es decir, aquella con el menor tiempo posible de ejecución total del trabajo.
El problema de secuenciación se puede plantear como determinar una secuencia S tal que se optimicen uno o varios objetivos de secuenciación.
Una discusión detallada sobre la medición del desempeño se puede encontrar en Malakooti (2013). [1]
Tal como lo presentan Garey et al. (1976), [2] la mayoría de las extensiones de los problemas de programación de talleres de flujo son NP-difíciles 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]
Los métodos propuestos para resolver problemas de programación de taller de flujo se pueden clasificar como algoritmo exacto , como rama y límite, y algoritmo heurístico , como 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 ningún 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. Se requiere programar n trabajos en las máquinas para minimizar el espacio de trabajo. A continuación se detalla la regla de Johnson para programar trabajos en un taller de flujo de dos máquinas.
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 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 programa se conoce como programa SPT(1)-LPT(2).
Malakooti (2013) proporciona una discusión detallada de los métodos de solución disponibles . [1]
