Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs

This paper addresses a class of single-machine scheduling problems with a common due-date for all jobs, and general earliness and tardiness costs. The authors show that a class of simple, polynomial, ‘greedy-type’ heuristics can be used to generate close-to-optimal schedules. An extension numerical study exhibits small optimality gaps. For convex cost structures, the authors establish that the worst-case optimality gap is bounded by e’-ⁱ∼0.36, if the due-date is non-restrictive.