Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

https://hal-enac.archives-ouvertes.fr/hal-01856687
Contributor : Laurence Porte <>
Submitted on : Tuesday, February 26, 2019 - 9:59:07 AM
Last modification on : Tuesday, February 11, 2020 - 1:59:37 PM
Document(s) archivé(s) le : Monday, May 27, 2019 - 1:30:41 PM

File

branch-bound-procedure.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

169

Files downloads

251