Approximation Bounds for Weighted Completion Time Scheduling

54 concepts50 papers1 proposal

In modern computing, from data centers to single-processor systems, the fundamental challenge is ordering tasks to minimize delay. The most common metric for this is total weighted completion time ($\sum w_j C_j$), where each job has a weight $w_j$ representing its priority and a completion time $C_j$. While simple in concept, this problem becomes notoriously difficult when machines are "unrelated"—meaning a job's processing time depends entirely on which machine it is assigned to.

Research in this area focuses on finding approximation algorithms: strategies that are mathematically guaranteed to produce a schedule within a specific factor of the theoretical optimum.

Breaking the Unrelated Machine Barrier

For decades, the "gold standard" for minimizing weighted completion time on unrelated machines was a 1.5-approximation ratio. This bound was typically achieved through independent randomized rounding, where fractional assignments from a linear program (LP) are converted into discrete job-to-machine assignments.

The breakthrough beyond this limit came from moving toward more sophisticated rounding techniques. Aravind Srinivasan et al. introduced a bipartite rounding technique in Lift-and-round to improve weighted completion time on unrelated machines that enforced strong negative correlations between job assignments, successfully pushing the ratio to $(3/2 - c)$.

The intuition here is to prevent "collisions" where too many high-weight jobs are assigned to the same machine. By using iterative fair contention resolution, Maryam Shadloo further refined this to a 1.488-approximation. Most recently, Shi Li 0001 et al. achieved a $(1.36 + \epsilon)$ ratio in Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs by relaxing strict correlation requirements, demonstrating that simpler iterative rounding can be more powerful when paired with computational verification.

The Power of Proportionality

A recurring theme in this research is that scheduling becomes significantly more tractable when job weights are proportional to their processing times—a concept known as Uniform Smith Ratios.

When $w_j / p_j$ is constant across all jobs, the "Shortest Processing Time" rule becomes globally effective. Christos Kalaitzis et al. showed in Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios that this specific constraint allows for a 1.21-approximation, far outperforming general models. This principle extends to "rejection costs" in cloud computing; Rémi Bouzel et al. found that if the cost to offload a job is proportional to its size, the problem maps onto packing problems, yielding a $1.25(1+\epsilon)$ ratio in A 1.25(1+ε )-Approximation Algorithm for Scheduling with Rejection Costs Proportional to Processing Times.

From Completion Time to Flow-Time

While completion time measures the moment a job finishes, flow-time ($C_j - r_j$) measures the time a job spends in the system after its arrival ($r_j$). This is a much harder objective because a small delay early on can cascade through the entire schedule.

For unrelated machines, Nikhil Bansal et al. achieved the first poly-logarithmic approximation for total flow-time in Minimizing Flow-Time on Unrelated Machines. They utilized a sparse LP formulation and iterative rounding to manage the complex interactions between arrival times and machine speeds. On a single machine, the challenge was even more fundamental: for years, it was unknown if a constant-factor approximation for weighted flow-time was even possible in polynomial time. Janardhan Kulkarni et al. settled this in A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time, bridging the gap between theoretical possibility and efficient computation.

Handling Complex Constraints

Real-world scheduling often involves more than just machines and jobs. It includes:

  1. Precedence Constraints: Jobs that must finish before others start. Janardhan Kulkarni et al. used the Sherali-Adams LP hierarchy to handle these constraints on a constant number of machines, showing that techniques for simple tasks can scale to complex dependencies.
  2. Non-Renewable Resources: Jobs that consume a limited resource (like a battery or a budget) that arrives at specific times. Kristóf Bérczi et al. developed a Polynomial Time Approximation Scheme (PTAS) for this in Scheduling with non-renewable resources: minimizing the sum of completion times by shifting resource arrival times to powers of two, effectively discretizing the timeline into manageable subproblems.
  3. Non-Clairvoyance: Scheduling when job sizes are unknown. In the context of data center "coflows," Akhil Bhimaraju et al. proved that weight-proportional capacity allocation can still provide a provable $8p$-approximation, where $p$ is the network complexity.

These advancements collectively show that while scheduling problems are often NP-hard, the clever use of LP hierarchies, iterative rounding, and geometric reductions can bring us remarkably close to optimal efficiency.

Key Foundational Work

Scheduling Jobs that Arrive Over Time (Extended Abstract) (1995) — contributed 2 concept elements to this direction.
Approximation schemes for scheduling on parallel machines (1998) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_weighted_completion_time_bounds_01ba0f4b,
  title = {weighted completion time bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/weighted-completion-time-bounds/rdr_01ba0f4b172347d484071c22b4a65ba0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_weighted_completion_time_bounds_01ba0f4b_v1,
  title = {weighted completion time bounds},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/weighted-completion-time-bounds/rdr_01ba0f4b172347d484071c22b4a65ba0/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake