Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

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.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal-enac.archives-ouvertes.fr/hal-01856687
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : mardi 26 février 2019 - 09:59:07
Dernière modification le : lundi 4 juillet 2022 - 08:38:48
Archivage à long terme le : : lundi 27 mai 2019 - 13:30:41

Fichier

branch-bound-procedure.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

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⟩

Partager

Métriques

Consultations de la notice

122

Téléchargements de fichiers

321