Institut Fayol – Mines St Etienne

Offre de stage de Master 2 : « Coupler l’optimisation et l’apprentissage automatique pour résoudre les problèmes d’ordonnancement de machines parallèles sous incertitude »

2/12/2024 par Florent BREUIL

English below

 

Vous êtes à la recherche d’une offre de stage de Master ? Vous aimeriez le faire dans un laboratoire d’une grande École d’ingénieur ? Vous rêveriez de participer à de vrais programmes de recherche ?

L’Institut Henri Fayol, École des Mines de Saint-Étienne, vous offre l’opportunité de réaliser un stage de Master 2 dans son   département Génie Mathématique et Industriel.

Sujet : « Coupler l’optimisation et l’apprentissage automatique pour résoudre les problèmes d’ordonnancement de machines parallèles sous incertitude – 5 mois « 

Stage de recherche pour étudiants en 3ᵉ année d’école d’ingénieurs ou en 2ᵉ année de Master

  1. Sujet :
    Les problèmes d’ordonnancement [5] sont étudiés depuis les années 1950. Ils relèvent de la recherche opérationnelle, en particulier de l’optimisation combinatoire. En général, ces problèmes consistent à assigner et organiser des tâches sur des ressources limitées, tout en respectant diverses contraintes (e.g., configurations, délais) et en optimisant un ou plusieurs critères. De nombreuses applications pratiques, dans les systèmes de production ou les services, peuvent être modélisées sous la forme d’un problème d’ordonnancement de machines parallèles (PMSP).

    Dans la littérature, les PMSP sont souvent étudiés dans une configuration statique-déterministe, où toutes les données nécessaires sont connues à l’avance et exactes. Dans ce cadre, des méthodes exactes [2], heuristiques [6] ou hybrides sont généralement utilisées pour résoudre ces problèmes.

    Cependant, dans de nombreux cas pratiques, les données disponibles ne sont ni complètes ni exactes, en raison d’incertitudes [3, 1]. Ces incertitudes peuvent provenir, par exemple, de pannes machines, de l’arrivée imprévue de nouvelles tâches, ou de changements dans les délais ou les temps de traitement. Pour y faire face, des algorithmes de reprogrammation sont généralement proposés. Certaines approches se basent sur des règles de réoptimisation simples sans considérer les aspects stochastiques du problème, tandis que les méthodes prédictives-réactives élaborent un calendrier initial à partir d’informations préliminaires (étape prédictive) et ajustent ce calendrier en fonction des perturbations (étape réactive).

    Récemment, la communauté s’est tournée vers l’utilisation de méthodes basées sur l’apprentissage automatique (e.g., apprentissage par renforcement ou apprentissage profond) pour les problèmes d’ordonnancement [4]. Ces méthodes permettent à un ou plusieurs agents de prendre des décisions à partir de données historiques ou en temps réel. Cette proposition vise à intégrer des techniques d’optimisation (e.g., métaheuristiques) et d’apprentissage automatique dans une approche prédictive-réactive pour traiter les PMSP sous incertitude.

    Objectifs principaux du stage :

    • Réaliser une revue de littérature sur les problèmes d’ordonnancement de machines parallèles sous incertitude.
    • Définir un problème d’ordonnancement à explorer.
    • Identifier les principales méthodes de résolution déjà proposées.
    • Implémenter ou adapter certaines méthodes de référence.
    • Étudier les approches heuristiques et basées sur l’apprentissage automatique.
    • Proposer une méthode prédictive-réactive intégrant des composants heuristiques et d’apprentissage automatique.
    • Mener des expériences computationnelles.

    Mots-clés : problème d’ordonnancement; dynamique-stochastique; méthode prédictive-réactive; apprentissage automatique; métaheuristique.

  1. Informations générales

  • Durée du stage : 5 mois
  • Date de début : Dès que possible et au plus tard le 31 mars 2025
  • Lieu : LIMOS, École des Mines de Saint-Étienne, Institut Henri Fayol, Saint-Étienne, France
  • Indemnités : Montant légal (voir détails ici)
  • Encadrants : Arthur Kramer (Mines Saint-Étienne, UMR CNRS 6158 LIMOS) et Damien Lamy (Mines Saint-Étienne, UMR CNRS 6158 LIMOS)

Profil recherché

  • Formation : 3ᵉ année d’école d’ingénieurs (ou éventuellement 2ᵉ année de Master) avec possibilité de poursuivre en thèse (avec un partenaire industriel).
  • Compétences techniques : Solides compétences en programmation (C++, Python, Java…).
  • Connaissances : Bonne maîtrise de la recherche opérationnelle et de l’optimisation combinatoire.
  • Expérience : Familiarité avec les heuristiques et les méthodes d’apprentissage automatique ; une expérience avec les problèmes d’ordonnancement est un atout.
  • Langues : Un bon niveau d’anglais est apprécié.

Candidature

Pour postuler, envoyez avant le 12 décembre :

  • votre CV,
  • une lettre de motivation,
  • une copie des relevés de notes les plus récents.

Envoyez vos documents à :

Références

  1. Xavier Delorme, Audrey Cerqueus, Paolo Gianessi, et Damien Lamy. RMS balancing and planning under uncertain demand and energy cost considerations. Int. Journal of Production Economics, 261:108873, 2023.
  2. Arthur Kramer, Manuel Iori, et Philippe Lacomme. Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization. European Journal of Operational Research, 289(3):825–840, 2021.
  3. Djamila Ouelhadj et Sanja Petrovic. A survey of dynamic scheduling in manufacturing systems. Journal of scheduling, 12:417–431, 2009.
  4. Ayoub Ouhadi, Zakaria Yahouni, et Maria Di Mascolo. Integrating machine learning and operations research methods for scheduling problems: a bibliometric analysis and literature review. IFAC-PapersOnLine, 58(19):946–951, 2024.
  5. Michael L Pinedo. Scheduling: Theory, Algorithms, and Systems, volume 6. Springer Cham, 2022.
  6. Rubén Ruiz. Scheduling Heuristics, pages 1197–1220. Springer International Publishing, Cham, 2018.

