Maximizing Throughput in Flow Shop Real-Time Scheduling

Lior Ben Yamin, Jing Li, Kanthi K. Sarpatwar, Baruch Schieber, Hadas ShachnaiAPPROX-RANDOM 2020 · OpenReview

TL;DR

This paper tackles the challenging problem of maximizing throughput in real-time flow shop scheduling, where jobs have specific release times and deadlines. The authors present the first non-trivial approximation algorithms for this problem, offering a (2m+1)-approximation for general m-machine flow shops and a significantly better (9+ε)-approximation for the common two-machine case.

What Problem Does This Paper Address?

The authors address the problem of maximizing throughput in a real-time flow shop scheduling model. Imagine a manufacturing line or a cloud computing pipeline where jobs (tasks) must pass through a sequence of machines (stages) in a fixed order. Each job has a release time (when it becomes available), a due date (when it must be completed), and a weight (representing its importance or profit). The goal is to select a subset of jobs that can be processed through all machines within their respective time windows and maximize the total weight of these selected jobs.

While flow shop scheduling is a well-studied area, most prior work focused on minimizing metrics like makespan (total time to complete all jobs) or flow time. Real-time scheduling, where jobs have deadlines, is also extensively studied, but typically for single-machine or parallel-machine environments. This paper bridges a gap by focusing on throughput maximization specifically within the flow shop constraint, which adds significant complexity. Real-world applications include autonomous vehicle navigation, cloud data centers, and earth observation satellites, where timely processing of multiple data streams is crucial.

Methods

The paper introduces novel approximation algorithms for this problem.

  • For general m-machine flow shops (m ≥ 2, constant): They develop a pseudo-polynomial time (2m+1)-approximation algorithm. This algorithm is based on formulating the problem as a Configuration Linear Program (LP). The LP is then solved, and its fractional solution is rounded to obtain an approximate integer solution. The core idea involves defining "job cliques" based on intersecting job segments on machines and using a hierarchical ordering of job occurrences derived from a key lemma about neighboring job occurrences.
  • For the two-machine case (m=2): They achieve a much better polynomial-time (9+ε)-approximation algorithm. This involves a more intricate approach:
  • Eliminating "Almost-Large" Jobs: These jobs are decomposed into combinations of "Large" and "Small" jobs to simplify the problem.
  • Modified Linear Program: A new LP is formulated considering only "selected" job occurrences, with relaxed clique constraints.
  • Rounding: A sophisticated rounding technique, leveraging a new lemma for the two-machine case, transforms the LP solution into a feasible schedule.
  • Special Cases for Two Machines: They also present improved approximation ratios for specific scenarios:
  • A 4-approximation for jobs with the same release time (0) and unit weights.
  • A (3+ε)-approximation for jobs with the same release time (0) and due date (T). These algorithms often leverage existing single-machine scheduling algorithms like Moore's algorithm.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithm design and analysis rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Flow shop + Real-time = Hard: Combining the sequential machine constraints of flow shops with the deadline-driven nature of real-time scheduling creates a significantly harder problem than either in isolation.
  • Configuration LP as a Powerful Tool: The paper demonstrates the effectiveness of formulating scheduling problems as Configuration LPs, where job occurrences are treated as configurations. This allows for leveraging LP relaxation and rounding techniques.
  • Job Cliques Capture Conflicts: The concept of "job cliques" is crucial for modeling conflicts. If two job occurrences are in the same clique, they cannot both be scheduled.
  • Hierarchical Ordering for Rounding: The hierarchical ordering of job occurrences, derived from a key lemma, is essential for the greedy assignment of time intervals in the general m-machine algorithm.
  • Decomposition for Two Machines: The strategy of decomposing "almost-large" jobs into simpler "large" and "small" jobs is a clever way to handle complex job types and improve approximation ratios.
  • Bridging Single-Machine and Flow Shop: The paper shows how insights and algorithms from single-machine real-time scheduling can be adapted and extended to the two-machine flow shop setting, leading to better results for specific cases.

Key Results

  • General m-machine flow shop (m ≥ 2, constant): A pseudo-polynomial time (2m+1)-approximation algorithm for maximizing throughput. This is stated to be nearly tight due to hardness results.
  • Two-machine flow shop: A polynomial-time (9+ε)-approximation algorithm.
  • Restricted two-machine cases:
    • 4-approximation for unit weight jobs with the same release time.
  • (3+ε)-approximation for jobs with the same release time and due date.

Limitations and Future Work

  • Pseudo-polynomial Time for General m: The (2m+1)-approximation algorithm for m machines is pseudo-polynomial, meaning its runtime depends on the magnitude of the input values (like due dates). Converting this to a truly polynomial-time algorithm for constant m remains an open challenge.
  • Approximation Ratios: While significant progress is made, the approximation ratios for the general m-machine case are still relatively high. Further improvements would be valuable.
  • Practical Performance: The paper focuses on theoretical guarantees. Empirical evaluation of the proposed algorithms on real-world or synthetic datasets would be beneficial to understand their practical performance.
  • More Restricted Cases: Exploring other restricted subclasses of jobs or machine configurations for the two-machine case could potentially yield even better approximation ratios.
  • Preemptive Scheduling: The current work assumes non-preemptive jobs. Extending these results to preemptive scheduling could be a future direction.

Summary updated

Abstract

We consider scheduling real-time jobs in the classic flow shop model. The input is a set of n jobs, each consisting of m segments to be processed on m machines in the specified order, such that segment I_i of a job can start processing on machine M_i only after segment I_{i-1} of the same job completed processing on machine M_{i-1}, for 2 ≤ i ≤ m. Each job also has a release time, a due date, and a weight. The objective is to maximize the throughput (or, profit) of the n jobs, i.e., to find a subset of the jobs that have the maximum total weight and can complete processing on the m machines within their time windows. This problem has numerous real-life applications ranging from manufacturing to cloud and embedded computing platforms, already in the special case where m = 2. Previous work in the flow shop model has focused on makespan, flow time, or tardiness objectives. However, little is known for the flow shop model in the real-time setting. In this work, we give the first nontrivial results for this problem and present a pseudo-polynomial time (2m+1)-approximation algorithm for the problem on m ≥ 2 machines, where m is a constant. This ratio is essentially tight due to a hardness result of Ω(m/(log m)) for the approximation ratio. We further give a polynomial-time algorithm for the two-machine case, with an approximation ratio of (9+ε) where ε = O(1/n). We obtain better bounds for some restricted subclasses of inputs with two machines. To the best of our knowledge, this fundamental problem of throughput maximization in the flow shop scheduling model is studied here for the first time.
BibTeX
@inproceedings{yamin2020maximizing,
  author = {Lior Ben Yamin and Jing Li and Kanthi K. Sarpatwar and Baruch Schieber and Hadas Shachnai},
  title = {{Maximizing Throughput in Flow Shop Real-Time Scheduling}},
  booktitle = {APPROX-RANDOM},
  year = {2020},
  url = {https://openreview.net/forum?id=xCA_VfziN_},
}
Figure