Error Bound of a Heuristic for the Common Due Date Scheduling Problem

In this paper, a simple heuristic for the n-job, one-machine nonpreemptive scheduling problem of minimizing the sum of absolute deviations of job completion times about a common due date is proposed. The heuristic, which has a complexity of O(n log n), is shown to have a tight relative worst case error bound of 0.5. A practical and systematic guideline for determining the posterior performance of the heuristic is also provided. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.