GREEDY HEURISTICS FOR SINGLE-MACHINE SCHEDULING PROBLEMS WITH GENERALEARLINESS AND TARDINESS COSTS

Authors
FEDERGRUEN A MOSHEIOV G
Citation
A. Federgruen et G. Mosheiov, GREEDY HEURISTICS FOR SINGLE-MACHINE SCHEDULING PROBLEMS WITH GENERALEARLINESS AND TARDINESS COSTS, Operations research letters, 16(4), 1994, pp. 199-208
Citations number
19
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research letters → ACNP
ISSN journal
01676377
Volume
16
Issue
4
Year of publication
1994
Pages
199 - 208
Database
ISI
SICI code
0167-6377(1994)16:4<199:GHFSSP>2.0.ZU;2-P
Abstract
This paper addresses a class of single-machine scheduling problems wit h a common due-date for all jobs, and general earliness and tardiness costs. We show that a class of simple, polynomial, ''greedy-type'' heu ristics can be used to generate close-to-optimal schedules. An extensi ve numerical study exhibits small optimality gaps. For convex cost str uctures, we establish that the worst-case optimality gap is bounded by e(-i) similar to 0.36, if the due-date is non-restrictive.