Soutenance mémoire
Ordonnancement cumulatif en programmation par contraintes
En 1974, Baker définit dans [3] un problème d’ordonnancement comme l’allocation de ressources à des activités à travers le temps. La résolution d’un problème d’ordonnancement consiste à déterminer les dates de début et de fin d’un ensemble de tâches soumises à différents types de contraintes (e.g. contraintes de ressource, d’enchainement, de délai). Il existe une grande variété de problèmes d’ordonnancement comme les problèmes disjonctifs, cumulatifs, avec ou sans préemption. . . On trouve une classification bien connue en ordonnancement qui est celle de Graham [32]. Dans cette thèse, nous nous intéresserons aux problèmes d’ordonnancement cumulatifs sans préemption. Dans cette configuration, une tâche est définie par une date de début, une durée, une date de fin, et une hauteur représentant sa consommation à chaque point de temps de son exécution. La résolution d’un problème d’ordonnancement cumulatif consiste à déterminer les dates de début et de fin des tâches sans que la hauteur cumulée des tâches s’exécutant à chaque point de temps ne dépasse la quantité de ressource disponible.
La contrainte cumulative
En programmation par contraintes, la contrainte cumulative a été introduite par Aggoun et Beldiceanu dans [2] pour modéliser des problèmes d’ordonnancement cumulatifs.
Exprimée de manière plus informelle, la contrainte cumulative est satisfaite si la somme des hauteurs des tâches s’exécutant à chaque point de temps est inférieure ou égale à la capacité maximale de la ressource. Plusieurs types de raisonnements ont été développés pour écrire des algorithmes de filtrage pour cette contrainte, comme la méthode de Timetabling présentée par Le Pape dans [41], l’Edge-Finding introduit et développé dans [49, 48, 50, 46, 71, 37], l’Energetic Reasonning [25, 45, 44, 4], Not First / Not Last [65, 64], Task Intervals [20, 21], Overload Checking [73], ainsi que des méthodes basées sur les problèmes de sac à dos [12, 10]. Les raisonnements de Timetabling et d’Edge-Finding effectuent des filtrages différents qui semblent être incomparables. En effet, Vilim propose en 2011 une méthode très efficace issue de la combinaison de ces deux méthodes dans [72]. Cet algorithme a été repris et expliqué en 2013 par Schutt, Feydy et Stuckey dans [63] et est actuellement la méthode la plus performante sur les instances de la PSPLib [56].
Différents filtrages pour la contrainte cumulative
Nous présentons maintenant, de manière brève, les principaux algorithmes de filtrage pour la contrainte cumulative basés sur la notion d’énergie. Nous précisons également pour chacun d’eux les principales raisons nous laissant penser qu’ils sont ou ne sont pas les meilleures approches pour traiter des instances de très grande taille.
Edge-Finding L’Edge-Finding est une technique permettant de déduire des relations de précédence entre les tâches au regard de leur fenêtre temporelle, leur énergie et de l’énergie disponible sur certains intervalles. Grâce à ces précédences, il est alors possible de filtrer les dates de début et de fin des tâches. D’abord développés pour les problèmes d’ordonnancement disjonctifs [18], les algorithmes d’Edge-Finding ont ensuite été adaptés au cas cumulatif [48, 4]. Pour la contrainte cumulative, l’algorithme d’Edge-Finding le plus performant est celui de Kameugne et al. [37] dont la complexité temporelle dans le pire des cas est O(n2), où n désigne le nombre de tâches. Dans l’optique du passage à l’échelle, les algorithmes d’Edge-Finding ne nous semblent pas être les meilleurs candidats. En effet la complexité temporelle dans le pire des cas de l’algorithme de Kameugne et al., i.e. O(n2) est toujours atteinte.
Timetable Edge-Finding En 2011, Vilim propose un nouvel algorithme [72] utilisant à la fois les raisonnements d’Edge-Finding et de Timetabling. Tout en conservant la même complexité que l’algorithme d’Edge-Finding de Kameugne et al. (i.e. O(n2)), ce nouvel algorithme apporte un filtrage plus puissant au niveau déductif. Pour les mêmes raisons que celles évoquées pour l’Edge-Finding de Kameugne et al., cet algorithme ne nous semble pas être le meilleur candidat pour traiter des problèmes cumulatifs de très grande taille.
Energetic Reasoning L’Energetic Reasoning est un raisonnement introduit et développé dans [25, 45, 44, 4] dominant l’Edge-Finding. L’idée est de déterminer dans un premier temps la demande énergétique minimale des tâches sur un intervalle de temps donné, puis dans un second temps, de filtrer les tâches en observant la différence entre la quantité d’énergie offerte par l’intervalle et cette demande. Dans [4], Baptiste et al. précisent que le nombre d’intervalles d’intérêt est de O(n2) et que l’on peut ajuster les n tâches sur chacun de ces intervalles, et donc que la complexité de leur algorithme est O(n3). Une complexité temporelle de O(n3) semble rédhibitoire en vue du passage à l’échelle.
Timetabling Les premiers algorithmes de filtrage pour la contrainte cumulative sont basés sur la notion de partie obligatoire, initialement introduite par Lahrichi en 1982 [40]. Ces algorithmes construisent un profil des parties obligatoires (PPO) des tâches et l’utilisent pour filtrer les dates de début des tâches afin de ne pas dépasser la capacité de la ressource. Pour définir la notion de PPO nous rappelons tout d’abord la définition d’une instance réalisable d’une tâche et la définition de partie obligatoire d’une tâche, initialement introduite par Lahrichi [40].
Algorithme de balayage de 2001 pour la contrainte cumulative
L’algorithme de balayage pour la contrainte cumulative proposé dans [8] en 2001 repose sur un principe largement utilisé en géométrie algorithmique appelé balayage, ou sweep [24]. En programmation par contraintes, ce principe a déjà été utilisé pour implémenter un algorithme de filtrage pour la contrainte de non overlapping ainsi que d’autres contraintes géométriques [7]. Dans un espace à deux dimensions, l’algorithme de balayage [24] résout le problème en déplaçant une droite verticale, appelée droite de balayage, de gauche à droite et en utilisant deux éléments :
• L’état de la droite de balayage, qui contient les informations relatives à la position courante δ de la droite de balayage.
• La série d’évènements, qui contient l’ensemble des évènements à traiter, ordonnée par ordre croissant suivant l’axe du temps.
L’algorithme commence par initialiser l’état de la droite de balayage à la position initiale. Ensuite, la droite « saute » d’évènement en évènement, chacun d’entre eux étant traité puis inséré ou retiré de l’état de la droite de balayage de manière incrémentale. Dans le contexte de la contrainte cumulative, la droite de balayage parcourt l’axe du temps pour construire le profil des parties obligatoires (PPO), effectuer des vérifications de non dépassement du plafond de ressource et filtrer les domaines des variables selon ce profil et la capacité de la ressource. L’algorithme de balayage de 2001 est une implémentation de la méthode de Timetabling présentée dans [41]. Nous introduisons maintenant un exemple qui sera utilisé et étendu par la suite pour illustrer les différents algorithmes de balayage présentés dans cette thèse.
|
Table des matières
1 Introduction
I État de l’art
2 La programmation par contraintes
2.1 Modélisation d’un problème de contraintes
2.2 Résolution d’un problème de contraintes
3 Ordonnancement cumulatif en programmation par contraintes
3.1 La contrainte cumulative
3.2 Différents filtrages pour la contrainte cumulative
3.3 Algorithme de balayage de 2001 pour la contrainte cumulative
3.3.1 Types d’évènements
3.3.2 État de la droite de balayage
3.3.3 Algorithme de filtrage
3.3.4 Complexité d’une phase de balayage
3.4 Synthèse critique
II Contribution : vers un algorithme de filtrage intégrant une conjonction de contraintes cumulative, cumulative colorée et précédence
4 Motivation et démarche : passage à l’échelle en maîtrisant la convergence au point fixe
4.1 Faiblesses de l’algorithme de balayage de 2001
4.2 Solutions préconisées
5 Algorithme de balayage dynamique pour une seule contrainte cumulative
5.1 Propriété
5.2 Types d’évènements
5.3 État de la droite de balayage
5.4 Algorithme de filtrage
5.4.1 Algorithme principal
5.4.2 Filtrage
5.4.3 Resynchronisation des évènements
5.5 Correction et propriété vérifiée par sweep_min
5.6 Complexité
6 Balayage synchrone pour plusieurs contraintes cumulative avec ou sans précédences
6.1 Une première approche sans contrainte de précédence
6.1.1 Types d’évènements
6.1.2 État de la droite de balayage
6.1.3 Algorithme de filtrage
6.1.4 Complexité
6.2 Une seconde approche intégrant les contraintes de précédence
6.2.1 Types d’évènements
6.2.2 État de la droite de balayage
6.2.3 Algorithme de filtrage
6.2.4 Complexité
6.3 Cumulative colorée : ou comment remplacer la somme par le nombre de valeurs distinctes
6.3.1 Définition de la contrainte multiSumColorPrecCumulative
6.3.2 Schémas classiques d’apparition de la contrainte multiSumColorPrecCumulative
6.3.3 Reformulation quadratique de la contrainte cumulative colorée
6.3.4 Intégration au balayage synchrone avec précédences
7 Synthèse des nouveaux algorithmes de balayage
7.1 Algorithme de balayage dynamique
7.2 Algorithme de balayage synchrone sans précédence
7.3 Algorithme de balayage synchrone avec précédences
III Améliorations pratiques et évaluation
8 Améliorations pratiques
8.1 Mieux gérer les matrices creuses de consommations
8.2 Agrégation des parties obligatoires
8.3 Mode glouton
8.3.1 Types d’évènements
8.3.2 État de la droite de balayage
8.3.3 Algorithme glouton
9 Évaluation
9.1 Présentation des problèmes sélectionnés
9.2 Instances aléatoires
9.3 Instances de la PSPLib
9.4 Redéploiement d’un réseau d’informations financières à grande échelle
10 Conclusion
Annexe
