HyattDenesik, Dylan ;
Rahgoshay, Mirmahdi ;
Salavatipour, Mohammad R.
Approximations for Throughput Maximization
Abstract
In this paper we study the classical problem of throughput maximization. In this problem we have a collection J of n jobs, each having a release time r_j, deadline d_j, and processing time p_j. They have to be scheduled nonpreemptively on m identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their [r_j,d_j] window. This problem has been studied extensively (even for the case of m = 1). Several special cases of the problem remain open. BarNoy et al. [STOC1999] presented an algorithm with ratio 11/(1+1/m)^m for m machines, which approaches 11/e as m increases. For m = 1, ChuzhoyOstrovskyRabani [FOCS2001] presented an algorithm with approximation with ratio 11/eε (for any ε > 0). Recently ImLiMoseley [IPCO2017] presented an algorithm with ratio 11/e+ε₀ for some absolute constant ε₀ > 0 for any fixed m. They also presented an algorithm with ratio 1O(√(log m/m))ε for general m which approaches 1 as m grows. The approximability of the problem for m = O(1) remains a major open question. Even for the case of m = 1 and c = O(1) distinct processing times the problem is open (Sgall [ESA2012]). In this paper we study the case of m = O(1) and show that if there are c distinct processing times, i.e. p_j’s come from a set of size c, then there is a randomized (1ε)approximation that runs in time O(n^{mc⁷ε^(6)}log T), where T is the largest deadline. Therefore, for constant m and constant c this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning.
BibTeX  Entry
@InProceedings{hyattdenesik_et_al:LIPIcs:2020:13355,
author = {Dylan HyattDenesik and Mirmahdi Rahgoshay and Mohammad R. Salavatipour},
title = {{Approximations for Throughput Maximization}},
booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)},
pages = {11:111:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771733},
ISSN = {18688969},
year = {2020},
volume = {181},
editor = {Yixin Cao and SiuWing Cheng and Minming Li},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13355},
URN = {urn:nbn:de:0030drops133555},
doi = {10.4230/LIPIcs.ISAAC.2020.11},
annote = {Keywords: Scheduling, Approximation Algorithms, Throughput Maximization}
}
04.12.2020
Keywords: 

Scheduling, Approximation Algorithms, Throughput Maximization 
Seminar: 

31st International Symposium on Algorithms and Computation (ISAAC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 