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

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. The paper presents a necessary and sufficient condition for local optimality which can also be considered as a priority rule. On the basis of this condition, it then defines a class of schedules which contains all optimal solutions. The paper presents some efficient heuristic algorithms using the previous condition to build a schedule belonging to this subset. It also proves 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. The paper compares 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.