Resumen: Se sabe que lograr la coherencia ligada para la restricción sin superposición es NP-completo. Por lo tanto, para esta restricción se han introducido varias técnicas de ajuste del tiempo polinomial, como la búsqueda de aristas, el razonamiento no primero ni el último y el razonamiento energético. En este trabajo, derivamos el primer algoritmo de coherencia límite para la restricción de no superposición. Al basarnos en el MDD sin superposición definido por Ciré y van Hoeve, extraemos los límites de la ventana de tiempo de los trabajos, lo que nos permite ajustar los tiempos de inicio y finalización en polinomio de tiempo en el número de nodos del MDD. De manera similar, para limitar el tamaño y la complejidad temporal, limitamos el ancho del MDD a un umbral, creando un MDD relajado que también se puede utilizar para relajar el filtrado coherente con límites. A través de experimentos sobre un problema de secuenciación con ventanas de tiempo y un objetivo justo a tiempo ($1 mid r_j, d_j, bar{d}_j mid sum E_j + sum T_j$), observamos que el filtrado propuesto, incluso con un umbral en el ancho, logra una reducción más fuerte en el número de nodos visitados en el árbol de búsqueda en comparación con el algoritmo de detección de precedencia propuesto previamente por Ciré y van Hoeve. El nuevo filtrado también parece ser complementario a los métodos de propagación clásicos para la restricción de no superposición, permitiendo una reducción sustancial tanto en el número de nodos como en el tiempo de resolución en varias instancias.
Publicado originalmente en export.arxiv.org el 21 de enero de 2026.
Ver fuente original
