The Taub Faculty of Computer Science Events and Talks

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.