Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models

Janardhan Kulkarni, Shi Li

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).

Geometric mapping of scheduling instances to rectangle covering problems (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

Abstract

Scheduling a set of jobs over a collection of machines is a fundamental problem that needs to be solved millions of times a day in various computing platforms: in operating systems, in large data clusters, and in data centers. Along with makespan, flow-time, which measures the length of time a job spends in a system before it completes, is arguably the most important metric to measure the performance of a scheduling algorithm. In recent years, there has been a remarkable progress in understanding flow-time based objective functions in diverse settings such as unrelated machines scheduling, broadcast scheduling, multi-dimensional scheduling, to name a few. Yet, our understanding of the flow-time objective is limited mostly to the scenarios where jobs have no dependencies. On the other hand, in almost all real world applications, think of MapReduce settings for example, jobs have dependencies that need to be respected while making scheduling decisions. In this paper, we take first steps towards understanding this complex problem. In particular, we consider two classical scheduling problems that capture dependencies across jobs: 1) concurrent open-shop scheduling (COSSP) and 2) precedence constrained scheduling. Our main motivation to study these problems specifically comes from their relevance to two scheduling problems that have gained importance in the context of data centers: co-flow scheduling and DAG scheduling. We design almost optimal approximation algorithms for COSSP and PCSP, and show hardness results.
BibTeX
@inproceedings{kulkarni2018flow,
  author = {Janardhan Kulkarni and Shi Li},
  title = {{Flow-time Optimization for Concurrent Open-Shop and Precedence Constrained Scheduling Models}},
  booktitle = {APPROX-RANDOM},
  year = {2018},
  url = {https://openreview.net/forum?id=FNhkZr5cFg},
}
Figure