ON THE MINIMIZATION OF THE MAKESPAN SUBJECT TO FLOWTIME OPTIMALITY
成果类型：
Note
署名作者：
ECK, BT; PINEDO, M
署名单位：
Columbia University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.41.4.797
发表日期：
1993
页码：
797-801
关键词：
摘要：
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 0(n log n). Extensions are discussed for general m.