Programmation par contraintes et ordonnancement cumulatif 

Télécharger le fichier pdf d’un mémoire de fin d’études

Ordonnancement et contraintes de ressources

L’ordonnancement

La théorie de l’ordonnancement s’intéresse au calcul de dates d’exécution d’un ensemble d’activités. Dans cette optique, l’utilisation d’une ou plusieurs ressources peut être nécessaire et l’exécution d’une activité implique souvent une telle consommation. Un problème d’ordonnancement peut alors être vu comme l’organisation dans le temps de la réalisation d’activités soumises à des contraintes de temps et de ressource. Dans la plupart des cas, un ou plusieurs objectifs sont définis et une solution au problème d’ordonnancement vise à optimiser ces objectifs.
Les activités
Une activité peut être définie par une date de début sti et une date de fin eti et une durée pi vérifiant eti = sti + pi. Cette date de début (respectivement fin) doit être comprise entre sa date de début (resp. fin) au plus tôt, esti (resp. eeti) et sa date de début (resp. fin) au plus tard, lsti (resp. leti).
Si l’activité utilise une ou plusieurs ressources durant son exécution, il est nécessaire d’ajouter à cette définition une fonction permettant de modéliser l’allocation de chaque ressource k à chaque activité i. Si cette fonction est donnée dans les paramètres du problème, on la note rik(t). Si, au contraire, elle fait partie des variables de décision du problème, on la note bik(t). Enfin, si cette fonction ne dépend pas du temps, i.e. est constante, le paramètre t pourra être omis.
Selon les problèmes, une activité peut être contrainte à s’exécuter en un seul morceau. On parle alors d’activité non préemptive et dans le cas contraire, i.e. les activités peuvent être exécutées en plusieurs morceaux, on parle d’activité préemptive.
Une activité peut être utilisée pour représenter, par exemple, une opération dans un processus de production, le décollage/atterrissage d’un avion ou encore une étape d’un projet de construction.
Les ressources
Une ressource k est un moyen technique ou humain requis pour la réalisation d’une activité et est disponible en quantité limitée. Cette quantité, appelée disponibilité de la ressource ou capacité, peut être soit constante ou varier au cours du temps. Dans ce manuscrit, nous considérons des ressources à capacité constante et cette capacité est notée Rk. Les ressources utilisées par les activités peuvent être de nature diverse. Parmi elles, on peut distinguer :
— les ressources renouvelables : ces ressources peuvent être réutilisées dès lors qu’elles sont libérées. Il s’agit, en fait, de ressources qui, après avoir été utilisées par une ou plusieurs activités, sont de nouveau disponible en même quantité. Ces ressources peuvent, par exemple, représenter la main d’œuvre d’une entreprise, des machines, de l’électricité ou des équipements.
— à l’inverse, les ressources consommables sont des ressources dont la consommation globale est limitée au cours du temps. Il peut s’agir, par exemple, de matières premières ou d’un budget. Parmi les ressources renouvelables, on distingue par ailleurs, les ressources disjonctives qui ne peuvent exécuter qu’une activité à la fois – e.g. pistes de décollage, salles – et les ressources cumulatives qui peuvent, elles, être utilisées par plusieurs activités en parallèle mais sont disponibles en quantité limitée – e.g. main d’œuvre, processeurs.
Du point de vue de leur divisibilité, les ressources peuvent aussi être divisées selon deux catégories :
— les ressources continues, i.e. divisibles en temps ou en quantité continu : dans le premier cas, il s’agit de ressources pouvant être ré-allouées à tout instant t ∈ [0, T ], où T est une borne supérieure sur la date de fin de l’ordonnancement ; dans le second cas, il s’agit de ressources pouvant être allouées en quantité continue, i.e. non discrète. Ce type de ressource permet, par exemple, de modéliser l’électricité, l’essence, l’énergie hydraulique…
— les ressources discrètes, i.e. divisibles en temps ou en quantité discret : à l’inverse, le premier cas décrit une ressource où la ré-allocation de cette dernière ne peut être exécutée qu’à des temps discrets t ∈ {0, . . . , T }. Ce cas correspond généralement au cas où l’horizon de temps a été discrétisé, soit pour faciliter le problème, soit sans perte de génralité. Le second cas correspond aux ressources ne pouvant être attribuées aux activités qu’en quantité discrète, e.g. employés, machines…
Les contraintes
Une contrainte permet d’exprimer des restrictions sur les valeurs que peuvent prendre une ou plusieurs variables du problème. Parmi les principales, on distingue :
— les contraintes de temps : elles intègrent les contraintes de temps alloué, issues généralement d’impératifs de gestion et relatives aux dates limites des activités (e.g. dates de livraison) ou à la durée totale d’un projet mais aussi les contraintes d’enchaînement qui décrivent des positionnements relatifs devant être respectés entre les activités. Ces contraintes peuvent, par exemple, modéliser des contraintes de précédence entre les activités, i.e. une activité ne peut commencer avant qu’une autre n’ait été achevée, ou des temps de transition à respecter entre les activités.
Étant donné une activité i, la date à partir de laquelle l’activité i peut être exécutée est appelée date de début au plus tôt et est notée esti (earliest start time en anglais). De même, la date avant laquelle l’activité i doit avoir été complètement exécutée sera appelée date de fin au plus tard et notée leti (latest end time en anglais).
— les contraintes de ressources : ce sont des contraintes d’utilisation des ressources qui expriment la nature et la quantité de moyens utilisés par les activités, ainsi que les caractéristiques d’utili-sation de ces moyens. Ces contraintes peuvent aussi représenter des contraintes de disponibilité des ressources qui précisent la nature et la quantité de moyens disponibles au cours du temps.
Les objectifs
Lors de la résolution d’un problème d’ordonnancement, deux buts différents peuvent être poursui-vis. Le premier vise à trouver une solution réalisable pour le problème tandis que le second cherche à trouver une solution réalisable optimisant un ou plusieurs critères ou objectifs.
Ces objectifs peuvent être liés à différents aspects de la solution. On distingue par exemple :
— les objectifs liés au temps : le temps total d’exécution ou le temps moyen d’achèvement d’un en-semble d’activités peuvent être minimisés, mais aussi les retards (maximum, moyen, somme…) par rapport aux dates de fin au plus tard fixées par le problème.
— les objectifs liés aux ressources : la quantité (maximale, moyenne, pondérée…) de ressources nécessaires pour réaliser un ensemble d’activités peut, par exemple, être minimisée.
— les objectifs liés aux coûts de lancement, de production, de transport, de stockage ou liés aux revenus, aux retours d’investissements…
— les objectifs liés à une énergie, un débit…
Deux exemples de problèmes d’ordonnancement sont présentés dans la sous-section suivante : le RCPSP et le CuSP.

