Titre : Contribution à l’ordonnancement biniveau :  modèles, algorithmes et application à l’Industrie du Futur. 

Directeurs de thèse : 

 (France) Vincent T’kindt  - email : tkindt@univ-tours.fr

 (Italie) Federico Della Croce – email : federico.dellacroce@polito.it

Mots clés :

     Ordonnancement, optimisation biniveau, Recherche Opérationnelle, Machine Learning, Industrie du Futur.

1. Contexte de la thèse 

Cette thèse sera réalisée en co-tutelle entre l’Université de Tours et le Politecnico di Torino (Italie). Le doctorant sera encadré conjointement par le Pr. Vincent T’KINDT (Laboratoire d’Informatique Fondamentale et Appliquée de Tours, LIFAT, Université de Tours) et le Pr. Federico DELLA CROCE (Department of Management and Production Engineering, DIGEP, Politecnico di Torino).

Le doctorant effectuera donc un séjour de 1,5 années au LIFAT puis 1,5 années au DIGEP mais sera en permanence encadré par ses deux directeurs de thèse. 

Scientifiquement, les recherches réalisées s’intègreront dans le cadre de la Chaire Industrielle Industrie du Futur, portée par Polytech Tours et le LIFAT.

2. Descriptif de la Thèse 

Nous nous intéresserons à une récente classe de problèmes d’ordonnancement appelés problèmes d’ordonnancement biniveaux ([4, 5, 6, 7, 8]).

Dans un problème d’optimisation biniveau on considère que dans le processus de décision un leader et n followers participent à la construction d’une solution s=(x,y1, …, yn), avec x le vecteur des décisions prises par le leader et yk le vecteur des décisions prises par le follower k. Chaque agent, qu’il soit leader ou follower¸ prend ses décisions pour optimiser une fonction objectif qui lui est propre. Néanmoins, pour chaque agent, la valeur de cette fonction objectif dépend des décisions prises par les autres agents. 

L’intrication de ces décisions rend les problèmes d’optimisation biniveau extrêmement difficiles à résoudre ([9]) et peu abordés dans le contexte de l’ordonnancement de la production ([8]) : il y a donc un challenge à relever et pour lequel les outils de la Recherche Opérationnelle sont pertinents.

Nous aborderons des problèmes d’ordonnancement biniveaux dans le cadre de l’Industrie du Futur, et même plus précisément dans le cadre d’une politique Zero Defect Manufacturing (ZDM) dont le but est de limiter les pannes machines conduisant à des arrêts de production ([1,2, 3]). Le leader est dans ce cas l’unité de supervision ZDM et les followers sont les différents ilots de production également appelés CPS. 

Nous nous intéresserons à la définition de modèles d’ordonnancement biniveaux de base tels que pouvant survenir dans l’Industrie du Futur. Pour ces modèles, nous établirons leur complexité théorique puis proposerons des méthodes exactes et heuristiques issues de la Recherche Opérationnelle (programmation mathématique, méthodes arborescentes, metaheuristiques, …). Nous aimerions aussi pouvoir mettre au point des algorithmes tirant partis des outils du Machine Learning, notamment pour guider les algorithmes d’ordonnancement mis au point. Ce dernier point se fera si le candidat possède des compétences en Machine Learning.

Le sujet de thèse est donc novateur au regard tant des problèmes abordés (problèmes d’ordonnancement biniveaux) que des méthodes mises au point.

 3. Programme prévisionnel 

Le programme scientifique général est le suivant :

Année 2023-2024 :

• Etat de l’art sur les problèmes de planification au sein de l’Industrie du Futur, sur les problèmes d’ordonnancement biniveau, et sur les techniques d’apprentissage en Recherche Opérationnelle.
• Etude et résolution d’un premier problème (P1) avec un superviseur ZDM et un CPS regroupant plusieurs machines fonctionnant en parallèle.

Année 2024-2025 :

• Etude et résolution du problème (P2) avec un superviseur ZDM et plusieurs CPS regroupant chacun plusieurs machines fonctionnant en parallèle.

Année 2025-2026 :

