Back to Search
Start Over
On the minimization of the makespan subject to flowtime optimality.
- Source :
- Operations Research; Jul/Aug93, Vol. 41 Issue 4, p797, 5p
- Publication Year :
- 1993
-
Abstract
- When scheduling n jobs on in 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 in. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 0030364X
- Volume :
- 41
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- Operations Research
- Publication Type :
- Academic Journal
- Accession number :
- 9311301114
- Full Text :
- https://doi.org/10.1287/opre.41.4.797