A la recherche de la politique optimale

Contexte

On considère un problème d'ordonnancement dynamique qui est de la famille des problèmes d'empaquetage (bin packing). Il se formule de la façon suivante.

Une suite d'objets arrivent au cours du temps, de façon aléatoire. Chaque objet a une certaine taille, aléatoire également. À chaque objet O correspond aussi une date limite de validité. Il s'agit de placer les objets dans des boites à raison d'une boite chaque unité de temps. Il y a des contraintes: la taille totale des objets ne peut pas dépasser celle de la boite. Il ne peut pas y avoir plus de deux objets par boite. Et les objets doivent être placés avant leur date limite respective. Si un objet n'a pas pu être placé à temps, il est perdu.

Comment faire pour que le moins d'objets possible soient perdus?

Objectifs

L'objectif de ce TER est donc d'étudier des stratégies pour résoudre ce problème. La solution optimale n'est pas connue; il s'agit plutôt de concevoir et d'étudier des heuristiques prometteuses.

Un travail préliminaire a été effectué, qui a abouti à la réalisation d'un simulateur, écrit en Java. D'autre part, une analyse mathématique du problème a été commencée: elle conduit à formuler la solution du problème comme un programme linéaire. Les objectifs généraux du projet sont:

• l'amélioration du simulateur existant: ajout d'une interface utilisateur, ajout de nouvelles fonctionalités.
• l'interfaçage du simulateur avec un programme de résolution de programmes linéaires.
• la définition, l'implémentation et l'étude de nouvelles stratégies.

Déroulement

Parmi les étapes du projet, on peut prévoir:

• analyse et compréhension du problème d'ordonnancement;
• prise en main du simulateur, analyse des besoins, extension;
• prise en main du programme de résolution des programmes linéaires, interfaçage avec le simulateur;
• réalisation d'expériences de simulation et comparaison des heuristiques.

Le groupe devra comporter 3 ou 4 étudiants.