Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6895635 | European Journal of Operational Research | 2016 | 11 Pages |
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-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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Boris Detienne, Ruslan Sadykov, Shunji Tanaka,