Borne inférieure pour le bin stretching online et jeux

Session : SS13-1 / SS13 : Méthodes d'optimisation pour l'ordonnancement et la planification
Jeudi 11 février 15:00 - 16:40 Salle : CI2-05
Michaël Gabay, Vladimir Kotov et Nadia Brauner

On considère le problème d’ordonnancement semi-online suivant : les tâches arrivent consécutivement et doivent être ordonnancées immédiatement et on connaît la valeur de l'ordonnancement optimal. On veut minimiser la dégradation de la durée totale de production. On peut le voir comme un problème de packing: on a des objets dont on sait qu’ils peuvent être placés dans k bins de taille 1 et on veut les affecter, en-ligne dans k bins de taille C. L’objectif est de minimiser C. On montre qu’aucun algorithme ne peut garantir de performance inférieure à 19/14 (env. 1.357). Jusqu’à présent, la seule borne inférieure connue pour ce problème était le classique 4/3. Une des raisons qui expliquent cette absence de meilleure borne est le fait qu’on ne puisse pas appliquer ici les méthodes classiques par cas à cause de la connaissance initiale supplémentaire. On obtient la borne de manière informatique et elle est vérifiable sur un graphe obtenu en sortie. On utilise des techniques de théorie des jeux pour calculer automatiquement la borne inférieure.

Mots clés : Bin stretching, algorithme online, borne inférieure