Contraintes de ressources

Dans ce manuscrit, nous nous intéressons principalement aux problèmes d’ordonnancement cu-mulatif. Parmi ces derniers, deux des plus étudiés sont le problème d’ordonnancement de projet à contraintes de ressource (RCPSP) et le problème cumulatif (CuSP). Nous allons donc commencer par présenter ces deux problèmes. En effet, beaucoup des travaux décrits dans ce manuscrit s’appuient sur des résultats mis en évidence pour eux.
Dans un second temps, nous montrerons les limites de ces modélisations pour exprimer certains problèmes cumulatifs réels et les modèles alternatifs mis en place dans la littérature pour pallier ces limitations.
Le problème d’ordonnancement de projet à contraintes de ressources (RCPSP) est un problème d’ordonnancement très général, utilisé pour modéliser certains problèmes pratiques. Le but est d’or-donnancer un ensemble d’activités de telle sorte que les capacités des ressources ne soient pas excédées et qu’un certain critière, ou fonction objectif, soit minimisé. Parmi les ressources modélisées, on trouve des ressources telles que des machines, des personnes, des salles, de l’argent ou encore de l’énergie. Pour les fonctions objectif, des quantités telles que la durée totale du projet, le retard ou les coûts peuvent être minimisées.
Formellement, le RCPSP est défini de la manière suivante : nous considérons un ensemble d’activités non préemptives A = {1, . . . , n} à ordonnancer et un ensemble R = {1, . . . , m} de ressources discrètes, cumulatives et renouvelables. Chacune de ces ressources k ∈ R est disponible tout au long du projet en quantité Rk et, durant son exécution, une activité consomme une quantité constante rik (pouvant être nulle) de cette ressource. Dans ce problème, une activité i ∈ A a une durée fixe pi et des relations de précédence lient les activités entre elles. Ces relations sont modélisées à l’aide d’un graphe G = (V, E), appelé graphe de précédence, dans lequel l’ensemble des arcs (i, j) ∈ E représente les relations de précédence, i.e. (i, j) ∈ E ⇔ i doit être ordonnancée avant j dans toute solution. Dans ce graphe, l’ensemble des sommets, noté V = {0, . . . , n+1}, correspond aux n activités auxquelles on ajoute deux activités fictives 0 et n + 1 qui représentent respectivement le début et la fin du projet. Ces activités fictives ne consomment pas de ressource et ont une durée d’exécution nulle. De plus, E contient les arcs suivants :
— (0, i), ∀i ∈ A,
— (i, n + 1), ∀i ∈ A.
Pour ce problème, la fonction objectif la plus rencontrée dans la littérature étant la minimisation de la date de fin du projet, i.e. Cmax, nous considérons principalement cet objectif dans la suite de ce manuscrit. Si un objectif différent est considéré, nous le précisons.
Le RCPSP a été prouvé NP-complet au sens fort [BLK83]. Ce problème a donc été très étudié dans la littérature, notamment pour trouver des méthodes efficaces pour sa résolution. Dans la section 4.2, nous présentons des modèles de programmation linéaire permettant de trouver une solution optimale à ce problème. Ces modèles seront alors adaptés dans le cadre d’un autre problème d’ordonnancement décrit dans le paragraphe 1.2.
Le problème cumulatif
Le problème d’ordonnancement cumulatif (CuSP) permet de caractériser le fait que le projet implique une ressource (ou un sous-ensemble de ressources) de nature cumulative. Le CuSP peut
être vu comme un cas particulier de la variante décisionnelle du RCPSP où l’on ne considère qu’une ressource et où l’on remplace les contraintes de précédence par les fenêtres de temps qu’elles induisent.
Formellement, le CuSP prend en entrée un ensemble A = {1, . . . , n} d’activités non préemptives à ordonnancer. Pour s’exécuter, une activité doit consommer une partie de la ressource ri et ce jusqu’à l’arrêt de l’activité, i.e. après un temps pi correspondant à la durée de l’activité i. Cette ressource est de type cumulatif, discrète et renouvelable, disponible en quantité R.
De plus, chaque activité dispose d’une fenêtre de temps [esti, leti] dans laquelle l’activité doit obligatoirement s’exécuter. Nous rappelons que esti correspond à la date de début au plus tôt de i et leti à sa date de fin au plus tard.

Limites des problèmes cumulatifs en termes de modélisation

Une des principales limitations du RCPSP et donc du CuSP (qui en est un cas particulier) en termes de modélisation est que, dans ces problèmes, chaque activité consomme une quantité de ressource fixe, connue à l’avance, durant toute sa durée d’exécution. De plus, cette durée est aussi supposée fixe. Cependant, pour de nombreux problèmes pratiques, ces suppositions reviennent à sur-contraindre le problème. En effet, considérons l’exemple suivant, décrit dans [FT10] pour lequel une activité représentant la peinture d’un bateau est considérée. Pour cette activité, la durée est remplacée par une quantité de travail, ou énergie, représentant le travail de 3 personnes sur une journée. Cette activité peut, au choix, être exécutée en 3 jours par 1 personne, ou en 2 jours par 2 personnes le premier jour et 1 personne le second, ou encore par 3 personnes en seulement un jour. Si l’on avait supposé une consommation et une durée fixe, l’espace des solutions aurait été réduit.
L’exemple décrit ci-dessus peut facilement être généralisé à de nombreux cas pratiques. Un autre exemple venant d’un problème industriel est présenté dans [ALH13]. Dans cet article, une application dans une fonderie où du métal est fondu dans des fours à induction est détaillé. La puissance de chaque four utilisée pour faire fondre le métal peut être réglée, à tout moment, afin d’éviter un dépassement d’un certain niveau de ressource (généralement dû à une limite suggérée par le fournisseur). De ce fait, si chaque opération de fonte est vue comme une activité, nous avons besoin de pouvoir moduler la quantité de ressource donnée à cette activité à chaque instant et la durée de l’activité dépend de cette quantité de ressource.
Pour représenter ces variations dans le profil de consommation des activités, nous avons choisi de modéliser la ressource comme une ressource continue. En effet, de nombreux exemples de ressource continue existent. C’est le cas de l’électricité, des sources d’énergie hydrauliques, du carburant ou encore de la mémoire d’un ordinateur. D’autres ressources telles que des employés ou des machines, qui sont normalement modélisées à l’aide de ressources discrètes, peuvent être modélisées par des ressources continues si l’on suppose qu’un employé ou une machine peut exécuter plusieurs activités en parallèle [Weg80, NK14].
De plus, les problèmes à ressources continues peuvent aussi servir de relaxation pour les problèmes avec des ressources discrètes. En effet, le caractère discret du problème peut parfois amener à consi-dérer de nombreuses possibilités d’affectations de la ressource. Dans certains cas, ce grand nombre d’affectation peut grandement complexifier le problème. Donc, considérer des ressources continues peut permettre l’agrégation des raisonnements dédiés à ces problèmes.
Une autre particularité du problème de la fonderie décrit dans [ALH13] vient du fait que la quantité de ressource allouée à un four doit être comprise dans un certain intervalle pendant toute la durée d’exécution de l’activité. En effet, pour des raisons opérationnelles et/ou physiques, la puissance des fours permettant la fonte du métal ne peut être ni trop élevée, ni trop basse et, de ce fait, ne peut ni dépasser un certain seuil dit maximum, ni descendre en dessous d’un seuil minimum.
Enfin, la quantité d’énergie fournie peut ne pas être proportionnelle à la quantité de ressource consommée. Le problème considéré dans cette thèse et décrit dans la section suivante permet de modéliser ces contraintes particulières. Cette modélisation sera ensuite comparée aux extensions du CuSP et du RCPSP, déjà existantes dans la littérature.

