Master MIAGE - Projet d'Optimisation combinatoire - Claire Hanen
Problème à résoudre
On s'intéresse à la résolution du problème d'ordonnancement suivant :
On se donne n tâches caractérisées par des durées pi, des dates d'échéance di et des profits wi.
Ces tâches doivent être ordonnancées sur une seule machine.
Le profit d'un ordonnancement est la somme des profits des tâches qui se terminent avant ou à leur date d'échéance.
Analyse a priori
Proposez les éléments d'une méthode arborescente pour ce problème.
Vous pourrez utiliser les propriétés qui ont permis de définir le schéma de programmation dynamique vu en cours pour ce même problème.
Vous pourrez également vous inspirer des méthodes arborescentes présentées dans le document de cours.
Vous préciserez dans le document d'analyse vos choix en matière de :
- Définition des sous-ensembles de solutions associés aux noeuds.
- Définition de l'opérateur de séparation
- Définition de la fonction d'évaluation par excès.
- Définition d'un algorithme permettant d'obtenir en chaque noeud une solution particulière et donc une évaluation par défaut.
Il y a plusieurs solutions possibles.
Vous pouvez faire plusieurs propositions, en tâchant de d'évaluer a-priori l'intérêt de chacune.
Implémentation
Implémentez votre méthode arborescente.
Vous travaillerez à 2 groupes (ou plus) pour constituer un fichier commun de jeux d'essai (données particulières de problèmes).
Vous pouvez si vous le souhaitez utiliser une génération aléatoire de données.
Il faudra des problèmes de taille différentes, quelques-un de l'ordre d'une
dizaine, d'une trentaine et d'une cinquantaine de tâches. Une quinzaine de problème (5 de chaque sorte) est un minimum.
Les groupes expérimenteront différents paramètres sur leur méthode,
en matière de règle de parcours (profondeur, largeur, meilleur),
ou de fonctions d'évaluation, ou encore de séparation.
Vous devez vous répartir le travail de manière équitable
(et le groupe de 4 en fournira un peu plus que les autres,
par exemple en implémentant également la méthode de programmation dynamique).
Pour chacun des jeux d'essai et des paramètres choisis, vous évaluerez (et comparerez)
le nombre de noeuds développés par la méthode, et le temps de calcul, si vous pouvez.
Dossier d'analyse
Le dossier d'analyse (un par groupe) comprendra une explication succinte
du choix des structures de données et d'algorithmique pour l'implémentation de la méthode,
ainsi qu'une étude comparative des résultats des différents tests menés par au moins deux groupes.
Il précisera également le rôle de chacun dans l'élaboration du projet.
L'objectif est de répondre à cette question : votre méthode est-elle efficace/inefficace ? Et à votre avis pourquoi ?