|
 ABSTRACT
(MATH) We present a new average case analysis for the problem of scheduling n jobs on $m$ machines so that the sum of job completion times is minimized. Our analysis transfers the concept of competitive analysis --- which is a typical worst case notion --- to the average case. We show that the classic SEPT scheduling strategy with &OHgr;(n) worst case competitive ratio achieves ${\cal O}(1)$ on the average. Moreover, bounds on the probability distribution of the competitive ratio are derived which provide an in-depth understanding of the stochastic version of the min sum scheduling problem.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
E. G. Coffmann, Jr. and E. N. Gilbert. Expected relative performance of list scheduling rules. Oper. Res., 33:548--561, 1985.
|
| |
3
|
E. G. Coffmann, Jr., K. Sao, M. Hofri, and A. C. Yao. A stochastic model of bin--packing. Inf. and Cont., 44:105--115, 1980.
|
| |
4
|
W. Feller. An Introduction to Probability Theory and its Applications, volume I. John Wiley & Sons, New York, 1957.
|
| |
5
|
K. D. Glazebrook. Scheduling tasks with exponential service times on parallel machines. Journal of Applied Probability, 16:685--689, 1979.
|
| |
6
|
R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnoy~Kan. Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete (MATH)ematics, 5:287--326, 1979.
|
| |
7
|
T. Kämpe. On the optimality of static priority policies in stochastic scheduling on parallel machines. Journal of Applied Probability, 24:430--448, 1987.
|
| |
8
|
N. Karmakar. Probabilistic analysis of some bin--packing algorithms. In Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pages 107--111, 1982.
|
| |
9
|
Z. Liu and E. Sanlaville. Stochastic scheduling with variable profile and precedence constraints. Technical Report RR-1525, Inria, Institut National de Recherche en Informatique et en Automatique, 1997.
|
| |
10
|
R. McNaughton. Scheduling with deadlines and loss functions. Management Science, 6:1--12, 1959.
|
| |
11
|
R. H. Möhring and F. J. Radermacher. Introduction to stochastic scheduling problems. In Contributions to operations research, volume 240 of Lect. Notes Econ. (MATH). Syst., pages 72--130, Oberwolfach/Ger., 1985.
|
| |
12
|
R. H. Möhring, F. J. Radermacher, and G. Weiss. Stochastic scheduling problems I: General strategies. Z. Oper. Res., Ser. A. 28:193--260, 1984.
|
| |
13
|
R. H. Möhring, F. J. Radermacher, and G. Weiss. Stochastic scheduling problems II: General strategies. Z. Oper. Res., Ser. A. 29:65--104, 1984.
|
 |
14
|
|
| |
15
|
|
| |
16
|
M. H. Rothkopf. Scheduling with random service times. Management Science, 12:703--713, 1966.
|
| |
17
|
W. E. Smith. Various optimizers for single--stage production. Naval Research and Logistics Quaterly, 3:59--66, 1956.
|
| |
18
|
R. R. Weber, P. Varaiya, and J. Walrand. Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime. Journal of Applied Probability, 23:841--847, 1986.
|
| |
19
|
G. Weiss and M. Pinedo. Scheduling tasks with exponential service times on non--identical processors to minimize various cost functions. Journal of Applied Probability, 17:187--202, 1980.
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
F.2