stringtranslate.com

Gráfico disyuntivo

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

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

Un cronograma válido para el grafo disyuntivo puede obtenerse hallando una orientación acíclica de los bordes no dirigidos –es decir, decidiendo para cada par de tareas no simultáneas cuál será la primera, sin introducir ninguna dependencia circular– y luego ordenando el grafo acíclico dirigido resultante . En particular, supongamos que todas las tareas tienen la misma longitud 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 makespan puede calcularse a partir de la ruta más larga en el grafo orientado, que puede encontrarse en tiempo polinomial para grafos acíclicos dirigidos. Sin embargo, la etapa de orientación de la solución es mucho más difícil: es NP-difícil hallar la orientación acíclica que minimice la longitud de la ruta más larga. En particular, por el teorema de Gallai–Hasse–Roy–Vitaver , si todos los bordes son inicialmente no dirigidos, entonces orientarlos para minimizar la ruta más larga es equivalente a hallar una coloración gráfica óptima del grafo no dirigido inicial.

Referencias

  1. ^ Gröflin, H.; Klinkert, A. (2002), "Programación con gráficos disyuntivos generalizados: cuestiones de viabilidad", 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, Brigham Young University, 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.

Lectura adicional