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:
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: