An algorithm for single machine sequencing with deadlines to minimize total weighted completion time

Each of n jobs is to be processed without interruption on a single machine. Each job becomes available for processing at time zero, has a deadline by which it must be completed and has a positive weight. The objective is to find a processing order of the jobs which minimizes the sum of weighted completion times. In this paper a branch and bound algorithm for the problem is presented which incorporates lower bounds that are obtained using a new technique called the multiplier adjustment method. Firstly several dominance conditions are derived. Then a heuristic is described and sufficient conditions for its optimality are given. The lower bound is obtained by performing a Lagrangean relaxation of the deadline constraints; the Lagrange multipliers are chosen so that the sequence generated by the heuristic is an optimal solution of the relaxed problem, thus yielding a lower bound. The algorithm is tested on problems with up to fifty jobs.