Open Research Index

Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard

Benjamin Moseley, Kirk Pruhs, Marc Uetz, Rudy Zhou

arXivarxiv/2601.17425Jan 24, 2026cs.DSscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2601.17425
curl -X POST /api/v1/records/arxiv/2601.17425/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.17425/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'