On the Minimization of the Makespan Subject to Flowtime Optimality

Brian Thomas Eck and Michael Pinedo
Additional contact information
Brian Thomas Eck: Juran Institute, Inc., Wilton, Connecticut
Michael Pinedo: Columbia University, New York, New York

Operations Research, 1993, vol. 41, issue 4, 797-801

Abstract: When scheduling n jobs on m identical machines in parallel, two performance criteria are of particular interest: the makespan (the completion time of the last job) and the flowtime (the sum of the completion times of all n jobs). Whereas minimizing makespan is NP-hard, many schedules minimize flowtime, and they are easy to characterize. This paper considers the problem of minimizing the makespan among flowtime-optimal schedules. Heuristics have appeared in the literature that result in flowtime-optimal schedules with makespans which are always less than or equal to 5/4 times the minimum flowtime-optimal makespan. In this note, we present new heuristics for this problem, one of which yields a worst-case bound of 28/27 for the two-machine case. The new heuristics have a running time of O ( n log n ). Extensions are discussed for general m .

Keywords: production/scheduling; sequencing; deterministic; worst-case analysis of parallel machines scheduling problem; programming; fractional worst-case analysis of parallel machines scheduling problem (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.4.797 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:41:y:1993:i:4:p:797-801

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().