A branch‐and‐bound algorithm to minimize total flow time with unequal release dates

Chengbin Chu

Naval Research Logistics (NRL), 1992, vol. 39, issue 6, 859-875

Abstract: This article examines the single‐machine scheduling problem to minimize total flow time with unequal release dates. This problem has been proven to be NP‐hard. We present a necessary and sufficient condition for local optimality which can also be considered as a priority rule. On the basis of this condition, we then define a class of schedules which contains all optimal solutions. We present some efficient heuristic algorithms using the previous condition to build a schedule belonging to this subset. We also prove some new dominance theorems, discuss the results found in the literature for this problem, and propose a branch‐and‐bound algorithm in which the heuristics are used to provide good upper bounds. We compare this new algorithm with existing algorithms found in the literature. Computational results on problems with up to 100 jobs indicate that the proposed branch‐and‐bound algorithm is superior to previously published algorithms. © 1992 John Wiley & Sons. Inc.

Date: 1992
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199210)39:63.0.CO;2-W

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:39:y:1992:i:6:p:859-875

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().