L’ordonnancement sous contraintes énergétiques

La modélisation présentée dans cette section repose sur le problème d’ordonnancement continu à contraintes énergétiques [AL15], le CECSP.

Définition du problème

Dans ce problème, un ensemble d’activités non préemptives A = {1, . . . , n} utilisant une ressource continue, cumulative et renouvelable, de capacité R doit être ordonnancé. Durant son exécution, une activité consomme une quantité variable bi(t) de la ressource qui doit être comprise entre une valeur minimale, rimin ∈ [0, R], et une valeur maximale, rimax ∈ [rimin, R]. De plus, la fin d’une activité corres-pond au moment où cette dernière a reçu une certaine quantité d’énergie Wi. Cette énergie est reçue via la ressource et calculée à l’aide d’une fonction fi : {0} ∪ [rimin, rimax] −→ {0} ∪ [f(rimin), f(rimax)] (fi(0) = 0 est imposé). Ces fonctions, appelées fonctions de rendement, font partie de la donnée du problème et sont supposées continues et strictement croissantes. La quantité d’énergie reçue par i à l’instant t est donc R0t fi(bi(s))ds. La dernière contrainte du problème précise que chaque activité doit être exécutée dans sa fenêtre de temps [esti, leti].
C’est par exemple le cas quand bi(t) ou sti et eti sont contraints à prendre des valeurs entières. Dans ce manuscrit, nous considérons les cas où les fonctions fi sont continues, croissantes et :
— égales à la fonction identité, ∀i ∈ A,
— affines, ∀i ∈ A,
— concaves et affines par morceaux, ∀i ∈ A.
L’intérêt de considérer de telles fonctions de rendement est double. Premièrement, un certain nombre de fonctions de rendement réelles ont une forme concave [MHM05, Lew08] due au fait, qu’à partir d’un certain seuil, il n’est plus aussi “rentable” d’allouer plus de ressource à une activité. Deuxièmement, les fonctions affines et concaves affines par morceaux nous permettent d’approcher un grand nombre de fonctions de rendement réelles non linéaires. Un exemple présentant de telles approximations sera présenté (cf. exemple 1.2.1).
Soit Pi le nombre d’intervalles de définition de la fonction fi, i.e. le nombre d’intervalles où la fonction fi a une expression différente, et Pi = {1, . . . , Pi} l’ensemble des indices de ces intervalles. Les points de cassures de la fonctions fi sont notés xi`, ∀` ∈ Pi.

