SCHEDULING WITH RELEASE DATES ON A SINGLE-MACHINE TO MINIMIZE TOTAL WEIGHTED COMPLETION-TIME

This paper considers the problem of scheduling jobs with release dates on a single machine to minimize the total weighted completion time. A branch and bound algorithm is proposed which incorporates three special features that contribute to its efficiency. Firstly, quickly computed lower bounds are obtained using a procedure which is based on job splitting. The job splitting methodology is shown to be applicable to a range of total weighted completion time scheduling problems. Secondly, the branching rule includes a release date adjustment mechanism which increases release dates at certain nodes of the tree with a view to tightening lower bounds. Thirdly, the branch and bound algorithm includes a new dominance rule for eliminating nodes of the search tree. Computational experience on problems with up to 50 jobs indicates that the proposed algorithm is superior to other known algorithms.