• Problème (P3) : Extension des travaux de l’année précédente dans un contexte dynamique (re-ordonnancement en temps réel).
• Rédaction du manuscrit de thèse et soutenance. 

L’état de l’art va permettre d’affiner la définition des problèmes de planification et d’ordonnancement à résoudre, notamment au niveau des objectifs et contraintes particulières à une politique ZDM au sein de l’Industrie du Futur. L’étude d’un premier problème (P1) va permettre au doctorant de mettre au point des premiers algorithmes couplant Recherche Opérationnelle et Apprentissage Automatique qui pourront être éventuellement réutilisés dans le cadre de la résolution du problème (P2), qui est plus général. Les algorithmes proposés seront des algorithmes exacts, retournant une solution optimale mais en temps exponentiel, et des algorithmes heuristiques, retournant une solution sous optimale mais en temps polynomial. 

Les problèmes (P1) et (P2) sont des problèmes dits statiques, c’est-à-dire que nous connaissons l’ensemble des travaux à réaliser au moment de la résolution du problème d’ordonnancement. Dans un contexte appliqué, il est plutôt pertinent de considérer leur version dynamique : à chaque instant de réordonnancement (la journée ou la semaine), de nouveaux travaux entrent dans l’atelier et doivent être ordonnancés sans trop perturber l’ordonnancement en cours. Le problème (P3) est la version dynamique du problème (P2) pour lesquels nous mettrons au point des algorithmes exactes et heuristiques de réordonnancement de la production. 

Tous les travaux feront l’objet de communication dans des conférences nationales et internationales du domaine. Ils seront également soumis pour publication dans des revues internationales avec ouverture en open accès aux articles de recherche, aux données et aux algorithmes produits. 

4. Comment candidater ? 

Il suffit de prendre contact avec les deux encadrants et d’envoyer : un CV, une lettre de motivation, vos relevés de notes de master (ou équivalent). Vous pouvez y joindre des lettres de recommandation.

Les compétences minimum recherchées sont : 

• Une bonne connaissance des outils de la Recherche Opérationnelle,
• Connaître les notions de base de la théorie de la complexité,
• Être curieux et passionné par la recherche,
• Savoir développer dans un langage de programmation de type C ou C++.

Avoir une bonne connaissance des outils du Machine Learning est un plus mais n’est pas obligatoire. 

Références bibliographiques 

[1] Hermann, M., T. Pentek, and B. Otto. (2016). Design Principles for Industrie 4.0 Scenarios, In 49th IEEE Hawaii International Conference on System Sciences (HICSS), 3928–3937. 

[2] Parente, M., Figueira, G., Amorim, P. and A. Marques (2020). Production scheduling  in the context of Industry 4.0 : review and trends, International Journal of Production Research, 58(17):5401-5431.

[3] Psarommatis, F., Kiritsis, D. (2018). A Scheduling Tool for Achieving Zero Defect Manufacturing (ZDM): A Conceptual Framework. In: Moon, I., Lee, G., Park, J., Kiritsis, D., von Cieminski, G. (eds) Advances in Production Management Systems. Smart Manufacturing for Industry 4.0. APMS 2018. IFIP Advances in Information and Communication Technology, vol 536. Springer.

[4] Karlof J. and W. Wang (1996). Bilevel programming applied to the flowshop scheduling problem, Computers and Operations Research, 23:443-451. 

[5] Abass, S. (2005). Bilevel programming approach applied to the flow-shop  scheduling problem under fuzziness, Computational Management Science, 2:279-293.

[6] Kovacs, A. and T. Kis (2011). Constraint programming approach to a bilevel scheduling problem, Constraints, 16:317-340.

[7] Kis, T. and A. Kovacs (2012). On bilevel machine scheduling problems, OR Spectrum, 34:43-68.

[8] T’kindt, V., Della Croce F. and A. Agnetis (2023). Single machine adversarial bilevel scheduling problems, European Journal of Operational Research, submitted. 

[9] Woeginger, G. (2021). The trouble with the second quantifier, 4OR, 19:157-81.