Abstract

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

Authors
Awi Federgruen and Gur Mosheiov
Format
Journal Article
Publication Date
Journal
Operations Research Letters

Full Citation

Federgruen, Awi and Gur Mosheiov
. “Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs.”
Operations Research Letters
vol.
16
, (November 01, 1994):
199
-
208
.