|
|
 |
|
Jeudi 15 Avril
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Formulations PLNE pour un problème d'ordonnancement juste-à-temps |
| Description: |
Anne-Elisabeth FALQ Une contrainte essentielle pour un problème d'ordonnancement sur une machine est le non-chevauchement des tâches: deux tâches ne peuvent être exécutées en même temps.
Les premières inégalités de non-chevauchement ont été proposées par Queyranne (1993) pour le problème de minimisation de la somme pondérée des dates de fins. La famille d'inégalités linéaires proposée décrit exactement l'enveloppe convexe des vecteurs encodant des ordonnancements réalisables par les dates de fins des tâches. Ces inégalités ne coupent pas tous les vecteurs encodant un ordonnancement avec chevauchement mais assurent le non-chevauchement au sens où tous les points extrêmes du polyèdre qu'elles définissent encodent des ordonnancements réalisables, et plus précisément ceux calés à gauche qui forment un ensemble dominant pour ce problème.
Dans cet exposé, nous nous intéresseront particulièrement au problème d'ordonnancement juste-à-temps où toutes les tâches partagent une même date d'échéance commune et où il s'agit de minimiser la somme pondérée des avances et des retards par rapport à cette date.
En s'appuyant sur les propriétés de dominance connues pour ce problème NP-difficile (Hall et Posner, 1991), nous proposerons une formulation basée sur des inégalités de non-chevauchement nouvelles. Cette formulation, qui n'est pas exactement un programme linéaire en nombre entiers (PLNE) puisqu'elle fait apparaître des contraintes d'extremalité, peut être résolue par un solveur de PL implémentant un algorithme de "Branch-and-Cut". Nous expliquerons comment et présenterons quelques résultats expérimentaux.
Dans un second temps, nous proposerons une formulation compacte pour ce problème, que nous renforçons par des inégalités dites de dominance. Ces inégalités sont ainsi nommées car elles traduisent la dominance des solutions localement optimales, où local s'entend pour un voisinage généré par une famille d'opérations sur les solutions. Pour chaque opération considérée, une inégalité élimine les solutions qu'on pourrait améliorer en appliquant la transformation. De ce fait, ces inégalités coupent des point entiers, et diffèrent en cela des inégalités classiques de renforcement. Grâce à des résultats expérimentaux, nous montrerons le gain defficacité qu'apporte ces inégalités de dominance. |
|
|
