Méthodes de résolution pour la caractérisation des solutions optimales du problème 1||Lmax

EasyChair Preprint 2618

Abstract

Beaucoup de problèmes d’ordonnancement peuvent être résolus en temps polynomial grâce à une règle de priorité. Cependant, ces problèmes peuvent admettre un grand nombre – possiblement exponentiel – de solutions optimales. L’objectif de notre étude est de caractériser l’ensemble des solutions optimales pour le problème 1||L_max, sans les énumérer. Une telle approche se révèle intéressante dans le cadre de l’ordonnancement multicritère, ou dans un contexte dynamique pour assurer une certaine forme de robustesse.  Dans ce papier, nous nous intéressons au problème qui consiste à chercher une solution faisable de plus bas niveau dans un treillis de permutations. Cette séquence permet à elle seule de caractériser un très grand nombre de séquences réalisables.

Keyphrases: Ordonnancement, caractérisation de solutions, treillis de permutations

@booklet{EasyChair:2618,
  author    = {Tifenn Rault and Ronan Bocquillon and Jean-Charles Billaut},
  title     = {Resolution methods for characterizing optimal solutions for the 1||Lmax},
  howpublished = {EasyChair Preprint 2618},
  year      = {EasyChair, 2020}}