Skip to Main content Skip to Navigation
Conference papers

Two-stage stochastic/robust scheduling using permutable operation groups

Louis Rivière 1, 2 Christian Artigues 1 Hélène Fargier 2 
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes
2 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
IRIT - Institut de recherche en informatique de Toulouse
Abstract : This paper considers a single machine scheduling problem with release dates, due dates,precedence constraints and aiming for the minimization of the maximum lateness or the sumof completion times over a sampled set of release dates scenarios, either in a stochastic orrobust setting. The standard 2-stage approach for stochastic and robust scheduling on a singlemachine considers first-stage decisions that output a full ordering (sequence) of the jobs (J-SEQ) on the machine and second-stage decisions that set the job start times in accordancewith the information of a given scenario.. In this paper, we study the performances of analternative 2-stage solution method based on groups of permutable jobs. The method, initiallypresented in [1], considers first-stage decisions that output only a partial ordering in the formof a sequence of groups of permutable jobs (G-SEQ). Given a scenario, the second stage policyorders the jobs inside each group according to the earliest realized release date first heuristic.We introduce a constraint programming approach to compute an optimal G-SEQ solutionbut show that in a limited time, it provides poor quality solutions on the largest instancescompared to a standard J-SEQ solution approach. We then design several heuristics that usea portion of the time limit to obtain good quality J-SEQ starting solutions and then switch toG-SEQ solutions via greedy or local search. The best G-SEQ heuristics outperform all of thestandard J-SEQ approaches under the same time limit.
Complete list of metadata
Contributor : CCSD Connect in order to contact the contributor
Submitted on : Thursday, March 3, 2022 - 10:53:26 AM
Last modification on : Monday, July 4, 2022 - 9:16:56 AM
Long-term archiving on: : Saturday, June 4, 2022 - 6:53:48 PM


Files produced by the author(s)


  • HAL Id : hal-03595429, version 1


Louis Rivière, Christian Artigues, Hélène Fargier. Two-stage stochastic/robust scheduling using permutable operation groups. 23ème Congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision (ROADEF 2022), Institut National des Sciences Appliquées : INSA Lyon; Université de Lyon, Feb 2022, Villeurbanne - Lyon, France. ⟨hal-03595429⟩



Record views


Files downloads