Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard

Benjamin Moseley, Kirk Pruhs, Marc Uetz, Rudy Zhou, [2ex] Carnegie Mellon University, Pittsburgh, PA, USA · 2026

Read Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard by Benjamin Moseley, Kirk Pruhs, Marc Uetz, Rudy Zhou, [2ex] Carnegie Mellon University, Pittsburgh, PA, USA (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-17425.txt.

Introduction

Benjamin Moseley, Kirk Pruhs, Marc Uetz, and Rudy Zhou prove a hardness result for job scheduling. The setting is stochastic jobs on parallel machines. Run times are not fixed; they follow chance laws. The goal is to cut the expected weighted sum of completion times. It is a classic problem with two decades of work on near-best methods.

The authors show the problem is hard in a strong sense. That caps what any algorithm can promise. Hardness proofs save teams from hunting for tools that cannot exist. They steer work toward smart trade-offs and special cases. Plant and cloud planners both face this task. Knowing its true depth shapes what software can claim.

Catalog record

CREATORBenjamin Moseley, Kirk Pruhs, Marc Uetz, Rudy Zhou, [2ex] Carnegie Mellon University, Pittsburgh, PA, USA
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE35 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-17425

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Minimizing Completion Times of Stochastic Jobs on Parallel Machines is Hard Benjamin Moseley, Kirk Pruhs, Marc Uetz, Rudy Zhou, [2ex] Carnegie Mellon University, Pittsburgh, PA, USA Abstract 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 in polynomial time. We address this gap with hardness results that demonstrate the problem’s inherent intractability. For the special case of discrete two-point processing time distributions and unit weights, we prove that deciding whether there exists a scheduling policy with expected cost at most a given threshold is #P-hard. Furthermore, we show that evaluating the expected objective value of the standard (W)SEPT greedy policy is itself #P-hard. These represent the first hardness results for scheduling independent stochastic jobs and min-sum objective that do not merely rely on the intractability of the underlying deterministic counterparts. 1 Introduction This paper addresses a long-standing open question in stochastic scheduling theory: whether the computational complexity of stochastic parallel machine scheduling fundamentally differs from that of its deterministic counterpart, even in the most basic settings. In deterministic scheduling on parallel identical machines, minimizing the total completion time \sum_{j}C_{j} when all jobs have equal weight is solvable in polynomial time by scheduling jobs in shortest processing time (SPT) order [ 3 ] . Here C_{j} is the completion time of job j under a scheduling policy. By contrast, for the stochastic version of the same problem, where processing times are random and revealed only upon completion, the computational complexity of computing an optimal scheduling policy has remained unresolved since the early 1980s. Despite decades of research on stochastic scheduling, computational hardness results were previously known only for more structured problems; discussed in more detail below. This paper provides the first evidence that the classical stochastic parallel machine scheduling for minimizing \mathbb{E}[\sum_{j}C_{j} ] is computationally intractable, thereby separating the stochastic problem from its deterministic counterpart. We consider a standard stochastic scheduling model with m parallel identical machines and n non-preemptive jobs. Each job j must be assigned to a single machine and, once started, runs to completion without interruption. The processing time p_{j} of job j is unknown in advance and is modeled as a nonnegative random variable X_{j} , independently distributed across jobs. Following recent work on approximation algorithms for stochastic scheduling, we focus on a discrete variant of the problem in which each X_{j} has finite support, and in particular we assume that each distribution has support size at most two . Each job j additionally may have a weight w_{j} . Under a scheduling policy, let S_{j} and C_{j} denote the (random) start and completion times of job j , respectively. By definition, \mathbb{E}[C_{j}]=\mathbb{E}[S_{j}]+\mathbb{E}[X_{j}] . The objective is to find, or evaluate, a scheduling policy that minimizes the expected weighted sum of completion times, \mathbb{E}\!\left[\sum\nolimits_{j}w_{j}C_{j}\right]. Optimal scheduling policies for this problem are known only in highly restricted special cases. When all weights are equal and processing times follow exponential distributions, the greedy SEPT (Shortest Expected Processing Time first) policy is optimal [ 32 , 5 ] . More generally, SEPT is still an optimal policy if the processing time distributions are pairwise stochastically comparable [ 31 ] . With exponentially distributed jobs, the optimality of SEPT also extends to weighted jobs whenever the SEPT order is agreeable with the job weights [ 18 ] . Outside of such special settings, however, it is well understood that optimal policies must be adaptive , reacting dynamically to realized processing times [ 29 , 26 , 6 ] . Moreover, the adaptivity gap between non-adaptive and adaptive policies can grow proportionally to the coefficient of variation of the processing time distributions [ 26 , 6 ] . Beginning with [ 22 ] , a substantial literature has developed approximation algorithms for stochastic scheduling, typically based on linear programming relaxations of the optimal adaptive policy [ 22 , 27 , 21 , 26 , 2 , 11 , 12 , 16 ] . Almost all of these approximation guarantees scale with the largest squared coefficient of variation of the random variables X_{j} , defined as {\mathbb{V}\rm ar}[\,X_{j}\,]/\mbox{${\mathbb{E}}[\,X_{j}\,]$}^{2} . For the special case of unit weights, an exception is [ 14 ] , whose performance guarantee instead depends on the number of machines m . More recently, for two-point Bernoulli processing times, sublinear-in- m approximation guarantees have been obtained that do not depend on second moments [ 10 , 1 ] : However, the approximation guarantee in [ 10 ] , while sublinear in m , contains large poly-logarithmic factors in the number of jobs n , and the guarantee in [ 1 ] is \textup{O}(\,\log n\,) , but only quasi-polynomial time. Despite the sophistication of these approximation results, strong lower bounds on the computational complexity of stochastic scheduling have remained largely absent. When job weights are arbitrary, the problem is NP-hard, since it generalizes deterministic scheduling on parallel machines, which is NP-hard [ 8 ] . However, for the unweighted case w_{j}=1 for all jobs j , deterministic scheduling is optimally solvable by SPT [ 3 ] . Quite strikingly, the computational complexity of the corresponding stochastic problem —minimizing \mathbb{E}[\sum_{j}C_{j}] on parallel identical machines— has remained open for over four decades. In particular, it is still open if the stochastic problem can be solved optimally in polynomial time. In summary, the lurking fundamental question is: Is it computationally hard to compute an optimal scheduling policy for minimizing expected total completion time on parallel identical machines? Despite sustained interest in stochastic scheduling since the 1980s, this question has not been resolved. This paper gives a partial answer, testifying the problem being computationally harder than the corresponding deterministic counterpart. 1.1 Results This paper provides the first indication that this stochastic scheduling problem is unlikely to admit a polynomial-time solution, even when all job weights are equal. We show that the decision problem of whether there exists a scheduling policy whose expected cost is at most a given threshold is #P-hard. This hardness result holds even under restricted stochasticity , namely with independent two-point processing time distributions. Beyond computing optimal policies, we also study the complexity of evaluating simple and widely used scheduling policies. Perhaps the most popular such policy is WSEPT (Weighted Shortest Expected Processing Time first), which schedules jobs greedily in non-increasing order of the ratios w_{j}/\mathbb{E}[X_{j}] . WSEPT is optimal on a single machine for both deterministic [ 28 ] and stochastic processing times [ 24 ] . On parallel machines, it remains optimal for exponential distributions when weights are agreeable with expected processing times [ 18 ] . In the case with unit weights, WSEPT reduces to SEPT, which is optimal for exponential distributions [ 32 , 5 ] and more generally for stochastically orderable processing times [ 31 ] . Even beyond these

Read the complete text