1 Search Results for "Ben Yamin, Lior"

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.48

Maximizing Throughput in Flow Shop Real-Time Scheduling

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

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

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.

Cite as

Lior Ben Yamin, Jing Li, Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai. Maximizing Throughput in Flow Shop Real-Time Scheduling. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{benyamin_et_al:LIPIcs.APPROX/RANDOM.2020.48,
  author =	{Ben Yamin, Lior and Li, Jing and Sarpatwar, Kanthi and Schieber, Baruch and Shachnai, Hadas},
  title =	{{Maximizing Throughput in Flow Shop Real-Time Scheduling}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.48},
  URN =		{urn:nbn:de:0030-drops-126510},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.48},
  annote =	{Keywords: Flow shop, real-time scheduling, throughput maximization, approximation algorithms}
}

Refine by Author
1 Ben Yamin, Lior
1 Li, Jing
1 Sarpatwar, Kanthi
1 Schieber, Baruch
1 Shachnai, Hadas

Refine by Classification
1 Mathematics of computing → Combinatorial optimization
1 Theory of computation → Scheduling algorithms

Refine by Keyword
1 Flow shop
1 approximation algorithms
1 real-time scheduling
1 throughput maximization

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Ben Yamin, Lior"

Maximizing Throughput in Flow Shop Real-Time Scheduling

Abstract

Cite as

Thanks for your feedback!

Could not send message