Caractérisations des raisonnements pour la contrainte Cumulative 

L’ordonnancement cumulatif

L’ordonnancement en programmation par contraintes

Baker définit dans [Bak74] les problèmes d’ordonnancement comme des problèmes d’allocation de ressources à des activités positionnées dans le temps. On notera la différence entre une activité et un intervalle par le fait qu’une activité consomme une certaine quantité de ressources. On parlera aussi de sa hauteur, en référence à la représentation schématique d’une activité. Dans cette thèse, nous considérons que cette demande est constante dans le temps.
Définition 3.1 (Activité). Une activité a est représentée par un quadruplet de variables : sa hauteur h a (h pour height en anglais), sa durée p a (p pour processing time en anglais), sa date de début s a (s pour start en anglais) et sa date de fin e a (e pour end en anglais). Elle respecte sa contrainte d’intégrité.

Les filtrages de la contrainte Cumulative

Bien qu’une activité soit définie sur 4 variables : s, d, e, h les principaux raisonnements se placent dans le cas où la consommation et la durée sont fixées et positives et les débuts et fins de consommation sont représentés par des variables bornées. Dans la suite de ce manuscrit, nous nous plaçons dans cette hypothèse. On peut remarquer que, puisque la durée est fixe, s et e sont directement liées par la contrainte (1) d’intégrité d’une activité. Assurer la cohérence de s assure la cohérence de e. De plus, le problème cumulatif est symétrique : l’image d’un problème vu d’un miroir est équivalent au problème lui-même (ou plus formellement en changeant la variable de début s et la variable de fin e par s ′ = −e et e ′= −s). Cette symétrie permet, avec un raisonnement pour la cohérence de la borne inférieure, d’assurer aussi la cohérence de la borne supérieure. Le plus souvent, les raisonnements et algorithmes ne présentent donc que le filtrage du début au plus tôt.
L’existence d’une solution d’un problème cumulatif est un problème NP-complet [GJ79], dans le cas ou toutes les variables sont bornées. Un algorithme assurant la consistance aux bornes assure qu’il existe une solution avec cette borne. Par conséquent, on ne peut avoir un algorithme polynomial assurant la BC. C’est pourquoi, différents raisonnements relaxant Cumulative ont été introduits. Dans cette section, nous présentons les principaux raisonnements tel qu’ils sont couramment utilisés, par ordre croissant de complexité.
Nous commencerons par présenter en détail le raisonnement Time-Table [Lah82] et l’algorithme de Letort et al. [LCB14] que nous allons adapter pour le cas robuste dans le chapitre 5. puis nous présenterons les raisonnements Edge-Finding [Nui94], Time-Table-Edge-Finding [Vil11] et le Raisonnement Energétique [ELT89]. Ces raisonnements utilisent des notions similaires de calcul de consommation pour lesquels nous proposerons une uniformisation dans la section 4. Finalement, nous proposerons une caractérisation précise des intervalles qu’il est intéressant de considérer pour le raisonnement énergétique.

Time-Table-Edge-Finding

Vilím propose d’améliorer le raisonnement Edge-Finding en prenant en compte, dans le calcul de l’énergie consommée dans un intervalle, les parties obligatoires du raisonnement Time-Table [Vil11].
L’algorithme proposé, qui est en O(n 2 ), est actuellement l’algorithme le plus performant en pratique pour résoudre des problèmes cumulatifs de la PSPLib [KS96]. Dans un solveur de contrainte basé sur la génération paresseuse de clauses, sa version expliquée a permis d’améliorer les benchmarks typiques de la littérature [SFS13].
L’idée du raisonnement Time-Table-Edge-Finding est donc d’ajouter l’énergie du raisonnement Time-Table au raisonnement Edge-Finding. Pour éviter de comptabiliser deux fois l’énergie consommée dans un intervalle, Vilím propose de séparer en deux la durée d’une activité : la partie fixe noté p T T correspondant à la durée de la partie obligatoire, et la partie libre p EF , le complément, chacune servant au calcul du raisonnement associé :

