Constraint programming for the robust two-machine flow-shop scheduling problem with budgeted uncertainty - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

Constraint programming for the robust two-machine flow-shop scheduling problem with budgeted uncertainty

Résumé

This paper addresses the robust two-machine permutation flow-shop scheduling problem considering non-deterministic operation processing times associated with an uncertainty budget. The objective is to minimize the makespan of the schedule. Exact solution methods incorporated within the framework of a twostage robust optimization are proposed to solve the problem. We first prove that under particular conditions the robust two-machine permutation flow-shop scheduling problem can be solved in polynomial time by the well-known Johnson's algorithm usually dedicated to the deterministic version. Then we tackle the general problem, for which we propose a column and constraint generation algorithm. We compare two versions of the algorithm. In the first version, a mixed-integer linear programming formulation is used for the master problem. In the second version, we use a constraint programming model for the master problem. To the best of our knowledge, the use of constraint programming for a master problem in a two-stage robust optimization problem is innovative. The experimental results show the very good performance of the method based on the constraint programming formulation. We also notice that Johnson's algorithm is surprisingly efficient for the robust version of the general problem.
Fichier principal
Vignette du fichier
CPAIOR_2023-Juvin_et_al.pdf (425.82 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03963365 , version 1 (30-01-2023)

Identifiants

  • HAL Id : hal-03963365 , version 1

Citer

Carla Juvin, Laurent Houssin, Pierre Lopez. Constraint programming for the robust two-machine flow-shop scheduling problem with budgeted uncertainty. 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), May 2023, Nice, France. pp.354-359. ⟨hal-03963365⟩
58 Consultations
42 Téléchargements

Partager

Gmail Facebook X LinkedIn More