A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times

A branch-and-bound algorithm for three-machine flowshop scheduling problem to minimize total completion time with separate setup times

0.00 Avg rating0 Votes
Article ID: iaor2007149
Country: Netherlands
Volume: 169
Issue: 3
Start Page Number: 767
End Page Number: 780
Publication Date: Mar 2006
Journal: European Journal of Operational Research
Authors: ,
Keywords: programming: branch and bound
Abstract:

In this paper, we address the three-machine flowshop scheduling problem. Setup times are considered separate from processing times, and the objective is to minimize total completion time. We show that the three-site distributed database scheduling problem can be modeled as a three-machine flowshop scheduling problem. A lower bound is developed and a dominance relation is established. Moreover, an upper bound is developed by using a three-phase hybrid heuristic algorithm. Furthermore, a branch-and-bound algorithm, incorporating the developed lower bound, dominance relation, and the upper bound is presented. Computational analysis on randomly generated problems is conducted to evaluate the lower and upper bounds, the dominance relation, and the branch-and-bound algorithm. The analysis shows the efficiency of the upper bound, and, hence, it can be used for larger size problems as a heuristic algorithm.

Reviews

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