Le 18/03/2011 par S_Ameur :

Titre :
"Complexité et algorithmes d'approximation pour les problèmes d'ordonnancement travaux interférants avec une fonction objectif globale"

Encadrant :
Ameur SOUKHAL & J-C BILLAUT

Contact :
ameur.soukhal@univ-tours.fr
jean-charles.billaut@univ-tours.fr
tel : 02 47 36 14 27 (A. Soukhal)

Laboratoire d'accueil :
Laboratoire d'Informatique (EA 2101) / Université François Rabelais de Tours (http://www.li.univ-tours.fr/)

Type de financement envisagé :
Bourse ministérielle

Dates de candidatures :
Les dossiers de candidatures sont à envoyer à ameur.soukhal@univ-tours.fr pour au plus tard le 25/04/2011.
Le candidat doit avoir (ou encours de finalisation) le diplôme/grade de Master/Ingénieur en informatique, recherche opérationnelle ou mathématiques appliquées.
Les candidatures (CV, lettre de motivation, notes, résultats et classement, éventuellement le sujet de master et coordonnées de l'encadrant)


Descriptif du sujet :
Motivée et stimulée par des questions qui se posent dans la planification et la gestion de la production, la théorie de l'ordonnancement est devenue un domaine important d'optimisation combinatoire, situé à l'interface entre les mathématiques appliquées, l'informatique et la recherche opérationnelle. Dans son sens le plus large, l'ordonnancement consiste à programmer l'exécution d'une réalisation en attribuant des ressources aux tâches et en fixant leur date d'exécution pour optimiser un ou plusieurs objectifs.

Dans cette thèse, il s'agit d'étudier une nouvelle classe de problèmes d'ordonnancement multicritères : "Les problèmes d'ordonnancement interférants (dits aussi, multi-agents) sous un objectif globale".

En effet, dans la plupart des études en ordonnancement multicritère, tous les travaux contribuent de la même façon à la mesure de la qualité de la solution, et celle-ci peut être donnée par plusieurs critères. Cependant, il arrive dans certains cas réels que l'application de la même mesure à tous les travaux ne soit pas pertinente. Ainsi, nous considérons qu'un critère est fourni pour l'ordonnancement de l'ensemble des travaux, mais que les autres critères peuvent porter sur un sous-ensemble des travaux. Ces problèmes se posent dans ces termes pour certaines entreprises où la production journalière est évaluée par un critère qui porte sur tous les travaux, et où des sous-ensembles de travaux doivent respecter des contraintes – parfois imposées par les clients ou relatives aux retards déjà accumulés – selon d'autres critères. On parle alors les problèmes d'ordonnancements de travaux interférants : on cherche alors à déterminer un ordonnancement qui permet d'optimiser un critère pour la globalité des travaux à effectuer, sachant que la solution trouvée doit permettre également l'optimisation d'un autre critère défini uniquement sur un sous-ensemble des travaux.

Il s'agit ici d'un nouveau problème d'ordonnancement multicritère, différent de la notion classique, et qui se rapproche des problèmes de type "multi-agent scheduling" ou "interfering job sets". Les approches considérées pour trouver une solution non dominée sont l'approche -contrainte et la combinaison linéaire de critères pour l'ordonnancement des travaux indépendants sur une machine ou sur des machines parallèles.

De nouveaux résultats de complexité sont à élaborer et des algorithmes polynomiaux/pseudo-polynomiaux et des schémas d'approximation sont à développer pour le calcul des solutions non dominées et donc pour trouver la courbe des optima de Pareto. Le doctorant débutera son travail de thèse par un état de l'art sur les problèmes d'ordonnancement multicritères abordés puis en mettant en place des méthodes et algorithmes de résolution efficaces où une attention particulière est donnée à :
i) la relaxation lagrangienne,
ii) la programmation dynamique,
iii) Programmation mathématique
iv) Schémas d'approximation