Affordable Access

Publisher Website

Scheduling with release dates on a single machine to minimize total weighted completion time

Authors
Journal
Discrete Applied Mathematics
0166-218X
Publisher
Elsevier
Publication Date
Volume
36
Issue
3
Identifiers
DOI: 10.1016/0166-218x(92)90255-9
Disciplines
  • Computer Science

Abstract

Abstract 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.

There are no comments yet on this publication. Be the first to share your thoughts.