TY - GEN

T1 - Minimizing Completion Times for Stochastic Jobs via Batched Free Times

AU - Gupta, Anupam

AU - Moseley, Benjamin

AU - Zhou, Rudy

N1 - Publisher Copyright:
Copyright © 2023 by SIAM.

PY - 2023

Y1 - 2023

N2 - We study the classic problem of minimizing the expected total completion time of jobs on m identical machines in the setting where the sizes of the jobs are stochastic. Specifically, the size of each job is a random variable whose distribution is known to the algorithm, but whose realization is revealed only after the job is scheduled. While minimizing the total completion time is easy in the deterministic setting, the stochastic problem has long been notorious: all known algorithms have approximation ratios that either depend on the variances, or depend linearly on the number of machines. We give an Õ(√m)-approximation for stochastic jobs which have Bernoulli processing times. This is the first approximation for this problem that is both independent of the variance in the job sizes, and is sublinear in the number of machines m. Our algorithm is based on a novel reduction from minimizing the total completion time to a natural makespan-like objective, which we call the weighted free time. We hope this free time objective will be useful in further improvements to this problem, as well as other stochastic scheduling problems.

AB - We study the classic problem of minimizing the expected total completion time of jobs on m identical machines in the setting where the sizes of the jobs are stochastic. Specifically, the size of each job is a random variable whose distribution is known to the algorithm, but whose realization is revealed only after the job is scheduled. While minimizing the total completion time is easy in the deterministic setting, the stochastic problem has long been notorious: all known algorithms have approximation ratios that either depend on the variances, or depend linearly on the number of machines. We give an Õ(√m)-approximation for stochastic jobs which have Bernoulli processing times. This is the first approximation for this problem that is both independent of the variance in the job sizes, and is sublinear in the number of machines m. Our algorithm is based on a novel reduction from minimizing the total completion time to a natural makespan-like objective, which we call the weighted free time. We hope this free time objective will be useful in further improvements to this problem, as well as other stochastic scheduling problems.

UR - http://www.scopus.com/inward/record.url?scp=85170033700&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85170033700&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85170033700

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1905

EP - 1930

BT - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

PB - Association for Computing Machinery

T2 - 34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023

Y2 - 22 January 2023 through 25 January 2023

ER -