CRAN - Campus Sciences
BP 70239 - 54506 VANDOEUVRE Cedex
Tél : +33 (0)3 72 74 52 90
Ph. D. Project : DES-based scheduling with uncertainty : definition of a stochastic modelling and solving framework, application to production and maintenance tasks scheduling
Dates : 2017/10/04 - 2020/09/30
Student: Sara HIMMICHE
Manager(s) CRAN: Jean-François PETIN , Alexis AUBRY
Full reference: Task scheduling consists in defining starting and completion dates of a given sequence of tasks, using dedicated resources, to produce a given service. When considering production systems, tasks may be manufacturing or maintenance operations, performed on machines, to produce a set of products or to ensure the availability of the production system. A large scope of problems is hidden behind this general definition, depending on the system structure and its operational environment.
To face this large variety of problems, operational research has produced many methods such as linear programming and so on. However, the involved models are often expressed as static mathematical programming formulations by considering a certain and stable environment. These models do not include the description of the system and environment dynamics . In practice, good performance achieved by the system in given conditions can be drastically deteriorated if these conditions change. It means that the optimal schedule considering a stable and static environment has often to be completed by online re-scheduling plans that adapt the initial schedule to perturbations. This need is particularly acute in the context of the Factories of the future or Industries 4.0 for facing the high variability of customized products and for taking benefit from IoT real-time information about system state (such as resources state monitoring, failure detection or ageing observations).

Faced to the classical Operational Research approaches for production scheduling, methods based on Discrete Event Systems (DES) theory have emerged to model and solve optimisation (Lemattre et al., 2011) and scheduling of production problems (Panek et al., 2006, Kobetski and Fabian, 2009). The basic underlying idea is to model the scheduling problem as a state-transition model that represent the sequence of operations and the machines availability and to use reachability analysis for finding a possible path that enables to reach the the state where all the jobs are finished. The trace from the initial state to the expected state provides one admissible schedule.

The efficiency of DES theory for modelling and solving a scheduling problem has been explored by several works (Behrmann et al., 2005 ; Panek et al., 2006 ; Subbiah and Engell, 2010).
Main conclusions of these related works consider the DES-based approaches as good alternatives for solving scheduling problems. However, most of the existing applications concern the classical job-shop problem with static operational routes without really taking advantage from the DES modularity. Introducing flexibility in the scheduling problem thanks to DES methods has been addressed by (Marangé et al., 2011) and has give rise to a research action, leaded by CRAN, within the French Thematic Research Group SED (Discrete Events Systems) of the GDR MACS Moreover, the efficiency of this approach regarding the modeling point of view has been studied in (Himmiche et al., 2017).

The objective of this PhD thesis is to enrich DES-based scheduling methods by taking into account the dynamics of the systems and the inherent perturbations.

The scientific issues are related to both modelling and application problems:
1) Modelling issues are related to the definition of a formal stochastic DES framework relevant to:
- capture the scheduling problem in an uncertain environment and more precisely to solve the problem of compositionality within DES stochastic models,
- to automatically compute a schedule from those DES stochastic models by enriching the deterministic trace given by a reaching graph by a stochastic trace (for example using the Probabilistic Languages theory),
2) Application issues are related to answer that should be given to only partially solved problem such as :
- finding a set of production operations schedules and quantifying each schedule by a probability of completion taking into account a stochastic model of the resources reliability and availability as well as the various production and failure modes,
- finding a predictive maintenance schedule that enforces production objectives and machines availability taking into account ageing models of the system and residual capabilities of the machines.

To answer to these issues, the thesis will follow the following program:
1) Make a state of the art on DES stochastic languages and their applications. The goal here is to:
- Identify and discuss the different available DES languages based on stochastic data (Stochastic Petri nets, Stochastic automata, Bayesian networks) and their associated solving methods.
- Identify and discuss the different classical stochastic approaches (stochastic programming \ldots).
- For each language (DES) or classical approach, evaluate the capacity to model perturbations, to give relevant information, to be relevantly interpretable in the context of production systems.
- Evaluate the efficiency of each associated solving methods.

2)Propose a stochastic DES-based scheduling method by defining:
- a modelling framework dedicated to scheduling in an uncertain environment; it requires to define different classes of perturbations and define how they should be modelled in the selected DES language; the models of a flexible manufacturing system can be based on previous works (Marangée et al., 2016) that should be extended to capture uncertainty in the system and in its environment; modularity of (Marangée et al., 2016) models will need to be considered by defining compositional or synchronisation operators onto DES stochastic models,
- a solving method that must be able to build reactive schedules after the occurrence of a perturbation (it means to propose an analysis algorithm to compute a reaching trace between current and targetted states), and to quantify the occurrence probability of this trace.

3) Evaluate the overall modeling and solving framework face to classical approaches for production and maintenance reactive scheduling. The goal here is to:
- Apply the overall approach on a use case, ideally taken from an industrial partner.
- Considering the modeling approach, evaluate its complexity, genericity and scalability as defined in (Himmiche et al., 2017).
- Considering the solving approach, evaluate its efficiency for production and maintenance scheduling problem under perturbations.
Keywords: Flexible Manufacturing Systems, Scheduling, Stochastic DES Models
Eco-Technic systems engineering
Publications: hal-01094679, hal-00627635, hal-00654166    + CRAN - Publications