Equitable Scheduling on a Single Machine

Klaus Heeger, Danny Hermelin, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Dvir ShabtayAAAI 2021 · DOI

Abstract

Traditional single-machine scheduling often prioritizes global efficiency, such as minimizing the total number of late jobs. However, this focus can lead to "starvation," where specific clients are consistently denied service to optimize the overall system performance. This paper introduces the Equitable Scheduling framework, which shifts the focus toward long-term fairness. By requiring that every client meets their deadline in at least $k$ out of $m$ days, the authors reveal a complex computational landscape where previously simple scheduling problems become NP-hard under fairness constraints.

Introduction

In classical scheduling theory, the $1||\sum U_j$ problem—minimizing the number of tardy jobs on a single machine—is a foundational task. While it can be solved efficiently in $O(n \log n)$ time, its solution often lacks equity. In environments where resources are shared over time, such as researchers sharing a high-performance computing cluster, a schedule that consistently penalizes the same individual to maximize total throughput is socially or organizationally undesirable.

This research proposes a multi-day model to address this imbalance. In this framework, $n$ clients each provide one job per day over a period of $m$ days. Each job has a specific processing time and deadline. The objective is to ensure that every client is "satisfied" (their job is completed by its deadline) for at least $k$ days. This $k$ value serves as the "equity parameter," guaranteeing a minimum level of service for all participants.

Problem Variants and Methodology

The authors categorize the Equitable Scheduling problem into several variants based on job characteristics and constraints, applying combinatorial optimization and parameterized complexity to analyze each.

1. Unit Processing Times (ESUP)

When all jobs require exactly one unit of time, the problem remains computationally tractable. The authors demonstrate that ESUP can be reduced to a Bipartite Maximum Matching problem. By representing jobs as one set of nodes and available time slots as another, a matching can be found that satisfies the $k$-day requirement for all clients in $O((n + m) \cdot (nm)^{1.5})$ time.

2. Single Deadline (ESSD)

In the ESSD variant, all jobs on a given day share a common deadline, but processing times vary. This introduces a "knapsack-like" challenge, as the scheduler must decide which subset of jobs can fit within the day's time limit. The authors prove that this variant is NP-hard and W[1]-hard, meaning it is unlikely to be solvable efficiently for a large number of days. However, they show it is Fixed-Parameter Tractable (FPT) when the number of clients $n$ is small, utilizing Integer Linear Programming (ILP) and Lenstra’s theorem.

3. Precedence Constraints (ESPC)

Adding dependencies between jobs (e.g., job A must finish before job B starts) significantly increases the problem's difficulty. Even with simple structures like disjoint paths, the authors show that the problem remains hard, requiring sophisticated ILP techniques to navigate the added constraints.

4. Identical Days and Approximation (ESSD*)

For scenarios where the set of jobs and deadlines is identical every day, the authors developed a $2/3$ approximation algorithm. Based on a "First-Fit-Decreasing" strategy similar to those used in Bin Packing, this algorithm ensures that if a valid schedule exists for $3k$ days, a solution can be found for $2k$ days in $O(n(k + \log n))$ time.

Key Insights: The Price of Fairness

A central finding of the paper is the "Price of Fairness." The transition from minimizing total tardiness (an "easy" polynomial problem) to ensuring a minimum number of successes per client (a "hard" NP-hard problem) highlights how fairness constraints fundamentally change the structure of optimization.

Furthermore, the research indicates that the complexity of equitable scheduling is more sensitive to the number of days ($m$) than the number of clients ($n$). This suggests that the framework is most applicable to stable, small-to-medium groups of users who interact over long durations.

Results and Complexity Summary

Variant Complexity Key Technique
ESUP (Unit Time) Polynomial: $O((n + m) \cdot (nm)^{1.5})$ Bipartite Matching
ESSD (Single Deadline) NP-hard / W[1]-hard ILP / Lenstra's Theorem
ESPC (Precedence) NP-hard Parameterized Complexity
ESSD* (Identical Days) 2/3 Approximation First-Fit-Decreasing

Conclusion and Future Directions

While the paper provides a robust theoretical foundation for equitable scheduling, it also identifies practical hurdles. The FPT algorithms, while theoretically efficient, involve a double-exponential dependence on the number of clients, which may limit their use in very large systems.

Future work should focus on developing more practical combinatorial algorithms for the Single Deadline case and exploring whether these fairness guarantees can be extended to more complex environments, such as parallel machine scheduling or flow shops. Additionally, empirical testing on real-world resource allocation data is needed to determine if the theoretical worst-case complexity is frequently encountered in practice.

Summary updated

BibTeX
@inproceedings{heeger2021equitable,
  author = {Klaus Heeger and Danny Hermelin and George B. Mertzios and Hendrik Molter and Rolf Niedermeier and Dvir Shabtay},
  title = {{Equitable Scheduling on a Single Machine}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i13.17404},
}
Figure