Programación de flujo de taller

La programación de flujo de trabajo es un problema de optimización en ciencias de la computación e investigación operativa . 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 ₁ , J ₂ , ..., J _n con tiempos de procesamiento variables, que deben programarse en m máquinas con potencia de procesamiento variable, mientras se intenta minimizar el tiempo de finalización (makespan ), es decir, la duración total de la programación (cuando todos los trabajos han terminado de procesarse). En la variante específica conocida como programación de flujo de trabajo , 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 producción es un caso especial de programación de talleres de producción donde existe un orden estricto para todas las operaciones que se realizan en todos los trabajos. Este tipo de programación puede aplicarse tanto a instalaciones de producción como a diseños informáticos . Un tipo especial de problema de programación de flujo de producción es el problema de programación de flujo de producción por permutación, en el que el orden de procesamiento de los trabajos en los recursos es el mismo para cada paso de procesamiento subsiguiente.

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 por F en el primer campo. Por ejemplo, el problema denotado por " F3|${\displaystyle p_{ij}}$|${\displaystyle C_{\max }}$" es un problema de taller de flujo con 3 máquinas y 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 un tiempo de ejecución.

Las operaciones dentro de un mismo trabajo deben ejecutarse en el orden especificado. La primera operación se ejecuta en la primera máquina, luego (una vez finalizada la primera) la segunda en la segunda máquina, y así sucesivamente hasta la m -ésima operación. Sin embargo, los trabajos pueden ejecutarse en cualquier orden. El problema consiste en determinar la disposición óptima, es decir, aquella que minimiza el tiempo total de ejecución 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.

1. Tiempo de flujo (promedio),${\displaystyle \sum (w_{i})F_{i}}$
2. Tiempo de finalización, C _máx.
3. (Promedio) Tardanza,${\displaystyle \sum (w_{i})T_{i}}$
4. ....

En Malakooti (2013) se puede encontrar una discusión detallada sobre la medición del desempeño . ^{[ 1 ]}

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 puede resolverse de manera óptima utilizando la regla de Johnson . ^{[ 3 ]}

Taillard proporciona problemas de referencia sustanciales para la programación de talleres de flujo, talleres abiertos y talleres de trabajo. ^{[ 4 ]}

Los métodos propuestos para resolver problemas de programación de talleres de flujo se pueden clasificar como algoritmos exactos, como el método de ramificación y acotación , y algoritmos heurísticos , como el algoritmo genético .

• Programación de talleres abiertos
• Programación de talleres