Programación de talleres abiertos

La programación de talleres abiertos o problema de programación de talleres abiertos ( OSSP ) 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 talleres abiertos , cada trabajo consta de un conjunto de operaciones O ₁ , O ₂ , ..., O _n que deben procesarse en un orden arbitrario . El problema fue estudiado por primera vez por Teofilo F. Gonzalez y Sartaj Sahni en 1976. ^{[ 1 ]}      

En la notación estándar de tres campos para problemas de programación óptima de trabajos , la variante de taller abierto se denota por O en el primer campo. Por ejemplo, el problema denotado por " O3|${\displaystyle p_{ij}}$|${\displaystyle C_{\max }}$" es un problema de taller de 3 máquinas con tiempos de procesamiento unitarios, donde el objetivo es minimizar el tiempo máximo de finalización.

La entrada al problema de programación de taller abierto consiste en un conjunto de n trabajos, otro conjunto de m estaciones de trabajo y una tabla bidimensional del tiempo que cada trabajo debe pasar en cada estación de trabajo (posiblemente cero). Cada trabajo solo puede procesarse en una estación de trabajo a la vez, y cada estación de trabajo solo puede procesar un trabajo a la vez. Sin embargo, a diferencia del problema de taller de trabajo , el orden en que ocurren los pasos de procesamiento puede variar libremente. El objetivo es asignar un tiempo para que cada trabajo sea procesado por cada estación de trabajo, de manera que no se asignen dos trabajos a la misma estación de trabajo al mismo tiempo, ningún trabajo se asigne a dos estaciones de trabajo al mismo tiempo, y cada trabajo se asigne a cada estación de trabajo durante el tiempo deseado. La medida habitual de calidad de una solución es su tiempo de finalización (makespan) , que es el tiempo transcurrido desde el inicio de la programación (la primera asignación de un trabajo a una estación de trabajo) hasta su finalización (el tiempo de finalización del último trabajo en la última estación de trabajo).

El problema de programación de talleres abiertos se puede resolver en tiempo polinomial para instancias con solo dos estaciones de trabajo o solo dos trabajos. También se puede resolver en tiempo polinomial cuando todos los tiempos de procesamiento distintos de cero son iguales: en este caso, el problema se vuelve equivalente a colorear las aristas de un grafo bipartito cuyos vértices son los trabajos y las estaciones de trabajo, y que tiene una arista por cada par trabajo-estación de trabajo con un tiempo de procesamiento distinto de cero. El color de una arista en la coloración corresponde al segmento de tiempo en el que se programa el procesamiento de un par trabajo-estación de trabajo. Dado que los grafos de líneas de los grafos bipartitos son grafos perfectos , los grafos bipartitos se pueden colorear en tiempo polinomial.

Para tres o más estaciones de trabajo, o tres o más trabajos, con tiempos de procesamiento variables, la programación de taller abierto es NP-difícil . ^{[ 2 ]}

• La planificación de talleres de producción es un problema similar, pero con una restricción adicional : las operaciones deben realizarse en un orden específico. 
• La programación de flujo en taller es una programación de taller por encargo, pero con unarestricción de flujo adicional : cada operación debe realizarse en una máquina específica.