Abstract
In the problem of online machine minimization, jobs with release times, deadlines, and processing requirements arrive dynamically, and the objective is to minimize the number of machines required to complete all jobs by their deadlines. For nearly two decades, the best-known competitive ratios for this problem were tied to the ratio of maximum to minimum job processing times ($p_{max}/p_{min}$). This paper presents a breakthrough $O(m^2 \log m)$-competitive preemptive algorithm, where $m$ is the optimal number of machines. This result provides the first competitive ratio independent of job processing parameters, establishing that the complexity of the problem is fundamentally governed by the optimal machine count rather than the temporal scale of the tasks.
1. Introduction
Online machine minimization is a core problem in real-time scheduling and cloud resource management. A scheduler must allocate resources to jobs as they arrive without knowledge of future requests. Each job $j$ is characterized by a release time $r_j$, a processing time $p_j$, and a deadline $d_j$. The goal is to find a feasible schedule that minimizes the maximum number of machines used at any point in time.
Historically, the performance of online algorithms for this task was bounded by $O(\log(p_{max}/p_{min}))$. This logarithmic dependence on the range of processing times meant that in environments with highly heterogeneous job lengths—such as a data center handling both microservices and long-running batch jobs—the theoretical performance guarantees were quite poor. This paper overcomes this limitation by providing a bound that depends solely on $m$, the number of machines used by an optimal offline scheduler.
2. Algorithmic Framework
The authors develop their $O(m^2 \log m)$ result through a multi-stage reduction and a series of structural insights into job configurations.
2.1 Reduction to Semi-Online
The algorithm first addresses the "semi-online" case, where the optimal number of machines $m$ is known in advance. The authors prove that any $\alpha$-competitive semi-online algorithm can be transformed into a $4\alpha$-competitive fully online algorithm using a standard doubling strategy. This allows the core analysis to focus on achieving a bound relative to a fixed $m$.
2.2 Job Categorization: Loose vs. Tight
Jobs are categorized based on their "laxity" or "slack"—the difference between the available time window ($d_j - r_j$) and the required processing time ($p_j$).
- Loose Jobs: Jobs with significant laxity are handled using the Earliest Deadline First (EDF) strategy, which is known to be efficient for under-constrained systems.
- Tight Jobs: The difficulty lies in tight jobs, where the processing time is a large fraction of the available window. The paper's primary contribution is a strategy for these high-pressure tasks.
2.3 Structural Cases: Agreeable and Laminar Instances
To solve the general case, the authors first analyze two restricted job structures:
- Agreeable Instances: In these sets, for any two jobs $i$ and $j$, if $r_i < r_j$, then $d_i \le d_j$. The authors introduce a "MediumFit" strategy that schedules jobs in the middle of their available windows, achieving $O(1)$-competitiveness.
- Laminar Instances: Here, job windows are either nested or disjoint. The authors utilize a balancing scheme that partitions machine capacity into "bins" to prevent nested jobs from exhausting resources needed for shorter, more urgent tasks. This yields an $O(\log m)$ competitive ratio.
3. Key Insights
3.1 Independence from Job Parameters
The most significant theoretical insight is that the "tightness" of a scheduling instance is a function of the number of machines $m$, not the ratio of job lengths. By focusing on the density of jobs over specific intervals, the algorithm avoids the $O(\log(p_{max}/p_{min}))$ bottleneck.
3.2 Non-Migratory Assignment
Surprisingly, while the problem allows for preemption (interrupting a job and resuming it later), the proposed algorithm is non-migratory. Once a job is assigned to a specific machine or group of machines upon arrival, it is never moved to a different machine. This property is highly desirable in practical systems where moving a job's state between physical nodes incurs significant overhead.
3.3 Capacity Binning
For complex nested (laminar) structures, the authors demonstrate that greedy assignment is insufficient. By treating machine laxity as a resource to be balanced across discrete bins, the algorithm prevents "clogging"—a state where a machine is technically free but cannot accept a new job without violating a future deadline.
4. Results and Conclusion
The paper establishes the following competitive ratios:
- General Case: $O(m^2 \log m)$
- Laminar Instances: $O(\log m)$
- Agreeable Instances: $O(1)$
Notably, for agreeable instances, the algorithm produces a non-preemptive schedule. This is a significant result given that the general lower bound for non-preemptive online scheduling is $n$ (the number of jobs).
While the $O(m^2 \log m)$ bound is a landmark improvement, a gap remains between this result and the known lower bound of $1.25$. Future work may focus on refining the analysis to reduce the $m^2$ factor to $O(m)$ or $O(\log m)$, potentially bringing the upper and lower bounds closer to convergence.
Summary updated