An Efficient Branch-And-Bound Algorithm For The Two-Machine Bicriteria Flowshop Scheduling Problem

Soc Manufacturing Engineers
Publication Type:
Journal Article
Journal Of Manufacturing Systems, 2001, 20 (2), pp. 113 - 123
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
2010004138OK.pdf6.89 MB
Adobe PDF
In this study, the two-machine bicriteria flowshop scheduling problem is addressed. The objective is to minimize a weighted sum of total flowtime and makespan. Different branch-and-bound algorithms have already appeared in the literature for this problem. In this study, a more efficient branch-and-bound algorithm is presented. The proposed algorithm and the existing ones are compared on randomly generated problems. The computational analysis on problems up to 20 jobs shows that the proposed branch-andbound algorithm is more efficient than the others, including the best-known algorithm. The upper bound used in the proposed branch-and-bound algorithm, a two-phase hybrid heuristic method, is also shown to be efficient. Its overall average error on the randomly generated problems is 0.000139, that is, almost equal to the optimal solution.
Please use this identifier to cite or link to this item: