On a dominance test for the single machine scheduling problem with release dates to minimize total flow time

The dominance test is a bounding operation in branch-and-bound algorithms, where each subproblem is examined whether it can be terminated or not by comparing, implicitly or explicitly, with another subproblem. For a single machine scheduling problem with release dates to minimize total flow time, Chu proposed a branch-and-bound algorithm with a dominance test based on already known and new dominance properties and reported that the dominance test works successfully to solve problem instances exactly with up to 100 jobs. On the other hand, a naive combination of these dominance properties may delete all of the optimal solutions. The purpose of this paper is to point out such a pitfall and then propose a way to avoid it. Furthermore, new dominance properties based on the property developed by Chu are proposed. Computational experiments are performed to see how often the branch-and-bound algorithm with a naive dominance test fails and to show an effectiveness of our branch-and-bound algorithm.