Analysis of a linearization heuristic for single-machine scheduling to maximize profit

We consider the problem of schedulingn jobs without preemption on a single machine to maximize total profit, where profit is given by a nonincreasing, concave separable function of job starting times. A heuristic is given in which jobs are sequenced optimally relative to a specific linear approximation of the profit, function. This heuristic always obtains at least 2/3 of the optimal profit, and examples exist where the heuristic obtains only 2/3 of the optimal profit. A large class of alternative linearizations is considrred and shown to give arbitrarily bad results. Work supported in part by NSF Grant ECS 82-05438 to the University of Pennsylvania and ONR Contract N00014-81-C-0302.