Coupling optimization and machine learning to deal with parallel machine scheduling problems under uncertainty

Basic information:

• How to apply: Follow the instructions in the detailed offer ( https://filesender.renater.fr/?s=download&token=8c33ce37-2cda-4047-b957-6df545ecc360 ) 
• Internship duration: 5 months
• Starting date: As soon as possible and no later than 31 March 2025
• Location: LIMOS, École des Mines de Saint-Étienne, Henri Fayol Institute, Saint-Étienne, France
• Supervisors: Arthur Kramer; Damien Lamy (École des Mines de Saint-Étienne, UMR CNRS 6158 LIMOS)

Context:

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 [5] 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, predictive-reactive methods can be developped. These methods focus 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) [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.

Main objectives:

• 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; optimization; dynamic-stochastic; predictive-reactive method; machine-learning; metaheuristic.

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 optimization problems;
• Familiarity with (meta-)heuristics and machine-learning methods;
• Experience with scheduling problems is a plus;
• A good level of English is highly appreciated.

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] Rubén Ruiz. Scheduling Heuristics, pages 1197–1220. Springer International Publishing, Cham, 2018.