A Sequencing Problem with Release Dates and Clustered Jobs

This paper considers a one-machine scheduling problem where the objective is to minimize the sum of weighted completion times subject to release dates. A polynomial time algorithm is developed for the case when the jobs are clustered. The jobs in each cluster must be processed sequentially and the clusters are ordered. The insights developed are used in an efficient heuristic for the weighted completion time problem without clusters. Also, a class of release date problems is described for which the heuristic finds an optimal solution.