A Branch-and-Bound Procedure for the Robust Cyclic Job Shop Problem - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

A Branch-and-Bound Procedure for the Robust Cyclic Job Shop Problem

(1) , (2) , (3)


This paper deals with the cyclic job shop problem where the task durations are uncertain and belong to a polyhedral uncertainty set. We formulate the cyclic job shop problem as a two-stage robust optimization model. The cycle time and the execution order of tasks executed on the same machines correspond to the here-and-now decisions and have to be decided before the realization of the uncertainty. The starting times of tasks corresponding to the wait-and-see decisions are delayed and can be adjusted after the uncertain parameters are known. In the last decades, different solution approaches have been developed for two-stage robust optimization problems. Among them, the use of affine policies, column generation algorithms, row and row-and-column generation algorithms. In this paper, we propose a Branch-and-Bound algorithm to tackle the robust cyclic job shop problem with cycle time minimization. The algorithm uses, at each node of the search tree, a robust version of the Howard’s algorithm to derive a lower bound on the optimal cycle time. We also develop a heuristic method that permits to compute an initial upper bound for the cycle time. Finally, encouraging preliminary results on numerical experiments performed on randomly generated instances are presented.
Fichier principal
Vignette du fichier
branch-bound-procedure.pdf (328.49 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01856687 , version 1 (26-02-2019)



Idir Hamaz, Laurent Houssin, Sonia Cafieri. A Branch-and-Bound Procedure for the Robust Cyclic Job Shop Problem. ISCO 2018, 5th International Symposium on Combinatorial Optimization, Apr 2018, Marrakech, Morocco. pp.228-240, ⟨10.1007/978-3-319-96151-4_20⟩. ⟨hal-01856687⟩
125 Consultations
326 Téléchargements



Gmail Facebook Twitter LinkedIn More