La programación de taller abierto o problema de programación de taller abierto ( OSSP ) 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 necesitan ser programados en m máquinas con potencia de procesamiento variable, mientras se intenta minimizar el makespan - la longitud total del cronograma (es decir, cuando todos los trabajos han terminado de procesarse). En la variante específica conocida como programación de taller abierto , cada trabajo consta de un conjunto de operaciones O 1 , O 2 , ..., O n que necesitan ser procesadas en un orden arbitrario . El problema fue estudiado por primera vez por Teófilo 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 con O en el primer campo. Por ejemplo, el problema denotado por " O3| | " es un problema de taller de tres 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 de la cantidad de tiempo que cada trabajo debe pasar en cada estación de trabajo (posiblemente cero). Cada trabajo puede procesarse solo en una estación de trabajo a la vez, y cada estación de trabajo puede procesar solo un trabajo a la vez. Sin embargo, a diferencia del problema de taller , el orden en el que ocurren los pasos de procesamiento puede variar libremente. El objetivo es asignar un tiempo para que cada estación de trabajo procese cada trabajo, de modo 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 la cantidad de tiempo deseada. La medida habitual de la calidad de una solución es su makespan , la cantidad de tiempo desde el inicio de la programación (la primera asignación de un trabajo a una estación de trabajo) hasta su final (el tiempo de finalización del último trabajo en la última estación de trabajo).
El problema de programación de taller abierto se puede resolver en tiempo polinomial para instancias que tienen 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 los bordes de un gráfico bipartito que tiene los trabajos y las estaciones de trabajo como sus vértices, y que tiene un borde para cada par trabajo-estación de trabajo que tiene un tiempo de procesamiento distinto de cero. El color de un borde en la coloración corresponde al segmento de tiempo en el que se programa el procesamiento de un par trabajo-estación de trabajo. Debido a que los gráficos de línea de los gráficos bipartitos son gráficos perfectos , los gráficos bipartitos pueden colorearse en los bordes 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-dura . [2]
