Algorithmes d?optimisation pour l?ordonnancement en ligne

Proposition de Stage

Algorithmes d’optimisation pour l’ordonnancement en ligne.

Laboratoire :              Logistique et Optimisation des Systèmes Industriels (LOSI), Institut Services et Industries du Futur de Troyes (ISIFT), UTT

Localisation :               Troyes, France

Profil recherché :        Étudiant Master 2 ou 5ème année d’école d’ingénieur en informatique, recherche opérationnelle ou mathématiques appliquées.

Durée :                        4 à 6 mois

Dans l’ère de l’industrie 4.0 (Factory of the Future) : les plans de production peuvent être modifiés en permanence, des tâches sont régulièrement créés par des commandes en ligne, les machines sont flexibles, la maintenance peut être planifiée. La théorie de l’ordonnancement en temps réel a été développée depuis des années 90 ; toutefois, ses applications se restreignaient aux domaines d’information et de calcul plutôt que dans le domaine de la production. Dans ce contexte, une approche de l’ordonnancement en ligne, plus particulièrement, sur les machines parallèles, sera une approche efficace pour faire face à ces problèmes d’ordonnancement myopes et flexibles.

Dans un premier temps, une étude sur les algorithmes d’ordonnancement déjà développés au sein du laboratoire est souhaitée. Une plateforme de simulateur des algorithmes d’ordonnancement en temps réel est en cours de développement. Nous espérons la transformer en une boite d’outils de planification en ligne qui serait plus générique et ayant une librairie d’algorithmes plus importante. Une documentation complète de l’outil est espérée pour faciliter l’utilisation de l’utilisateur.

Le problème d’optimisation est défini par la notation de trois champs de Graham . Dans le périmètre du stage l’outil va se concentrer sur l’environnement de machines parallèles identiques. Il faudra construire une librairie de contraintes et de fonctions objectifs avec les algorithmes de l’optimisation correspondants. L’algorithme développé pour un problème plus complexe sera capable de s’adapter pour résoudre un problème plus générique en relaxant les contraintes correspondantes. La représentation graphique de la solution sera également un objectif essentiel de ce stage.

Compétence souhaité

• Bonnes connaissances en recherche opérationnelle surtout dans le domaine d’ordonnancement sur machines parallèles.
• Très bonnes aptitudes de programmation et une maitrise d’un ou plusieurs langages de programmation (Matlab et C++ de préférence).
• Un précédent travail de recherche sera un plus.

Contacts

Les candidats potentiels sont invités à envoyer leur CV, lettre de motivation et notes de Master à nhan_quy.nguyen@utt.fr

Bibliographie

1. ALBERS, Susanne. Competitive online algorithms. Computer Science Department, University of Aarhus, 1996.
2. YALAOUI, Farouk et CHU, Chengbin. Parallel machine scheduling to minimize total tardiness. International Journal of Production Economics, 2002, vol. 76, no 3, p. 265-279.
3. YALAOUI, Farouk et CHU, Chengbin. An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times. IIE Transactions, 2003, vol. 35, no 2, p. 183-190.
4. SUCHA, Premysl, KUTIL, Michal, SOJKA, Michal, et al. Torsche scheduling toolbox for Matlab. In : Computer Aided Control System Design, 2006 IEEE International Conference on Control Applications, 2006 IEEE International Symposium on Intelligent Control, 2006 IEEE. IEEE, 2006. p. 1181-1186.
5. ALBERS, Susanne. Online scheduling. Introduction to Scheduling, 2009, vol. 3, p. 51-73.
6. LIU, Peihai et LU, Xiwen. On-line scheduling of parallel machines to minimize total completion times. Computers & Operations Research, 2009, vol. 36, no 9, p. 2647-2652.
7. CHEN, Xin, STERNA, Malgorzata, HAN, Xin, et al. Scheduling on parallel identical machines with late work criterion: Offline and online cases. Journal of Scheduling, 2016, vol. 19, no 6, p. 729-736.
8. NGUYEN, Nhan-Quy, YALAOUI, Farouk, AMODEO, Lionel, et al. Reactive rescheduling method for electric vehicles charging in dedicated residential zone parking. In : Computational Intelligence (SSCI), 2017 IEEE Symposium Series on. IEEE, 2017. p. 1-6.