Two-machine flowshop scheduling with a secondary criterion

Two-machine flowshop scheduling with a secondary criterion

0.00 Avg rating0 Votes
Article ID: iaor20031850
Country: United Kingdom
Volume: 30
Issue: 4
Start Page Number: 505
End Page Number: 526
Publication Date: Apr 2003
Journal: Computers and Operations Research
Authors: , ,
Keywords: heuristics, programming: branch and bound
Abstract:

This paper develops mathematical programming formulations, a branch-and-bound algorithm, and a heuristic algorithm for solving the two-machine flowshop scheduling problem with the objective of minimizing total completion time, subject to the constraint that the makespan is minimum. The proposed branch-and-bound algorithm uses several lower bounding schemes, which are based on problem relaxations. Several dominance conditions are used in the algorithm to limit the size of the search tree. Results of extensive computational tests show that the proposed branch-and-bound algorithm is effective in solving problems with up to 35 jobs. For problems containing larger number of jobs, the proposed heuristic algorithm, which is also used as an upper bound in the proposed branch-and-bound algorithm, is quite effective in finding an optimal or near-optimal schedule.

Reviews

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