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 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 espacio de trabajo . 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 abierto , cada trabajo consta de un conjunto de operaciones O 1 , O 2 , ..., On que deben procesarse en un orden arbitrario . El problema fue estudiado por primera vez por Teófilo F. González y Sartaj Sahni en 1976. [1]
En la notación estándar de tres campos para problemas óptimos de programación de trabajos , la variante de taller abierto se indica con O en el primer campo. Por ejemplo, el problema indicado por " O3| | " 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 talleres abiertos consta de 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 se puede procesar sólo en una estación de trabajo a la vez, y cada estación de trabajo sólo puede procesar un trabajo a la vez. Sin embargo, a diferencia del problema del taller , el orden en que ocurren los pasos del procesamiento puede variar libremente. El objetivo es asignar un tiempo para que cada trabajo sea procesado por cada estación de 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 todos los trabajos se asignen. a cada estación de trabajo durante el tiempo deseado. La medida habitual de la calidad de una solución es su intervalo de tiempo , la cantidad de tiempo desde el inicio del cronograma (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 polinómico para instancias que tienen solo dos estaciones de trabajo o solo dos trabajos. También se puede resolver en tiempo polinómico 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 vértices, y que tiene un borde para cada par de 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 está programado el procesamiento de un par de trabajo-estación de trabajo. Debido a que las gráficas lineales de las gráficas bipartitas son gráficas perfectas , las gráficas bipartitas pueden tener colores de borde 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]