La notion de robustesse

La robustesse d’une solution peut se définir comme sa capacité à garder ses performances suite à une modification des données. Dans de nombreuses applications réelles, la notion de satisfiabilité (et a fortiori d’optimalité) est souvent secondaire, et trouver des solutions offrant des compromis est souvent nécessaire. Par exemple la solution d’un problème d’ordonnancement est souvent assez peu stable : si l’une des activités venait à être retardée l’ensemble des activités pourraient en être impacté ; de plus la performance en est souvent grandement affectée.
Pour répondre à ce genre de problématiques, de nombreuses méthodes ont été proposées.
Qu’elles soient réactives ou proactives, la plupart sont stochastiques [Pin12]. Les méthodes réactives, qui permettent de réparer les solutions lorsqu’une perturbation est connue s’opposent aux méthodes proactives, qui proposent des solutions anticipant les perturbations.
Alors que les modèles stochastiques permettent d’envisager des variables aléatoires sur lesquelles la théorie des probabilités peut être appliquée, dans de nombreux cas pratiques, soit l’utilisateur final ne dispose pas de données adéquates avec lesquelles travailler, soit les modèles probabilistes ne sont tout simplement pas pertinents. Par conséquent, les modèles d’optimisation déterministes qui tiennent compte de toutes les incertitudes possibles ont été largement étudiés dans les quinze dernières années, principalement à travers le concept de solution robuste, par exemple, [DJB01, BN02, BS03, BS04, BMS08, WBB09, ZVS + 13, DPZ14a].
Nous décrivons ici les approches robustes qui sont directement liées à la contribution présentée dans le chapitre 5 : une approche qui soit à la fois proactive, déterministe et qui, bien que dédiée aux problèmes d’ordonnancements, reste modulaire, de manière à couvrir un ensemble de problèmes le plus large possible.

Intervalles d’intérêt pour la détection d’incohérence

