Introduction
In modern large-scale computing environments, such as those utilizing MapReduce or Spark, jobs are rarely monolithic tasks. Instead, they are composed of complex structures involving multiple operations. Optimizing "flow-time"—the total duration a job spends in the system from arrival to completion—is critical for maintaining a high-quality user experience and efficient resource utilization. This paper investigates flow-time optimization for two sophisticated scheduling models: Concurrent Open-Shop Scheduling (COSSP) and Precedence Constrained Scheduling (PCSP).
Historically, scheduling research has focused on minimizing makespan (the completion time of the last job). However, flow-time optimization is significantly more challenging due to its sensitivity to individual job wait times. This work provides the first near-optimal approximation algorithms for these problems while establishing theoretical bounds on their complexity.
Geometric Analysis for COSSP
In the Concurrent Open-Shop (COSSP) model, a job consists of multiple operations that can be processed simultaneously across different machines. To address this, the authors translate the scheduling problem into a geometric framework known as Parallel Capacitated Rectangle Covering (PR2C).
By representing jobs as points in a multi-dimensional space and scheduling decisions as rectangles, the authors utilize "union complexity" analysis to bound approximation errors. This approach distinguishes between "heavy" jobs (high demand) and "light" jobs (low demand), applying tailored rounding strategies to each. The resulting polynomial-time algorithm achieves an $O(\log(m \log P))$ approximation, where $m$ is the number of machines and $P$ is the ratio of maximum to minimum processing times. This represents a major breakthrough for a problem that remained open for years.
Precedence Constraints and Speed Augmentation
Precedence Constrained Scheduling (PCSP) involves tasks with strict dependencies, often modeled as Directed Acyclic Graphs (DAGs). The authors demonstrate that flow-time optimization for PCSP is inherently harder than for COSSP or makespan-based models.
To circumvent the theoretical impossibility of achieving a good approximation in standard settings, the paper employs speed augmentation. This technique provides the algorithm's machines with a constant factor more speed ($O(1)$-speed) than the optimal baseline. Using a two-step approach—solving a time-indexed linear program (LP) for a migratory schedule and then rounding it into a non-migratory one—the authors achieve the first $O(1)$-approximation for the sum of general delay costs in precedence-constrained environments. This justifies speed augmentation as a necessary tool for practical scheduling in complex systems.
Complexity and Hardness Proofs
The paper provides rigorous justification for the use of speed augmentation. Through a reduction from the Densest-k-Subgraph problem, the authors prove that for a single machine, no polynomial-time algorithm can achieve an approximation factor better than $n^{\epsilon}$ for PCSP without extra speed (assuming the Exponential Time Hypothesis). This highlights a stark contrast in scheduling theory: while makespan often allows for constant-factor approximations, flow-time for precedence-constrained jobs is super-polynomially hard.
Conclusion and Future Work
This research bridges a significant gap between theoretical scheduling and the practical needs of modern data centers. By introducing geometric mapping and validating speed augmentation as a necessary tool, the authors provide a robust framework for handling complex job structures.
Future research directions include:
- Non-Concurrent Open-Shop: Adapting these techniques to models where a job's operations must be processed sequentially.
- Coflow Scheduling: Developing non-trivial approximations for the broader coflow problem in networking.
- Refining PCSP: Identifying specific job structures where approximations might be possible without speed augmentation.
Summary updated