Stage Master Recherche - ordonnancement avec considération d'outils

Forum 'Stages' - Sujet créé le 22/11/2022 par unknown (602 vues)

Le 22/11/2022 par unknown :

Une offre de stage Master 2 de 5 mois (début en février 2023) est ouverte au sein du LIMOS et du Département Génie Mathématique et Industriel de l'École des Mines de Saint-Étienne.

Ce sujet de stage s'interesse à l'étude et applications des techniques de recherche opérationnelle pour un problème d'ordonnancement de tâches avec considération d'outils.

Le candidat doit avoir un profil lié aux domaines de la recherche opérationnelle et/ou informatique avec des connaissances en au moins un langage de programmation.

Pour plus de détails et pour savoir comment se candidater, veuillez consulter les détails ci-dessous.


A 5-month Master 2 internship offer (starting in February 2023) is open at the LIMOS in the Department of Mathematics and Operations Research for Engineering at the École des Mines de Saint-Étienne.

The subject of the internship concerns the study and applications of operations research methods to a scheduling problem with tooling constraints.

The candidate must have competences in operations research and/or computer science with knowledge in at least one programming language.

For more details on the offer and on how to apply, see the message below.


Subject: The job sequencing and tool switching problem with non-identical parallel machines

Keywords: Job sequencing and tool switching problem; parallel machines; combinatorial optimization; integer linear programming; arc-flow; decomposition methods; constraint programming.

Contact: Arthur Kramer (}) and Khadija Hadj Salem (

Basic information

  • Internship duration: 5 months
  • Starting date: February 2023
  • Location: École des Mines de Saint-Étienne, Henri Fayol Institute, Saint-Étienne, France
  • Supervisors: Arthur Kramer (Mines Saint-Étienne, UMR CNRS 6158 LIMOS) and Khadija Hadj Salem (Mines Saint-Étienne, UMR CNRS 6158 LIMOS)

Candidate profile

  • Good programming skills (C++, Java, Python, Julia);
  • Good knowledge of operations research and combinatorial optimization (ILP, heuristics);
  • Familiarity with optimization solvers such as Cplex, Gurobi, Xpress;
  • Knowledge of decomposition methods (column generation, Dantzig–Wolfe, Benders) or constraint programming is a plus;
  • A good level of English is highly appreciated.


  • To apply, candidates must send, before 9th of December, their CV and a cover letter to Arthur Kramer (}) and Khadija Hadj Salem (


Manufacturing systems commonly involve processing a set of jobs subject to the presence of limited resources (e.g., time, machines, energy, personnel). Due to market competitiveness, it is required that companies become more flexible and optimize the utilization of their scarce resources.

In this sense, it arises the job sequencing and tool switching problem (SSP), in the context of flexible manufacturing systems (FMS). In FMS, it is often possible to process a variety of jobs that have different requirements in terms of tools, by loading/unloading the tools on a limited storage buffer. The SSP was initially proposed by Bard (1988) and Tang and Denardo (1988) and has been proved to be a combinatorial NP-hard problem.

In the SSP, we are given a set of jobs J, a set of tools T and a magazine capacity C. One machine is available to process all jobs, one at a time. Each job j ∈ J requires a subset Tj of tools to be loaded during its processing and at most C tools can be loaded simultaneously. Since job requirements, in terms of tools, may be different, and the magazine capacity is limited, tool switches are needed to fully process all jobs. Considering that all jobs have a unit processing time and that tool switching times are neglected, the objective of the problem is to find a processing sequence of jobs that minimizes the total number of tool switches.

In this research internship proposal, we are particularly interested in a variant of the SPP where the jobs may have non-unit processing times, the tool switching operations times are not neglected and a set of non-identical parallel machines are available to process the jobs. In the environment of non-identical parallel machines, the processing times of the jobs depend on the machine the jobs will be processed and each machine has an independent magazine capacity which also depends on the machine. This variant, called job sequencing and tool switching problem with non-identical parallel machines (SSP-NPM), was addressed by Calmels (2019), with the aim of minimizing the objective functions related to job execution times (e.g., makespan, total flow time) and/or the number of tool switches.

SSP-NPM is particularly challenging because it combines features of SSP and scheduling problems with parallel machines. Both are known NP-hard problems. Thus, combining solution methods already successfully used for both problems, such as arc-flow models, constraint programming (CP) methods, and/or heuristics should be considered.

The main objectives of this research internship are the following:

  • Identify the main solution methods already proposed to solve the SSP-NPM;
  • Implement (or adapt) some of the methods from the literature to use them as a reference;
  • Propose new mathematical models and/or heuristic methods;
  • Perform computational experiments;

Moteur de recherche
Tous les forums

  La Société française de Recherche Opérationnelle et Aide à la Décision ROADEF est une association Loi 1901 Plus d'informations sur la ROADEF