Dans cette section nous proposons de caractériser le plus finement possible les intervalles qu’il est nécessaire de vérifier pour assurer la détection d’une incohérence. En effet les différentes caractérisations que nous avons vues dans la section précédente ont toutes été définies comme étant un raisonnement sur l’ensemble des N 2 intervalles. Or, il est inutile de considérer un intervalle qui est en dehors de l’horizon de toute activité, car la consommation sur cet intervalle sera nulle. On peut donc limiter les raisonnements aux intervalles inclus dans [min a∈A s a , maxa∈A e a [. Pour chacun des raisonnements, il est possible de réduire encore l’ensemble des intervalles d’intérêts. Nous proposons d’étudier au cas par cas chacun des raisonnements et d’en donner une caractérisation la plus fine possible, c’est-à-dire caractériser le moins possible d’intervalles comme étant d’intérêt.

Time-Table

Dans un souci d’unification, la formule (34) de consommation du raisonnement Time-Table prend en considération tous les intervalles de la forme [t 1, t 2 [, t 1 , t 2 ∈ N 2 . Pour le raisonnement Time-Table il est possible de ne considérer qu’un nombre d’intervalles correspondant au nombre d’activités ayant une partie obligatoire. En effet, seuls les intervalles de la forme [s a , s a + 1[, c’est-à-dire le début de partie obligatoire, pour chaque activité a ayant une partie obligatoire sont d’intérêts. La formule devient alors :

Relations de dominance des détections d’incohérence

Dans cette section, nous proposons une comparaison des relations de dominance entre les algorithmes de détection d’incohérence, pour cela nous considérons la caractérisation proposée dans la section 4.1.
Pour évaluer les dominances entre raisonnements, il suffit de comparer la fonction de consommation. Si la consommation d’un raisonnement est toujours inférieure, alors celui-ci ne peut détecter d’échec sans que le premier ne le détecte aussi ; il est dominé.
Proposition 4.1 (Time-Table-Edge-Finding ≤ Raisonnement Energétique). Démonstration. Comparons les fonctions ConsoER (formule (32), page 54) et ConsoTTEF (formule (38), page 55) en comparant la consommation d’une activité a en fonction de son inclusion dans un intervalle quelconque [t 1 , t 2[.
Dans la formule de consommation Time-Table-Edge-Finding, Ω représente l’ensemble des activités entièrement incluses dans [t 1 , t 2 [. La consommation de a est donc comptabilisée soit au titre de ConsoEF, soit au titre de ConsoTT.
Si l’activité a appartient complètement à l’intervalle [t 1 , t 2 [, elle est comptabilisée dans ConsoEF et la consommation est égale à celle du raisonnement énergétique.
Si l’activité n’est pas entièrement incluse, alors elle est comptabilisée dans ConsoTT, qui est inférieure ou égale à la consommation du raisonnement énergétique.
La consommation ConsoTTEF du raisonnement Time-Table-Edge-Finding est donc inférieure ou égale à la consommation ConsoER du raisonnement énergétique ; donc le raisonnement Time-Table-Edge-Finding est dominé par le raisonnement énergétique. Proposition 4.2 (Time-Table ≤ Time-Table-Edge-Finding).Démonstration. Exprimée comme dans l’equation (37) (page 55), la consommationTime-Table-Edge-Finding est trivialement supérieure ou égale à la consommation Time-Table. Par conséquent le raisonnement Time-Table-Edge-Finding domine le raisonnement Time-Table. Rappelons que Vilím a considéré, en introduisant l’algorithme Time-Table-Edge-Finding, qu’un algorithme Time-Table est préalablement appliqué. Par conséquent bien que leraisonnement Time-Table-Edge-Finding domine le raisonnement Time-Table, l’algorithmeTime-Table-Edge-Finding ne cherche pas à ré-effectuer ce qui est deja effectué par un algorithme Time-Table ; il ne domine pas en ce sens les algorithmes Time-Table.

La démonstration de la dominance de Time-Table-Edge-Finding sur les raisonnements

Edge-Finding initialement proposée se base uniquement sur les calculs de l’énergie [Vil11].
Et en effet, comme nous l’avons démontré, le calcul de l’énergie du raisonnement Time-Table-Edge-Finding domine ceux du raisonnement Edge-Finding. Le contre-exemple qu’expose Kameugne tient dans la caractérisation des intervalles d’intérêt. En effet, en limitant le test de propagation aux ensembles d’activités ayant une partie libre, l’algorithme ne considère pas les activités fixées, qui peuvent également apporter un filtrage. Dans l’exemple 4.1, l’algorithme Time-Table-Edge-Finding ignore l’ensemble Ω = {a 1 , a 2 , a 3 } car l’activité a 3 est fixée. Nous pourrions en déduire que Time-Table-Edge-Finding et Edge-Finding ne sont pas comparables.
Dans un solveur de contraintes, il est commun de cumuler plusieurs raisonnements pour améliorer le filtrage. L’ajout du propagateur Time-Table est souvent réalisé, car il est rapide à exécuter. Nous allons maintenant démontrer que, comme pour l’algorithme de détection d’incohérence, si l’on considère que le raisonnement Time-Table a été appliqué, alors le raisonnement Time-Table-Edge-Finding domine le raisonnement Edge-Finding.
Nous avons deja montré que le calcul de l’énergie du raisonnement Time-Table-Edge-Finding est plus grand que celui du raisonnement Edge-Finding. Il nous reste donc à montrer que les intervalles non caractérisés par l’algorithme sont dominés.

Conclusions et Perspectives

Dans ce chapitre, nous avons proposé une étude théorique des différents raisonnements pour la contrainte Cumulative. Nous avons montré que les principaux raisonnements pouvaient être vus comme des raisonnements basés sur l’énergie sur un intervalle de temps, tel que présenté par la propriété 4.1.
En ce basant sur cette notion de consommation sur un intervalle et en comparant directement les fonctions correspondantes, nous avons pu redonner des démonstrations simples sur les relations de dominances entre les différentes règles de détection d’incohérence. Nous avons aussi pu montrer qu’appliqué avec un propagateur Time-Table le raisonnement Time-Table-Edge-Finding domine le raisonnement Edge-Finding, comme annoncé dans [Vil11].
Dans le cadre du raisonnement énergétique, en étudiant plus finement les propriétés de la fonction de consommation sur un ensemble d’activités, nous avons obtenu les deux résultats théoriques suivants :
• nous avons montré qu’il était possible de réduire le nombre d’intervalle d’intérêt tout en conservant la complétude du filtrage (théorème 4.4, page 66), ce qui réponds à une question laissé ouverte par Baptiste et al. [BLN01, page 89].
• nous avons réduit significativement le nombre d’intervalles d’intérêt à considerer dans l’algorithme de détection d’incohérence et de filtrage (sections 4.2.4 et 4.4.1). D’un point de vue pratique, cette réduction du nombre d’intervalles à considerer a amené, sur le tempsd’exécution du propagateur, à des gains d’un facteur compris entre deux et quatre.
Ces résultats ouvrent des perspectives intéressantes concernant le propagateur énergétique.
Notre travail, principalement théorique, a naturellement aboutit à un nouvel algorithme du raisonnement énergétique. Une perspective est d’aboutir à un algorithme ayant un temps d’exécution encore plus faible que les algorithmes actuels du raisonnement énergétique, tout en gardant un pouvoir de filtrage plus élevé que l’algorithme Time-Table-Edge-Finding.
Ces travaux on fait l’objet d’une publication à la conférence internationale CP’14 [DP14], puis d’une communication à la conférence nationale JFPC’14 [Der14].

Détection d’incohérence

Nous avons vu, dans les chapitres précédents, que le raisonnement Time-Table permet de détecter efficacement les incohérences pour des problèmes à plusieurs milliers d’activités. Nous avons donc cherché à adapter ce raisonnement à la contrainte FlexC.
Nous venons de voir que le problème pouvait se modéliser à l’aide d’une décomposition en n contraintes Cumulative. Nous cherchons donc à obtenir un niveau de consistance équivalent à la consistance obtenue par l’application du raisonnement Time-Table sur chacune des n contraintes
Cumulative sans créer explicitement ces n contraintes Cumulative. Pour cela nous introduisons la notion de partie K-obligatoire, le complément entre la partie obligatoire de l’activité rallongéeet la partie obligatoire de l’activité d’origine.

Algorithme de filtrage

Dans la section 5.2.3, nous venons de proposer une adaptation du raisonnement Time-Table à la contrainte FlexC. Nous proposons maintenant un algorithme pour effectuer le filtrage correspondant. L’algorithme de balayage SWEEP_MIN est capable de résoudre des problèmes de grande taille, c’est-à-dire des problèmes pouvant aller jusqu’à plusieurs dizaines, voire centaines de milliers d’activités [LCB14].
Dans l’état de l’art (section 3.1.3, page 29), nous avons donné les détails de l’algorithme de balayage dynamic sweep de Letort et al. que nous adaptons pour la contrainte FlexC dans cette section. Pour rappel, le principe est de faire évoluer ce que l’on appelle une droite de balayage, de la gauche vers la droite de l’horizon de temps, en suivant les évènements stockés dans une structure de données nommée h event. L’algorithme maintient, à chaque point de temps, la hauteur restant disponible pour les activités dans la variable gap, ainsi que l’état de chaque activité :
• Si une activité ne respecte pas la contrainte de capacité, elle est dite en conflit et est stockée dans une structure de données nommée h conf lict .
• Si elle n’est pas en conflit, alors elle est stockée dans h check .
L’algorithme SWEEP_MIN gère les évènements et organise le balayage. Il délègue le filtrage sur un intervalle à l’algorithme FILTER _MIN et la synchronisation des évènements à l’algorithme SYNCHRONIZE.

Analyse de l’algorithme

L’adaptation que nous proposons induit un certain nombre d’évènements dynamiques. À chaque traitement de l’évènement de fin de partie obligatoire, si l’activité a été repoussée, l’évènement est repoussé. Cela ce produit un nombre de fois de l’ordre de k a /p a (cf. annexe A.2). Notons d le plus grand ratio entre la durée de l’activité et sa partie robuste (d = maxa∈A (k a /p a )). Dans le pire cas, l’algorithme doit traiter O(d n) évènements. La complexité de l’algorithme est alors O(d n 2 log n). Dans la plupart des cas, on peut admettre que la partie robuste k a est plus petite que la durée de l’activité. Dans ce cas au plus 1 nouvel évènement est créé, l’algorithme est alors en O(n 2 log n).
Nous avons adapté plusieurs versions différentes de l’algorithme de balayage Time-Table, Dynamic Sweep ([LCB14, section 3]) et Synchronized Sweep ([LCB14, section 4]). Dans le cadre d’une adaptation robuste les deux implémentations ne diffèrent que très légèrement, aussi bien en matière d’adaptation algorithmique, qu’en temps d’exécution. Puisque ces différentes versions n’ajoutent rien à la capacité de modélisation, que nous souhaitons privilégier, nous ne noussommes pas attardés dessus. Cette piste d’amélioration purement algorithmique reste donc ouverte.

Table des matières
1 Introduction 
I État de l’art
2 Notions de base 
2.1 Notions de complexité
2.1.1 La notation de Landau .
Les limites pratiques de la notation de Landau
2.1.2 Les classes de complexité .
Problème de décision
Problème de recherche de solutions
Problème d’optimisation
2.2 La programmation par contraintes
2.2.1 Les réseaux de contraintes
2.2.2 La recherche
2.2.3 La propagation
La cohérence d’arc généralisée
Les cohérences aux bornes
Les cohérences plus faibles que GAC ou BC
3 Ordonnancement et Robustesse 
3.1 L’ordonnancement cumulatif
3.1.1 L’ordonnancement en programmation par contraintes
3.1.2 La contrainte Cumulative
3.1.3 Les filtrages de la contrainte Cumulative
Time-Table
Edge-Finding
Time-Table-Edge-Finding
Le raisonnement énergétique
3.2 La notion de robustesse
3.2.1 La robustesse en programmation par contraintes
3.2.2 La robustesse en ordonnancement
II Contributions
4 Caractérisations des raisonnements pour la contrainte Cumulative 
4.1 Détection d’incohérence
4.1.1 Raisonnement énergétique
4.1.2 Edge-Finding
6 Table des matières
4.1.3 Time-Table
4.1.4 Time-Table-Edge-Finding
4.2 Intervalles d’intérêt pour la détection d’incohérence
4.2.1 Time-Table
4.2.2 Edge-Finding
4.2.3 Time-Table-Edge-Finding
4.2.4 Raisonnement énergétique
Etude de l’intersection minimale
Applications et experimentations
4.3 Relations de dominance des détections d’incohérence
4.4 Extension de la caractérisation aux propagateurs
4.4.1 Raisonnement énergétique
Étude de la fonction de consommation d’énergie
Applications et expérimentations
4.4.2 Time-Table-Edge-Finding
4.5 Conclusions et Perspectives
5 L’ordonnancement robuste 
5.1 Introduction
5.2 FlexC : Une contrainte Cumulative robuste
5.2.1 Description du nouveau paradigme
5.2.2 Détection d’incohérence
5.2.3 Filtrage
5.2.4 Algorithme de filtrage
Adaptation générique
Adaptation pour le filtrage du début au plus tôt
Adaptations pour le filtrage de la fin au plus tard .
5.2.5 Analyse de l’algorithme
5.2.6 Contraintes annexes
5.2.7 Tests expérimentaux
5.3 Application à un problème de déchargement de grues
5.3.1 Description du problème .
5.3.2 Résultats
5.4 Conclusions et Perspectives
6 Conclusion 
A Annexe
A.1 Travaux en Parallèle de la thèse
A.2 Nombre de décalages de EKCPD
A.3 Tableaux Benchs
A.3.1 Approche robuste
A.3.2 Comparaison des propagateurs
Instances Pack en satisfaction 
Instances Pack en optimisation .

Lire le rapport complet