Autres modélisations des activités à profil variable

Dans un premier temps, nous nous intéressons aux extensions du RCPSP. Une des extensions les plus célèbres est le problème d’ordonnancement de projet multimode (MRCPSP). Dans ce problème, un choix de différents modes est disponible pour chaque activité et une activité doit être exécutée selon un de ces modes. Un mode correspond à une combinaison formée d’un temps d’exécution constant et d’une consommation de ressource qui permet d’apporter à l’activité au moins la quantité d’énergie requise. Même si de nombreux problèmes basés sur ce concept de mode existent [DRDH98, RK07, RRK09, DDrH00] et que des méthodes de résolution efficaces ont été mises en place pour résoudre le MRCPSP [PV10], cette modélisation peut amener à une mauvaise allocation de la ressource.
Si nous reprenons l’exemple de la peinture d’un bateau, décrit à la sous-section 1.1.2, l’activité avait besoin de 3 unités d’énergie pour s’exécuter. Dans le contexte du MRCPSP, seulement 3 modes seraient décrits : (3, 1), (2, 2) et (1, 3). Or, dans le second cas, on donne une unité de trop à l’activité et la possibilité d’allouer 2 unités de ressource pendant une période de temps et 1 unité pendant la seconde n’est pas représentée ici.
La principale limitation du MRCPSP est donc que les activités sont contraintes à être rectangu-laires, i.e. avec une consommation de ressource constante.
D’autres extensions du RCPSP existent. C’est le cas par exemple des problèmes d’ordonnancement de projet avec une ressource de type work-content [FT10] ou du problème d’ordonnancement de projet avec des profils de ressource flexibles (FRCPSP) [NK14]. Dans ces problèmes, plusieurs types de ressources sont considérées :
— principale (ou work-content dans [FT10]) : il s’agit de la ressource via laquelle la quantité d’énergie requise est donnée à l’activité. C’est elle qui sert à déterminer la durée de l’activité.
— les ressources dépendantes : l’utilisation de ces ressources dépendent de l’utilisation de la res-source principale.
— les ressources indépendantes : la consommation de ces ressources est indépendante des consommations des autres ressources mais ces utilisations doivent être synchrones.
Bien que plusieurs différences existent entre ces problèmes et le CECSP– l’utilisation de plusieurs ressources, ressource/temps discret pour [FT10]… – les principales sont les suivantes : la longueur minimale des blocs et les fonctions de rendement. La première correspond au temps minimal qu’il faut attendre entre deux ré-allocations de la ressource, que les auteurs de [FT10] appellent longueur minimale de bloc et qui est absente dans notre problème. La seconde fait référence à l’absence de fonctions de rendement dans [FT10].
Enfin, la dernière extension du RCPSP présentée est celle où les activités ont une intensité va-riable [Kis05]. Ici, chaque activité requiert une certaine quantité d’énergie durant toute son exécution. Pour apporter cette énergie à l’activité, il faut décider, dans chaque période de temps, l’intensité à laquelle est exécutée l’activité. L’énergie apportée à l’activité est alors proportionnelle à cette inten-sité. Dans ce cas, on peut introduire des fonctions de rendement mais ces fonctions seraient alors contraintes à être linéaires, i.e. b → a ∗ b. De plus, aucune borne inférieure sur la consommation d’une activité n’est considérée.
Dans le cadre du CuSP, d’autre variantes ainsi que des algorithmes de filtrages dédiés ont été proposés. Parmi ceux-ci, on retrouve le cas des activités complètement/partiellement élastiques de Baptiste et al. [BLPN99]. Dans le premier cas, les activités ont une demande en énergie constante mais la quantité de ressource consommée par une activité à chaque instant (discret) peut varier entre 0 et la capacité de la ressource. Dans le second cas, les mêmes conditions sont présentes mais les auteurs définissent des contraintes permettant de limiter les variations dans l’utilisation de la ressource. Aucun de ces deux problèmes ne considère de fonctions de rendement.
Dans [BP07], les auteurs définissent une activité comme une séquence de sous-activités trapézoï-dales ayant des durées et hauteurs (consommations) variables. Enfin, Vilím [Vil09b] considère des activités pour lesquelles la durée et la hauteur sont définies par des intervalles. Pour ces deux pro-blèmes, aucune demande en énergie n’est définie pour les activités. De plus, dans le second, l’énergie manquante peut être achetée moyennant un certain coût.
Enfin, le CECSP est aussi lié à d’autres problèmes à contraintes d’énergie avec ressources conti-nues [BEP+01, Wal11]. Dans [BEP+01], plusieurs modèles représentant le temps d’exécution d’une activité en fonction de la ressource qui lui est allouée sont présentés. En particulier, les auteurs consi-dèrent un problème où un ensemble de processeurs identiques et parallèles jouent le rôle de la ressource. De plus, des fonctions représentant le temps d’exécution d’une activité en fonction du nombre de pro-cesseurs qui lui est allouée sont définies. Ce nombre de processeurs peut varier continuellement au cours du temps et donc ces fonctions sont équivalentes aux fonctions de rendement définies dans le cadre du CECSP. De plus, dans [BEP+01, Wal11], l’énergie est calculée en intégrant une fonction de rendement sur tout l’horizon de temps. Cependant, aucune contrainte de consommation maximum et minimum n’est considérée dans ces problèmes. Dans [Wal11], une partie des ressources est continue et une partie est discrète.
Le CECSP est donc un nouveau problème et les différences avec les problèmes existants ne nous permettent pas d’appliquer directement des techniques déjà définies pour d’autres problèmes. Cepen-dant, certaines techniques existantes peuvent être adaptées dans le cadre du CECSP. Ces techniques seront présentées plus tard dans le manuscrit.
La section suivante présente des propriétés du CECSP qui seront utilisées dans le cadre de sa résolution.

