En el modelado matemático de los problemas de programación del taller de trabajo , los gráficos disyuntivos son una forma de modelar un sistema de tareas a programar y restricciones de tiempo que deben ser respetadas por el programa. Son gráficos mixtos , en los que los vértices (que representan tareas a realizar) pueden estar conectados por bordes tanto dirigidos como no dirigidos (que representan restricciones de tiempo entre tareas). Los dos tipos de aristas representan restricciones de dos tipos diferentes:
- Si una tarea x se deben realizar antes de una segunda tarea y , esta restricción está representado por una arista dirigida de x a y .
- Si, por el otro lado, dos tareas x y y se pueden realizar en cualquier orden, pero no simultáneamente (tal vez debido a que tanto la demanda el uso del mismo equipo u otro recurso), esta restricción no simultaneidad está representada por un borde no dirigido conectando x e y .
Los pares de tareas que no tienen restricciones en su orden (se pueden realizar en cualquier orden o incluso simultáneamente) están desconectados entre sí en el gráfico. [1] [2] [3]
Se puede obtener un cronograma válido para el grafo disyuntivo encontrando una orientación acíclica de los bordes no dirigidos, es decir, decidiendo para cada par de tareas no simultáneas cuál debe ser la primera, sin introducir dependencias circulares , y luego ordenando el resultado dirigido. gráfico acíclico . En particular, suponga que todas las tareas tienen la misma duración y el objetivo es encontrar un horario que minimice el lapso de tiempo, el tiempo total hasta que se hayan completado todas las tareas. En este caso, el Makingpan se puede calcular a partir de la ruta más larga en el gráfico orientado, que se puede encontrar en tiempo polinómico para gráficos acíclicos dirigidos. Sin embargo, la etapa de orientación de la solución es mucho más difícil: es NP-difícil encontrar la orientación acíclica que minimice la longitud del camino más largo. En particular, según el teorema de Gallai-Hasse-Roy-Vitaver , si todas las aristas no están dirigidas inicialmente, orientarlas para minimizar la ruta más larga equivale a encontrar una coloración gráfica óptima de la gráfica inicial no dirigida.
Referencias
- ^ Gröflin, H .; Klinkert, A. (2002), "Programación con gráficos disyuntivos generalizados: cuestiones de viabilidad", XV Conferencia del Capítulo Europeo de Optimización Combinatoria (ECCO XV), 30 de mayo - 1 de junio de 2002, Lugano, Suiza.
- ^ Olson, Lars E. (agosto de 2003), Querying Disjunctive Databases in Polynomial Time (PDF) , Tesis de maestría, Universidad Brigham Young, Departamento de Ciencias de la Computación.
- ^ Roy, S .; Sussman, B. (diciembre de 1964), Les problemes d'ordonnancement avec contraintes disjonctives , Nota DS No. 9 bis, SEMA.
Otras lecturas
- Balas, Egon (abril de 1969), Machine Sequencing: Disjunctive Graphs and Degree-Restrained Subgraphs , Informe No. 320–2971, IBM, Centro Científico de Nueva York.
- Balas, Egon (1969), "Secuenciación de máquinas a través de gráficos disyuntivos: un algoritmo de enumeración implícito", Investigación de operaciones , 17 : 941–957, doi : 10.1287 / opre.17.6.941 , MR 0250770.
- Błażewicz, Jacek; Pesch, Erwin; Sterna, Małgorzata (2000), "La representación de la máquina gráfica disyuntiva del problema de programación del taller", European Journal of Operational Research , 127 (2): 317–331, doi : 10.1016 / S0377-2217 (99) 00486-5.
- Mason, Scott J .; Oey, Kasin (2003), "Programación de talleres de trabajo complejos utilizando gráficos disyuntivos: un procedimiento de eliminación de ciclo", International Journal of Production Research , 41 (5): 981–994, doi : 10.1080 / 00207540210163009