Stochastic load balancing and related problems

摘要: We study the problems of makespan minimization (load balancing), knapsack, and bin packing when jobs have stochastic processing requirements or sizes. If are all Poisson, we present a two approximation for first problem using Graham's rule, observe that polynomial time schemes can be obtained last problems. exponential, three also obtain quasi-polynomial if Bernoulli variables.