Grafo disyuntivo

Manera de representar problemas de programación mostrando las tareas y las reglas de tiempo que deben seguir.

En el modelado matemático de problemas de programación de talleres , los gráficos disyuntivos son una forma de modelar un sistema de tareas a programar y restricciones de tiempo que el cronograma debe respetar. Son gráficos mixtos , en los que los vértices (que representan tareas a realizar) pueden estar conectados por aristas dirigidas y no dirigidas (que representan restricciones de tiempo entre tareas). Los dos tipos de aristas representan restricciones de dos tipos diferentes:

• Si una tarea x debe realizarse antes que una segunda tarea y , esta restricción se representa mediante un borde dirigido de x a y .
• Si, por otro lado, dos tareas x e y se pueden realizar en cualquier orden, pero no simultáneamente (quizás porque ambas exigen el uso del mismo equipo u otro recurso), esta restricción de no simultaneidad está representada por una arista no dirigida. conectando x e y .

Los pares de tareas que no tienen restricciones en su orden (pueden realizarse en cualquier orden o incluso simultáneamente) están desconectados entre sí en el gráfico. ^{[1] [2] [3]}

Se puede obtener una programación válida para el grafo disyuntivo encontrando una orientación acíclica de las aristas no dirigidas (es decir, decidiendo para cada par de tareas no simultáneas cuál será la primera, sin introducir dependencias circulares ) y luego ordenando las tareas dirigidas resultantes. gráfico acíclico . En particular, supongamos que todas las tareas tienen la misma duración y el objetivo es encontrar un cronograma que minimice el makespan, el tiempo total hasta que se hayan completado todas las tareas. En este caso, el makepan 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 todos los bordes inicialmente no están dirigidos, orientarlos para minimizar el camino más largo es equivalente a encontrar una coloración gráfica óptima del gráfico no dirigido inicial.

Referencias

1. Gröflin, H.; Klinkert, A. (2002), "Scheduling with generalized disjunctive Graphs: Feasibility issues", XV Conferencia del Capítulo Europeo sobre Optimización Combinatoria (ECCO XV), 30 de mayo - 1 de junio de 2002, Lugano, Suiza.
2. Olson, Lars E. (agosto de 2003), Consulta de bases de datos disyuntivas en tiempo polinomial (PDF) , tesis de maestría, Universidad Brigham Young, Departamento de Ciencias de la Computación.
3. Roy, S.; Sussman, B. (diciembre de 1964), Les problemes d'ordonnancement avec contraintes disjonctives , Nota DS N° 9 bis, SEMA.

Otras lecturas

• Balas, Egon (abril de 1969), Secuenciación automática: gráficos disyuntivos y subgrafos restringidos por grados , Informe n.º 320–2971, IBM, Centro científico de Nueva York.
• Balas, Egon (1969), "Secuenciación de máquinas mediante 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", Revista europea de investigación operativa , 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 ciclos", Revista Internacional de Investigación de Producción , 41 (5): 981–994, doi :10.1080/00207540210163009