Abstract
We consider the classic problem of scheduling jobs with precedence constraints on a set of identical machines to minimize the makespan objective function. Understanding the exact approximability of the problem when the number of machines is a constant is a well-known question in scheduling theory. Indeed, an outstanding open problem from the classic book of Garey and Johnson [9] asks whether this problem is NP-hard even in the case of 3 machines and unit-length jobs. In a recent breakthrough, Levey and Rothvoss [24] gave a (1 + ε)-approximation algorithm, which runs in nearly quasi-polynomial time, for the case when job have unit lengths. However, a substantially more difficult case where jobs have arbitrary processing lengths has remained open. We make progress on this more general problem. We show that there exists a (1 + ε)-approximation algorithm (with similar running time as that of [24]) for the nonmigratory setting: when every job has to be scheduled entirely on a single machine, but within a machine the job need not be scheduled during consecutive time steps. Further, we also show that our algorithmic framework generalizes to another classic scenario where, along with the precedence constraints, the jobs also have communication delay constraints. Both of these fundamental problems are highly relevant to the practice of datacenter scheduling.
Introduction
The problem of scheduling jobs with precedence constraints on identical machines to minimize makespan ($C_{max}$) is a cornerstone of combinatorial optimization. Despite its long history, significant gaps remain in our understanding of its approximability, particularly when the number of machines $m$ is a small constant. A long-standing open question in scheduling theory is whether the problem is NP-hard for as few as three machines, even with unit-length jobs.
Recent progress by Levey and Rothvoss introduced a $(1+\epsilon)$-approximation algorithm for unit-length jobs using the Sherali-Adams linear programming (LP) hierarchy. However, real-world applications—such as task scheduling in datacenters—rarely involve unit-length tasks. This paper extends these theoretical breakthroughs to the more complex and realistic setting of arbitrary job lengths and communication delays.
Problem Formulation and Challenges
The research focuses on three primary dimensions of the scheduling problem:
- Arbitrary Job Lengths: Unlike previous models restricted to unit-length tasks, this work addresses jobs with varying processing times, which significantly complicates the recursive partitioning of the schedule.
- Non-Migratory Constraints: In many distributed systems, a job can be preempted (paused and resumed later), but it cannot migrate between machines. Once a job is assigned to a specific machine, all its processing must occur there. This "preemptive but non-migratory" middle ground is mathematically more challenging than the fully preemptive case.
- Communication Delays: In practice, if Job B depends on Job A, and they are executed on different machines, there is a temporal delay associated with data transfer. Accounting for these delays while maintaining a near-optimal makespan is a notoriously difficult approximation task.
Methodology: The Splitting Operation
The authors build upon the Sherali-Adams hierarchy to strengthen standard LP relaxations. The core of their approach is a recursive partitioning of the time horizon into a binary tree of intervals. The primary technical innovation introduced is the "splitting" operation.
To handle arbitrary job lengths without allowing migration, the algorithm must ensure that even if a job's processing is distributed across different recursive time intervals, it remains anchored to a single machine. The splitting operation allows the algorithm to decompose special jobs into chunks across the recursive structure. By conditioning the LP solution on specific events—effectively narrowing the search space—the framework forces these chunks to be scheduled on the same machine, eventually yielding a valid integral schedule.
For "top-level" jobs (those spanning large time intervals), the authors employ a hybrid policy combining Earliest Deadline First (EDF) and Earliest Completion Time (ECT) logic. This ensures that large tasks are efficiently slotted into the gaps created by smaller, "bottom-level" jobs.
Key Results
The paper establishes two major theoretical milestones:
- Theorem 1.1: A $(1+\epsilon)$-approximation algorithm for the preemptive, non-migratory makespan problem ($Pm|prec, pmtn|C_{max}$) that runs in nearly quasi-polynomial time: $n^{(\log n)^{O(m^2/\epsilon^2 \log \log n)}}$.
- Theorem 1.2: A generalization of this framework that accommodates communication delays, provided the delays are relatively small ($O(1)$). This is achieved by incorporating "buffer" slots around jobs to satisfy delay constraints without significantly impacting the total makespan.
These results demonstrate that LP hierarchies are robust enough to handle the complexities of non-migratory scheduling and communication overhead, provided the number of machines $m$ remains constant.
Discussion and Limitations
While these results represent a significant theoretical advance, the paper identifies clear boundaries for the current approach.
First, the authors provide evidence of an integrality gap for the non-preemptive case (where jobs must run to completion without any pausing). This suggests that standard LP hierarchies may be insufficient for non-preemptive scheduling, which likely requires a different mathematical toolkit.
Second, the computational complexity, while quasi-polynomial, remains too high for immediate practical application in real-time production environments. The current value of the algorithm lies in providing a theoretical guarantee that we can approach the optimal solution for small $m$. Future research is needed to bridge the gap between these hierarchy-based theoretical bounds and efficient, non-preemptive scheduling heuristics used in practice.
Summary updated