Scheduling and constraint propagation (Q697570)

Un projet comporte \(n\) activités (ou tâches) \(i\) utilisant \(r\) ressources renouvelables disponibles en quantités limitées à chaque instant. En vue d'ordonnancer le projet, il importe de répertorier les constraintes de base sur les activités et d'étudier comment elles se propagent dans le graphe d'ordonnancement. Par exemple, une contrainte peut être: -- une précédence notée \(i\to j\) si \(j\) ne peut commencer que si \(i\) est terminée, ce qui implique, si \(i\) dure \(p_i\) unités de temps, la conjonction: \(S_i+p_i\leq S_j\) où désigne la date de début de tâche. -- un parallélisme noté \(i\|j\) si ni \(i\to j\) ni \(j\to i\) n'est vrai, ou une disjonction \(i\to j\) qui en est la négation. Dans ces conditions, si \(i \|k\) et \(j\|k\) et si \(i,j,k\) sont insécables et ne peuvent se dérouler simultanément par manque de ressources, la contrainte \(i-j\) en découle. Ce papier étudie ainsi une procédure de propagation de constraintes et des algorithmes (Branch-and-Bound, heuristiques) dont la complexité est évaluée et qui fournissent des ordonnancements compatibles avec les constraintes et dont la qualité peut être appréciée par rapport à une borne inférieure de la durée du projet. Un tableau comparatif d'algorithmes alternatifs est fourni ainsi qu'une cinquantaine de références bibliographiques.