A Branch and bound for 1|ri| wiCi, Scheduling Problem

International audienceIn this paper, we consider a single machine scheduling problem with release dates. The objective is to minimize the total completion time. This problem is know to be strongly NP-hard. We propose two new lower bounds that can be computed in O(n 2 ) and in O(n log n) time respectively. We also propose some dominance properties. A branch-and-bound algorithm in which the lower bounds and the dominance properties are incorporated is proposed and tested on a large set of instance