TY - JOUR
T1 - Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling
AU - Berman, Piotr
AU - Dasgupta, Bhaskar
N1 - Funding Information:
⁄A preliminary version of this paper will appear under the title ‘‘Improvements in Throughput Maximization for Real-Time Scheduling’’ in 32nd Annual ACM Symposium on Theory of Computing, May 2000. †Supported in part by NSF grant CCR-9700053 and National Library of Medicine grant LM05110. ‡Supported in part by NSF grant CCR-9800086.
Funding Information:
The authors would like to thank Sefi Naor and Baruch Schieber for their useful discussion and explanations, Amos Fiat and Gerhard Woeginger for organizing Dagstuhl workshop on online algorithms where some of these discussions took place, Michael A. Palis for pointing out applications of stretch factors to adaptive rate-controlled scheduling, as well as NSF and NLM for providing the financial support for this research.
PY - 2000
Y1 - 2000
N2 - We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem discussed here were already treated by Bar-Noy et al. (Proc. 31st ACM STOC, 1999, pp. 622-631; http://www.eng.tau.ac. il/∼amotz/). Our main contribution is to provide algorithms that do not use linear programming, are simple and much faster than the corresponding ones proposed in Bar-Noy et al. (ibid., 1999), while either having the same quality of approximation or improving it. More precisely, compared to the results of in Bar-Noy et al. (ibid., 1999), our pseudo-polynomial algorithm for multiple unrelated machines and all of our strongly-polynomial algorithms have better performance ratios, all of our algorithms run much faster, are combinatorial in nature and avoid linear programming. Finally, we show that algorithms with better performance ratios than 2 are possible if the stretch factors of the jobs are bounded; a straightforward consequence of this result is an improvement of the ratio of an optimal solution of the integer programming formulation of the JISP2 problem (see Spieksma, Journal of Scheduling, vol. 2, pp. 215-227, 1999) to its linear programming relaxation.
AB - We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem discussed here were already treated by Bar-Noy et al. (Proc. 31st ACM STOC, 1999, pp. 622-631; http://www.eng.tau.ac. il/∼amotz/). Our main contribution is to provide algorithms that do not use linear programming, are simple and much faster than the corresponding ones proposed in Bar-Noy et al. (ibid., 1999), while either having the same quality of approximation or improving it. More precisely, compared to the results of in Bar-Noy et al. (ibid., 1999), our pseudo-polynomial algorithm for multiple unrelated machines and all of our strongly-polynomial algorithms have better performance ratios, all of our algorithms run much faster, are combinatorial in nature and avoid linear programming. Finally, we show that algorithms with better performance ratios than 2 are possible if the stretch factors of the jobs are bounded; a straightforward consequence of this result is an improvement of the ratio of an optimal solution of the integer programming formulation of the JISP2 problem (see Spieksma, Journal of Scheduling, vol. 2, pp. 215-227, 1999) to its linear programming relaxation.
UR - http://www.scopus.com/inward/record.url?scp=0000332042&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0000332042&partnerID=8YFLogxK
U2 - 10.1023/A:1009822211065
DO - 10.1023/A:1009822211065
M3 - Article
AN - SCOPUS:0000332042
SN - 1382-6905
VL - 4
SP - 307
EP - 323
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 3
ER -