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

Boris Detienne 1, 2 Ruslan Sadykov 2 Shunji Tanaka 3
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : 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.
Type de document :
Communication dans un congrès
7th Multidisciplinary International Conference on Scheduling: Theory and Applications, Aug 2015, Prague, Czech Republic. pp.635-637, 2015, Proceedings of the 7th Multidisciplinary International Conference on Scheduling: Theory and Applications
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01248318
Contributeur : Ruslan Sadykov <>
Soumis le : jeudi 24 décembre 2015 - 18:10:55
Dernière modification le : jeudi 11 janvier 2018 - 06:22:12

Fichier

Detienne_etall_MISTA15.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01248318, version 1

Collections

Citation

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, 2015, Proceedings of the 7th Multidisciplinary International Conference on Scheduling: Theory and Applications. 〈hal-01248318〉

Partager

Métriques

Consultations de la notice

253

Téléchargements de fichiers

124