Chérif Sadfi
Laboratoire GILCO - ENSGI - INPG
Résumé : Nous proposons une étude du problème d'ordonnancement sur une machine avec période d'indisponibilité de la machine. L'objectif est la minimisation de la somme des dates d'achèvement des travaux.
Dans la première partie, nous proposons une heuristique avec une garantie de performance de 20/17 qui améliore la meilleure borne trouvée dans la littérature (9/7) développée par Lee et Liman 1992.
Dans la deuxième partie, nous proposons une résolution du problème par programmation dynamique. Pour cela, un algorithme de programmation dynamique conduisant à une solution optimale du problème est présenté. La complexité de cet algorithme est O(nR), où n représente le nombre de travaux et R la date de la période d'indisponibilité. Ensuite, nous proposons une amélioration de la complexité de cet algorithme par une méthode de "fixation de variables". Enfin, une analyse théorique et expérimentale est présentée pour chacune des méthodes proposées afin de juger sa performance.
Mots clés : Ordonnancement sur une machine, minimisation du flot total, indisponibilité des machines, heuristique, garantie de performance, programmation dynamique, fixation de variables.