The two-machine flowshop total completion time problem: Branch-and-bound algorithms based on network-flow formulation

•We study the two-machine flowshop problem with sequence-independent setup times to minimize total completion time.•Strong Lagrangian bounds are proposed based on large scale network flow formulations.•To cope with their size, filtering procedures are developed.•Numerical experiments assess the effi...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2016-08, Vol.252 (3), p.750-760
Main Authors: Detienne, Boris, Sadykov, Ruslan, Tanaka, Shunji
Format: Article
Language:English
Subjects:
Algorithms
Branch & bound algorithms
Branch-and-bound
Completion time
Computer Science
Filtering
Filtration
Flowshop
Formulations
Job shops
Lagrange multiplier
Lagrangian relaxation
Network flow problem
Operational research
Operations Research
Optimization
Optimization algorithms
Production management
Scheduling
Setup times
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:•We study the two-machine flowshop problem with sequence-independent setup times to minimize total completion time.•Strong Lagrangian bounds are proposed based on large scale network flow formulations.•To cope with their size, filtering procedures are developed.•Numerical experiments assess the efficiency of branch-and-bound algorithms. 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-job instances of our testbed with setup times and all 140-job instances without setup times, thus significantly outperforming the best algorithms in the literature.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2016.02.003