Coupling optimization and machine learning to deal with parallel machine scheduling problems under uncertainty
Research Internship for 3rd-year engineering school students or 2nd-year Master students

Subject
Scheduling problems [5] have been widely studied since de 1950s. This is a classical problem in the operations research field, and in particular, in the combinatorial optimization class. In general, scheduling problems concern to the assignment and sequencing of tasks to a set of limited resources subject to a variety of constraints  (e.g., setup, deadline) and aiming to optimize one or several criteria. Many practical applications in manufacturing systems and in services can be modeled as a Parallel Machine Scheduling Problem (PMSP). In the literature, PMSPs are often considered in its static-deterministic form, i.e., all needed data are known in advance (at the moment the decisions need to be taken) and are accurate. In this configuration, PMSPs are commonly solved by means of exact [2], heuristics [6] or hybrid methods.
However, in many real-life problems, the hypothesis that the needed data is known in advance, complete and accurate is not verified, i.e., the observed information may be different from the expected/estimated one due to uncertainty [3, 1]. Uncertain events can be related, e.g., to machine breakdowns, new job arrivals, due date and processing time changes. To deal with them, rescheduling algorithms are usually proposed. Some of them are based on simple re-optimization methods based on simple dispatching rules without considering the stochastic nature of the problem. Predictive-reactive methods, in turn, focuses on the proposal of an initial schedule (predictive step) by using some prior information about the events that may disrupt the system. The execution of this initial schedule is then controlled and adjustments (reactive step) are done when necessary. Recently, scheduling community turned out its attention to the study and application  of machine learning-based methods (e.g., reinforcement and deep reinforcement learning) to deal with  cheduling problems [4]. Mainly, in these methods an (or multiple) agent learn, by using historical, and eventually real-time, data in order to take decisions. Thus, the objective of this proposition is to study the integration of optimization (e.g., metaheuristics) and machine learning (e.g., reinforcement learning) methods into a predictive-reactive approach to deal with PMSP under uncertainty.

The main objectives of this research internship are the following:

  • Perform a literature review on parallel machine scheduling problems under uncertainty;
  • Define a parallel machine scheduling problem to investigate;
  • Identify the main solution methods already proposed in the literature;
  • Implement (or adapt) some of the methods from the literature to use them as a reference;
  • Study on heuristics and machine-learning-based methods for scheduling problems;
  • Propose a predictive-reactive method with heuristic and machine-learning components;
  • Perform computational experiments.

Keywords: scheduling problem; dynamic-stochastic; predictive-reactive method; machine-learning; metaheuristic.

Basic information

  • Internship duration: 5 months
  • Starting date: As soon as possible and no later than 31 March 2025
  • Location: LIMOS, Ecole des Mines de Saint- ´ Etienne, Henri Fayol Institute, Saint- ´ Etienne, France ´
  • Indemnities: Legal amount (https://www.service-public.fr/particuliers/vosdroits/F32131)
  • Supervisors: Arthur Kramer (Mines Saint-Etienne, UMR CNRS 6158 LIMOS) ´
    Damien Lamy (Mines Saint-Etienne, UMR CNRS 6158 LIMOS) ´

Candidate profile

  • 3rd year of an engineering school (eventually 2nd year of MSc) with possibility of pursuing in PhD (with industrial partner);
  • Strong programming skills (C++, Python, Java…) is a must;
  • Good knowledge of operations research and combinatorial optimization;
  • Familiarity with heuristics and machine-learning methods;
  • Experience with scheduling problems is a plus;
  • A good level of English is highly appreciated.

Application
To apply, candidates must send, before 12th of December, their CV, a motivation letter and a copy of the last transcript of records to Arthur Kramer (arthur.kramer@emse.fr) and Damien Lamy (damien.lamy@emse.fr).

References
[1] Xavier Delorme, Audrey Cerqueus, Paolo Gianessi, and Damien Lamy. RMS balancing and planning under
uncertain demand and energy cost considerations. Int. Journal of Production Economics, 261:108873, 2023.
[2] Arthur Kramer, Manuel Iori, and Philippe Lacomme. Mathematical formulations for scheduling jobs on identical
parallel machines with family setup times and total weighted completion time minimization. European Journal
of Operational Research, 289(3):825–840, 2021.
[3] Djamila Ouelhadj and Sanja Petrovic. A survey of dynamic scheduling in manufacturing systems. Journal of
scheduling, 12:417–431, 2009.
[4] Ayoub Ouhadi, Zakaria Yahouni, and Maria Di Mascolo. Integrating machine learning and operations research methods for scheduling problems: a bibliometric analysis and literature review. IFAC-PapersOnLine,
58(19):946–951, 2024. 18th IFAC Symposium on Information Control Problems in Manufacturing INCOM 2024.
[5] Michael L Pinedo. Scheduling: Theory, Algorithms, and Systems, volume 6. Springer Cham, 2022.
[6] Rub´en Ruiz. Scheduling Heuristics, pages 1197–1220. Springer International Publishing, Cham, 2018.

#LIMOS

Illustration : “Designed by Freepik”  http://www.freepik.com/
ODD9-scaled

Commentaires Clos.