En la ciencia de la computación teórica y la investigación de operaciones , el problema de programación de taller abierto ( OSSP ) es un problema de programación en el que un conjunto determinado de trabajos debe procesarse durante períodos de tiempo determinados en cada uno de un conjunto determinado de estaciones de trabajo, en un orden arbitrario. y el objetivo es determinar la hora a la que se procesará cada trabajo en cada estación de trabajo. El problema fue estudiado por primera vez por Teófilo F. González y Sartaj Sahni en 1976. [1]
Definición
Más precisamente, la entrada al problema de programación de la tienda abierta 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 debería 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 del taller de trabajo , el orden en el 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 modo que no se asignen dos trabajos a la misma estación de trabajo al mismo tiempo, no se asigne ningún trabajo 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 la calidad de una solución es su duración , la cantidad de tiempo desde el inicio del programa (la primera asignación de un trabajo a una estación de trabajo) hasta su final (la hora de finalización del último trabajo en la última estación de trabajo).
Complejidad computacional
El problema de la programación de la tienda abierta 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 el borde 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 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 las gráficas lineales de las gráficas bipartitas son gráficas perfectas , las gráficas bipartitas pueden tener color de borde en tiempo polinomial.
Para tres o más estaciones de trabajo, o tres o más trabajos, con diferentes tiempos de procesamiento, la programación de taller abierto es NP-difícil .
Ver también
- Programación de Flow Shop
- Programación del taller de trabajo
- Programación de tareas paralelas
Referencias
- ^ González, Teófilo; Sahni, Sartaj (1976), "Programación de taller abierto para minimizar el tiempo de finalización", Journal of the ACM , 23 (4): 665–679, CiteSeerX 10.1.1.394.1507 , doi : 10.1145 / 321978.321985 , MR 0429089.
- Williamson, DP ; Hall, LA; Hoogeveen, JA; Hurkens, CAJ; Lenstra, JK ; Sevast'janov, SV; Shmoys, DB (1997), "Short shop schedule", Operations Research , 45 (2): 288–294, doi : 10.1287 / opre.45.2.288 , JSTOR 171745 , MR 1644998.