Unifying Scheduling Algorithms for Group Completion Time

Alexander Lindermayr, Zhenwei Liu, Nicole Megow

Abstract

We propose new abstract problems that unify a collection of scheduling and graph coloring problems with general min-sum objectives. Specifically, we consider the weighted sum of completion times over groups of entities (jobs, vertices, or edges), which generalizes two important objectives in scheduling: makespan and sum of weighted completion times. We study these problems in both online and offline settings. In the non-clairvoyant online setting, we give a novel $O(\log g)$-competitive algorithm, where $g$ is the size of the largest group. This is the first non-trivial competitive bound for many problems with group completion time objective, and it is an exponential improvement over previous results for non-clairvoyant coflow scheduling. Notably, this bound is asymptotically best-possible. For offline scheduling, we provide powerful meta-frameworks that lead to new or stronger approximation algorithms for our new abstract problems and for previously well-studied special cases. In particular, we improve the approximation ratio from $13.5$ to $10.874$ for non-preemptive related machine scheduling and from $4+\varepsilon$ to $2+\varepsilon$ for preemptive unrelated machine scheduling (MOR 2012), and we improve the approximation ratio for sum coloring problems from $10.874$ to $5.437$ for perfect graphs and from $11.273$ to $10.874$ for interval graphs (TALG 2008).

Introduction

In traditional scheduling theory, objectives typically focus on either the makespan (the time the last job finishes) or the sum of weighted completion times (the average time jobs spend in the system). However, many modern computational environments, such as data centers and distributed systems, require a focus on groups of tasks.

For instance, in "coflow scheduling," a distributed computing stage may involve multiple data transfers. The entire stage is only considered complete when the slowest transfer in its group finishes. Similar group-based completion requirements arise in graph coloring (where a vertex is "done" only when all its incident edges are colored) and data migration. Optimizing for group objectives is significantly more complex than for individual ones. Historically, algorithmic results for these problems were fragmented across sub-fields, and online guarantees were often poor. For example, previous online coflow algorithms had competitive ratios that grew linearly with the size of the largest group.

Methodology: The Polytope Scheduling Framework

The core contribution of this work is the abstraction of these diverse problems into a unified framework called Polytope Scheduling with Groups (PSP-G). This abstraction allows for the development of general algorithms that apply to a wide range of specific scheduling and coloring problems.

1. The Polytope Abstraction

Rather than modeling specific machine configurations, the "processing power" available at any given time is modeled as a packing polytope. Any valid schedule is represented as a sequence of rate vectors chosen from this polytope.

2. Online (Non-Clairvoyant) Setting

In the non-clairvoyant setting, the algorithm lacks prior knowledge of job durations. The authors adapt the Proportional Fairness (PF) algorithm, a classic resource allocation rule, by introducing "virtual weights". Each group distributes its total weight evenly among its currently unfinished jobs. This approach is analyzed using a novel "factor-revealing" Linear Program (LP), leading to a best-possible $O(\log g)$-competitive ratio.

3. Offline (Discrete) Setting

For non-preemptive problems, the authors propose a three-step meta-framework:

  1. Solve a time-indexed LP relaxation of the problem.
  2. Partition jobs into "batches" using randomized shifting based on the LP solution.
  3. Schedule these batches sequentially using a problem-specific makespan minimization subroutine.

Key Results

The PSP-G framework yields significant improvements over existing literature across multiple domains, including machine scheduling, graph coloring, and coflow scheduling.

Table 1: Comparison of new results against previous known bounds.

Key highlights include:

  • Online Exponential Speedup: For non-clairvoyant coflow scheduling, the competitive ratio is improved from $O(g)$ to $O(\log g)$, where $g$ is the maximum group size. This bound is proven to be asymptotically optimal.
  • Machine Scheduling Improvements: The approximation ratio for non-preemptive related machine scheduling ($Q | r_j | \sum w_S C_S$) is reduced from 13.5 to 10.874. For preemptive unrelated machine scheduling ($R | r_j, pmtn | \sum w_S C_S$), the bound is improved from $4 + \varepsilon$ to $2 + \varepsilon$, reaching near-optimality.
  • Graph Coloring Progress: For sum multicoloring on perfect graphs, the previous best approximation ratio is halved from 10.874 to 5.437. On interval graphs, it is improved from 11.273 to 10.874.

Conclusion and Future Work

By proving results for the abstract PSP-G model, the authors provide a unified set of tools for problems ranging from data center networking to theoretical graph coloring. The discrete framework demonstrates that the difficulty of the "weighted sum of group completion times" objective can be reduced to makespan minimization with only a constant-factor overhead.

Future research directions include:

  • Reducing Subroutine Dependence: Exploring whether the discrete framework can be made truly "black-box," removing the dependence on specific makespan-minimization subroutines.
  • Refining Preemptive Bounds: Investigating if the $(2 + \varepsilon)$ bound for offline preemptive scheduling can be further improved.
  • Expanding the Framework: Adapting the PSP-G model to capture additional constraints, such as "consecutive colorings" in multicoloring problems.

Summary updated

Abstract

We propose new abstract problems that unify a collection of scheduling and graph coloring problems with general min-sum objectives. Specifically, we consider the weighted sum of completion times over groups of entities (jobs, vertices, or edges), which generalizes two important objectives in scheduling: makespan and sum of weighted completion times. We study these problems in both online and offline settings. In the non-clairvoyant online setting, we give a novel $O(\log g)$-competitive algorithm, where $g$ is the size of the largest group. This is the first non-trivial competitive bound for many problems with group completion time objective, and it is an exponential improvement over previous results for non-clairvoyant coflow scheduling. Notably, this bound is asymptotically best-possible. For offline scheduling, we provide powerful meta-frameworks that lead to new or stronger approximation algorithms for our new abstract problems and for previously well-studied special cases. In particular, we improve the approximation ratio from $13.5$ to $10.874$ for non-preemptive related machine scheduling and from $4+\varepsilon$ to $2+\varepsilon$ for preemptive unrelated machine scheduling (MOR 2012), and we improve the approximation ratio for sum coloring problems from $10.874$ to $5.437$ for perfect graphs and from $11.273$ to $10.874$ for interval graphs (TALG 2008).
BibTeX
@misc{lindermayr2025unifying,
  author = {Alexander Lindermayr and Zhenwei Liu and Nicole Megow},
  title = {{Unifying Scheduling Algorithms for Group Completion Time}},
  year = {2025},
  eprint = {2501.17682},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.17682},
}
Figure