The Deadline Constrained Weighted Completion Time Problem: Analysis of a Heuristic

A greedy heuristic that schedules jobs on one machine is examined. The problem considered is to minimize the sum of weighted completion times subject to deadline constraints. Both theoretical and empirical evidence are presented to suggest that this method finds solutions that are near optimal. Optimality conditions are developed. Also, an analysis of the relative error is presented. Worst case bounds are found that are based on the problem parameters. In addition, we show that the relative error goes to zero as the problem size goes to infinity.