{"id":"arxiv/2601.17425","url":"https://arxiv.org/abs/2601.17425","tags":["cs.DS","cs.CC","math.OC"],"score":0,"title":"Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard","domain":"cs.DS","source":"arxiv","authors":["Benjamin Moseley","Kirk Pruhs","Marc Uetz","Rudy Zhou"],"reviews":0,"subject":"cs.DS","summary":"This paper considers the scheduling of stochastic jobs on parallel identical machines to minimize the expected total weighted completion time. While this is a classical problem with a significant body of research on approximation algorithms over the past two decades, constant-factor performance guarantees are currently known only under very restrictive assumptions on the input distributions, even when all job weights are identical. This algorithmic difficulty is striking given the lack of corresponding complexity results: to date, it is conceivable that the problem could be solved optimally…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-24","reactions":{}}