Sujet de stage de recherche - Master informatique

  • titre: rectangles, graphes d'intervalles et ordonnancement
  • Responsable: Arnaud Pêcher (professeur)
  • Téléphone : 05 40 00 60 78
  • e-mail: pecher@labri.fr
  • Équipe: Combinatoire et Algorithmique
  • Thème : Graphes et applications
  • Equipe INRIA: RealOpt

Présentation du sujet :

Le problème consistant à sélectionner un ensemble d'objets rectangulaires qui peuvent être placés sans chevauchement dans un conteneur rectangulaire, de manière à minimiser l'espace inoccupé est un problème classique en recherche opérationnelle. La figure ci-dessous est une illustration de ce problème: les objets 1,2,3,4,5 et 6 admettent un tel placement, cependant l'objet 7 ne peut être mis avec eux.

La modélisation par des graphes par Feketete et Shepers (1997) de ce problème a permis de faire un saut quantitatif quant à la taille des problèmes traités. En effet, en représentant les solutions par des graphes, de nombreuses symmétries (i.e. des solutions identiques) sont éliminées et les bonnes propriétés algorithmiques des graphes mis en jeu, des graphes d'intervalle, sont la clef pour la conception de l'algorithme de Fekete/Shepers.

Cette modélisation est illustrée dans la figure ci-dessous, 5 boites sont placées dans le grand carré. A ce placement est associé deux graphes d'intervalle: G1 (en haut) et G2 (en bas). Les sommets de G1 (resp. G2) correspondent aux boites; deux sommets sont adjacents si et seulement si la projection des deux boites sur l'axe vertical (resp. horizontal) s'intersecte.

Nous avons développé deux nouveaux algorithmes qui exploitent cette modélisation.

Le travail demandé consiste à étudier des évolutions de ces deux algorithmes de manière à pouvoir traiter de nouveaux problèmes:

  • en considérant que l'axe des abcisses correspond à l'axe temporel et celui des ordonnées correspond aux ressources mobilisées, il suffit de rajouter des contraintes de précédence pour modéliser des problèmes d'ordonnancement; il s'agit donc d'introduire ces contraintes de précédence dans les algorithmes et d'évaluer les performances obtenues sur les jeux de tests standards des problèmes d'ordonnancement
  • en identifiant les bords du conteneur deux-à-deux, les problèmes deviennent périodiques; cela nécessite de revoir en profondeur les algorithmes pour prendre en compte cette périodicité.

Bibliographie et urls :

  1. S.P. Fekete, J.Schepers, J.van der Veen. An exact algorithm for higher-dimensional orthogonal packing Operations Research, Vol. 55, No. 3, 2007, pp. 569-587.
  2. logiciel AlgoKP: https://wiki.bordeaux.inria.fr/realopt/pmwiki.php/Project/SoftwareAlgoKP