Skip to Main content Skip to Navigation

Méthodes d'optimisation robuste pour les problèmes d'ordonnancement cyclique

Idir Hamaz 1 
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : Several studies on cyclic scheduling problems have been presented in the literature. However, most of them consider that the problem parameters are deterministic and do not consider possible uncertainties on these parameters. However, the best solution for a deterministic problem can quickly become the worst one in the presence of uncertainties, involving bad schedules or infeasibilities. Many sources of uncertainty can be encountered in scheduling problems, for example, activity durations can decrease or increase, machines can break down, new activities can be incorporated, etc. In this PhD thesis, we focus on scheduling problems that are cyclic and where activity durations are affected by uncertainties. More precisely, we consider an uncertainty set where each task duration belongs to an interval, and the number of parameters that can deviate from their nominal values is bounded by a parameter called budget of uncertainty. This parameter allows us to control the degree of conservatism of the resulting schedule. In particular, we study two cyclic scheduling problems. The first one is the basic cyclic scheduling problem (BCSP). We formulate the problem as a two-stage robust optimization problem and, using the properties of this formulation, we propose three algorithms to solve it. The second considered problem is the cyclic jobshop problem (CJSP). As for the BCSP, we formulate the problem as two-stage robust optimization problem and by exploiting the algorithms proposed for the robust BCSP we propose a Branch-and-Bound algorithm to solve it. In order to evaluate the efficiency of our method, we compared it with classical decomposition methods for two-stage robust optimization problems that exist in the literature. We also studied a version of the CJSP where each task duration takes uniformly values within an interval and where the objective is to minimize the mean value of the cycle time. In order to solve the problem, we adapted the Branch-and-Bound algorithm where in each node of the search tree, the problem to be solved is the computation of a volume of a polytope. Numerical experiments assess the efficiency of the proposed methods.
Complete list of metadata

Cited literature [131 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Monday, September 30, 2019 - 3:48:09 PM
Last modification on : Wednesday, June 1, 2022 - 3:55:34 AM


Version validated by the jury (STAR)


  • HAL Id : tel-01975512, version 2


Idir Hamaz. Méthodes d'optimisation robuste pour les problèmes d'ordonnancement cyclique. Génie des procédés. Université Paul Sabatier - Toulouse III, 2018. Français. ⟨NNT : 2018TOU30205⟩. ⟨tel-01975512v2⟩



Record views


Files downloads