Minimisation de la date d'achèvement et du nombre de travaux en retard pour l'ordonnancement multiagent

Session : SS13-3 / SS13 : Méthodes d'optimisation pour l'ordonnancement et la planification
Vendredi 12 février 15:00 - 15:40 Salle : CI2-05
Van Ut Tran, Faiza Sadi et Ameur Soukhal

Dans cette étude, nous proposons des algorithmes polynomiaux pour la résolution des problèmes d'ordonnancement multiagent sur une seule machine. Les critères des agents sont la minimisation du makespan et le nombre de travaux en retard. Des programmes dynamiques pseudo-polynomiaux sont aussi développés pour la résolution de ces problèmes dans le cas de machines parallèles identiques. Dans cette étude, le calcul de la solution optimale au sens de Pareto est basée sur l'approche epsilon-contrainte.

Mots clés : Recherche Opérationnelle, Ordonnancement, Travaux Interférants, Complexité, Algorithmes gloutons, Programmes dynamiques.