Stochastic Load Balancing on Unrelated Machines: An Effective-Size LP and Its Rounding Give a Constant-Factor Approximation to the Minimum Expected MakespanResearch Paper
Load balancing asks for an assignment of jobs to machines that keeps the largest machine load, the makespan, small. On unrelated machines the processing time of a job may depend arbitrarily on the machine; the deterministic problem has the classical -approximation of Lenstra, Shmoys and Tardos (1990). In many applications (virtual-circuit routing,…