Polytope Scheduling with Groups: Unified Models and Optimal Guarantees

Alexander Lindermayr, Zhenwei Liu, Nicole Megow

Abstract: We propose new abstract and unified perspectives on a range of scheduling and graph coloring problems with general min-sum objectives. Specifically, we consider various problems where the objective function is the weighted sum of completion times over groups of entities (jobs, vertices, or edges), thereby generalizing two important objectives in scheduling: makespan and the sum of weighted completion times. As one of our main results, we present a best-possible $\mathcal O(\log g)$-competitive algorithm in the non-clairvoyant online setting, where $g$ denotes the size of the largest group. This is the first non-trivial competitive bound for several problems with group completion time objective, and it is an exponential improvement over previous results for non-clairvoyant coflow scheduling. For offline scheduling, we provide elegant yet powerful meta-frameworks that, in a unifying way, yield new or stronger approximation algorithms for our new abstract problems as well as for previously well-studied special cases.

Introduction

In classical scheduling theory, objectives typically focus on minimizing either the makespan (the time the last job finishes) or the sum of weighted completion times (the average time jobs finish). However, many real-world systems involve groups of jobs that are interdependent. For instance, in coflow scheduling within data centers, a data transfer is only useful once all its constituent packets have arrived. Similarly, in graph coloring problems like sum multicoloring, a vertex is considered "processed" only after all its required colors are assigned.

This paper addresses the challenge of minimizing the weighted sum of group completion times, where a group is complete only when its final constituent job finishes. Historically, these problems were studied in isolation. This work unifies them under a single abstract framework called Polytope Scheduling with Groups (PSP-G) and provides optimal or near-optimal guarantees for both online non-clairvoyant and offline settings.

The PSP-G Framework

The authors introduce two primary models to capture resource constraints geometrically:

  1. PSP-G (Preemptive): For tasks that can be paused and resumed.
  2. DPSP-G (Discrete): For non-preemptive tasks.

Instead of modeling specific machine speeds or network topologies, the models abstract all resource constraints into a downward-closed geometric polytope. This abstraction allows the development of algorithms that are independent of specific hardware details, making them applicable to a wide range of problems including machine scheduling, data migration, and graph coloring.

Online Non-Clairvoyant Scheduling

A significant contribution of this work is the treatment of the non-clairvoyant online setting, where the scheduler does not know the processing requirements of jobs until they complete.

The authors adapt the Proportional Fairness (PF) allocation rule, traditionally used for individual jobs, to the group context. The key insight is a virtual weight system: each group dynamically distributes its weight equally among its currently unfinished jobs. This strategy naturally prioritizes "stragglers"—the jobs holding up the completion of the entire group.

Through this approach, the authors achieve an $\mathcal{O}(\log g)$-competitive ratio, where $g$ is the maximum group size. This represents an exponential improvement over the previous $\mathcal{O}(g)$ bounds for coflow scheduling and is proven to be theoretically optimal via a matching $\Omega(\log g)$ lower bound.

Offline Approximation Results

For the offline setting, where all job information is known in advance, the paper provides a meta-framework that yields improved approximation ratios for several classic problems.

Comparison of known and new bounds for various scheduling problems.

As shown in the table above, the new framework achieves significant improvements over existing literature:

  • An improvement from 13.5 to 10.874 for related machines ($Q|r_j|\sum w_S C_S$).
  • An improvement from 11.273 to 10.874 for non-preemptive sum multicoloring on interval graphs.
  • A reduction from 10.874 to 5.437 for perfect graphs.
  • A $(2+\epsilon)$-approximation for offline preemptive PSP-G, which is optimal under the Unique Games Conjecture.

Conclusion

By shifting the focus from specific scheduling environments to abstract polytopes, this research provides a powerful unified theory for group-based scheduling. The introduction of virtual weights for non-clairvoyant settings and the interval-indexed LP meta-framework for offline settings set new benchmarks in algorithmic performance. Future work remains in decoupling the discrete offline framework from problem-specific makespan subroutines and further refining approximation ratios for non-grouped special cases.

Summary updated

Abstract

We propose new abstract and unified perspectives on a range of scheduling and graph coloring problems with general min-sum objectives. Specifically, we consider various problems where the objective function is the weighted sum of completion times over groups of entities (jobs, vertices, or edges), thereby generalizing two important objectives in scheduling: makespan and the sum of weighted completion times. As one of our main results, we present a best-possible $\mathcal O(\log g)$-competitive algorithm in the non-clairvoyant online setting, where $g$ denotes the size of the largest group. This is the first non-trivial competitive bound for several problems with group completion time objective, and it is an exponential improvement over previous results for non-clairvoyant coflow scheduling. For offline scheduling, we provide elegant yet powerful meta-frameworks that, in a unifying way, yield new or stronger approximation algorithms for our new abstract problems as well as for previously well-studied special cases.
BibTeX
@misc{lindermayr2025polytope,
  author = {Alexander Lindermayr and Zhenwei Liu and Nicole Megow},
  title = {{Polytope Scheduling with Groups: Unified Models and Optimal Guarantees}},
  year = {2025},
  eprint = {2501.17682},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.17682},
}
Figure