Branch‐and‐bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates

In this paper, we consider a single‐machine scheduling problem with release dates. The aim is to minimize the total weighted completion time. This problem is known to be strongly NP‐hard. We propose two new lower bounds that can be, respectively, computed in O(n ²) and in $O(n\log n)$ time where n is the number of jobs. We prove a sufficient and necessary condition for local optimality, which can also be considered as a priority rule. We present an efficient heuristic using such a condition. We also propose some dominance properties. A branch‐and‐bound algorithm incorporating the heuristic, the lower bounds and the dominance properties is proposed and tested on a large set of instances.