Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups

Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups

0.00 Avg rating0 Votes
Article ID: iaor19991743
Country: United Kingdom
Volume: 25
Issue: 5
Start Page Number: 351
End Page Number: 366
Publication Date: May 1998
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: travelling salesman
Abstract:

This paper presents a branch-and-cut (B&C) algorithm for the problem of minimizing the makespan associated with scheduling n jobs in an m-machine flowshop with setup times (SDST flowshop). Two different mathematical formulations are considered. Model A is based on a traveling salesman problem-like formulation. Model B uses fewer binary variables and constraints, but is less structured than model A. A number of valid inequalities, including facet-inducing inequalities, for these two different formulations are evaluated. It was found that the B&C approach outperforms conventional branch and bound. With respect to computational effort, model B proved superior.

Reviews

Required fields are marked *. Your email address will not be published.