Maximizing throughput in flow shop real-time scheduling

Lior Ben Yamin, Jing Li, Kanthi Sarpatwar, Baruch Schieber, Hadas Shachnai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 Ii of a job can start processing on machine Mi only after segment Ii−1 of the same job completed processing on machine Mi−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/logm) 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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2020
EditorsJaroslaw Byrka, Raghu Meka
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771641
DOIs
StatePublished - Aug 1 2020
Event23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020 - Virtual, Online, United States
Duration: Aug 17 2020Aug 19 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume176
ISSN (Print)1868-8969

Conference

Conference23rd International Conference on Approximation Algorithms for Combinatorial Optimization Problems and 24th International Conference on Randomization and Computation, APPROX/RANDOM 2020
CountryUnited States
CityVirtual, Online
Period8/17/208/19/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximation algorithms
  • Flow shop
  • Real-time scheduling
  • Throughput maximization

Fingerprint Dive into the research topics of 'Maximizing throughput in flow shop real-time scheduling'. Together they form a unique fingerprint.

Cite this