Stochastic load balancing and related problems
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 579-586
- https://doi.org/10.1109/sffcs.1999.814632
Abstract
We study the problems of makespan minimization (load balancing), knapsack, and bin packing when the jobs have stochastic processing requirements or sizes. If the jobs are all Poisson, we present a two approximation for the first problem using Graham's rule, and observe that polynomial time approximation schemes can be obtained for the last two problems. If the jobs are all exponential, we present polynomial time approximation schemes for all three problems. We also obtain quasi-polynomial time approximation schemes for the last two problems if the jobs are Bernoulli variables.Keywords
This publication has 10 references indexed in Scilit:
- Allocating bandwidth for bursty connectionsPublished by Association for Computing Machinery (ACM) ,1997
- Randomized AlgorithmsPublished by Cambridge University Press (CUP) ,1995
- Turnpike Optimality of Smith's Rule in Parallel Machines Stochastic SchedulingMathematics of Operations Research, 1992
- Approximation results in parallel machnies stochastic schedulingAnnals of Operations Research, 1990
- Scheduling jobs with exponential processing times on parallel machinesJournal of Applied Probability, 1988
- Using dual approximation algorithms for scheduling problems theoretical and practical resultsJournal of the ACM, 1987
- Scheduling jobs by stochastic processing requirements on parallel machines to minimize makespan or flowtimeJournal of Applied Probability, 1982
- Fast Approximation Algorithms for Knapsack ProblemsMathematics of Operations Research, 1979
- Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsJournal of the ACM, 1975
- Bounds for Certain Multiprocessing AnomaliesBell System Technical Journal, 1966