Awi Federgruen

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

Coauthor(s): Gur Mosheiov.

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.

Source: Operations Research Letters
Exact Citation:
Federgruen, Awi, and Gur Mosheiov. "Greedy heuristics for single-machine scheduling problems with general earliness and tardiness costs." Operations Research Letters 16, no. 4 (November 1994): 199-208.
Volume: 16
Number: 4
Pages: 199-208
Date: 11 1994