Propriétés du CECSP

Dans cette section, nous allons commencer par présenter la preuve de NP-complétude du CECSP. Ce problème pouvant être vu comme une généralisation du CuSP, nous utilisons ce problème pour montrer la difficulté du CECSP.
Théorème 1.1 ([NAL15b]). Le CECSP est NP-complet.
Démonstration. Nous réduisons donc le CuSP vers le CECSP. Soit Π une instance du CuSP. Nous réduisons Π en une instance du CECSP, Π0, de la manière suivante, ∀i ∈ A :
— rimin = rimax = ri
— fi(b) = b
— Wi = piri
— R, esti and leti restent inchangés.
On peut facilement vérifier que Π est une instance positive du CuSP si et seulement si Π0 est une instance positive du CECSP. Le CECSP est donc NP-complet.
Le problème de décision associé au CECSP est donc NP-complet. Dans ce manuscrit, nous avons donc considérer ce problème sans fonction objectif mais aussi avec la fonction objectif suivante :
Z eti X minimiser bi(t)dt i A sti
Cette fonction consiste en la minimisation de la consommation totale de ressource. L’intérêt de cette fonction objectif dans le cas où les fonctions de rendement sont égales à la fonction identité est discuté dans le chapitre 5. Dans le cas où les fonctions de rendement sont affines ou concaves et affines par morceaux, cet objectif est pertinent puisque, même si la quantité d’énergie apportée à une activité est fixée, la quantité de ressource que l’activité doit consommer ne l’est pas et plusieurs profil de consommation peuvent conduire à la même quantité d’énergie apportée. Trouver le profil qui consomme le moins de ressource possible tout en apportant l’énergie requise est donc un vrai problème. Dans la suite, si rien n’est précisé, cela veut dire que nous considérons le CECSP sans fonction objectif.
Nous présentons un exemple d’instance ne comprenant que des données entières et ne possédant que des solutions non entières. Ceci permet de justifier l’utilisation de modèles à temps continu.

