The two-machine flowshop total completion time problem: A branch-and-bound based on Network-flow formulation - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

The two-machine flowshop total completion time problem: A branch-and-bound based on Network-flow formulation

Résumé

We consider the flowshop problem on two machines with sequence-independent setup times to minimize total completion time. Large scale network flow formulations of the problem are suggested together with strong Lagrangian bounds based on these formulations. To cope with their size, filtering procedures are developed. To solve the problem to optimality, we embed the Lagrangian bounds into two branch-and- bound algorithms. The best algorithm is able to solve all 100-jobs instances of our testbed with and without setup times, thus significantly outperforming the best algorithms in the literature.
Fichier principal
Vignette du fichier
Detienne_etall_MISTA15.pdf (170.41 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01248318 , version 1 (24-12-2015)

Identifiants

  • HAL Id : hal-01248318 , version 1

Citer

Boris Detienne, Ruslan Sadykov, Shunji Tanaka. The two-machine flowshop total completion time problem: A branch-and-bound based on Network-flow formulation. 7th Multidisciplinary International Conference on Scheduling: Theory and Applications, Aug 2015, Prague, Czech Republic. pp.635-637. ⟨hal-01248318⟩

Collections

CNRS INRIA INRIA2
149 Consultations
106 Téléchargements

Partager

Gmail Facebook X LinkedIn More