Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Maximizing Throughput in Flow Shop Real-time Scheduling
event speaker icon
Lior Ben-Yamin (M.Sc. Thesis Seminar)
event date icon
Thursday, 29.04.2021, 14:30
event location icon
Zoom Lecture: 93508538152
For password to lecture, please contact: lior.b@cs.technion.ac.il
event speaker icon
Advisor: Prof. H. Shachnai
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. Each job also has a release time, a due date, and a weight. The objective is to maximize the throughput, 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 throughput maximization on $m \geq 2$ machines, where m is a constant. This ratio is essentially tight due to a known hardness of approximation result. For the two-machine case, we give a polynomial-time $9+\eps$-approximation algorithms, where $\eps = O(1/n)$. Better bounds are derived for some restricted subclasses of inputs with two machines, as well as the no-wait flow shop model.