Table des matières

I Présentation du problème 
1 Ordonnancement, ressources cumulatives et énergie 
1.1 Ordonnancement et contraintes de ressources
1.1.1 L’ordonnancement
1.1.2 Contraintes de ressources
1.2 L’ordonnancement sous contraintes énergétiques
1.2.1 Définition du problème
1.2.2 Autres modélisations des activités à profil variable
1.2.3 Propriétés du CECSP
II Programmation par contraintes 
2 Programmation par contraintes et ordonnancement cumulatif 
2.1 La programmation par contraintes
2.1.1 Problème de satisfaction de contraintes
2.1.2 Exploration de l’espace de recherche
2.1.3 Détection d’incohérence et Filtrage
2.2 L’ordonnancement cumulatif
2.2.1 L’ordonnancement en programmation par contraintes
2.2.2 La contrainte cumulative
2.2.3 Les filtrages de la contrainte cumulative
3 Propagation de contraintes pour le CECSP 67
3.1 Algorithmes de filtrage basés sur le Time-Table
3.1.1 Le Time-Table
3.1.2 Le Time-Table disjonctif
3.1.3 Le Time-Table basé sur les flots
3.2 Algorithme de filtrage du raisonnement énergétique
3.2.1 Algorithme de vérification
3.2.2 Les ajustements de bornes
3.2.3 Caractérisation des intervalles d’intérêt
III Programmation linéaire en nombres entiers 
4 Programmation linéaire et ordonnancement de projet 
4.1 La programmation linéaire en nombres entiers
4.1.1 La programmation linéaire
4.1.2 Contrainte d’intégrité
4.1.3 Techniques de résolution
4.2 Application au RCPSP
4.2.1 Modèles indexés par le temps
4.2.2 Modèles à événements
5 Programmation linéaire pour le CECSP et renforcement des modèles
5.1 Modèles de programmation linéaire mixte pour le CECSP
5.1.1 Modèle indexé par le temps
5.1.2 Modèles à événements
5.2 Renforcement des modèles
5.2.1 Amélioration des modèles indexés par le temps
5.2.2 Amélioration des modèles à événements
IV Implémentations et Expérimentations 
6 Implémentations et Expérimentations 
6.1 Génération des instances et pré-traitement
6.1.1 Instances du CECSP
6.1.2 Instances et pré-calcul des fenêtres de temps pour le RCPSP
6.2 Performances de la Programmation Linéaire Mixte
6.2.1 Modèle indexé par le temps
6.2.2 Modèles à événements
6.2.3 Comparaison des différentes approches
6.3 Performances de la Programmation Par Contraintes
6.3.1 Cadre des expérimentations
6.3.2 Raisonnement énergétique
6.3.3 Raisonnements basés sur le Time-Table
6.3.4 Comparaison des différentes approches
A Programmation linéaire mixte et programmation par contraintes pour un problème d’ordonnancement à contraintes énergétiques
A.1 Introduction
A.2 Modèle de programmation par contraintes
A.2.1 Raisonnement énergétique
A.3 Modèle de programmation linéaire en nombres entiers
A.3.1 Modèle
A.4 Inégalités valides basées sur le raisonnement énergétique
A.5 Résultats expérimentaux
B A batch sizing and scheduling problem on parallel machines with different speeds, maintenance operations, setup times and energy costs
B.1 Introduction
B.2 The industrial scheduling problem
B.3 Related work and modeling issues
B.4 A continuous time event-based mixed-integer linear programming formulation
B.5 A simplified model and a matheuristic
B.6 Computational experiments
B.7 Conclusion

Télécharger le rapport complet