{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,21]],"date-time":"2026-10-21T04:15:49Z","timestamp":1792556149177,"version":"4.5.0"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2001,1]]},"abstract":"<jats:p>We consider the following fundamental scheduling problem. The input to the problem consists of n jobs and k machines. Each of the jobs is associated with a release time, a deadline, a weight, and a processing time on each of the machines. The goal is to find a nonpreemptive schedule that maximizes the weight of jobs that meet their respective deadlines. We give constant factor approximation algorithms for four variants of the problem, depending on the type of the machines (identical vs. unrelated) and the weight of the jobs (identical vs. arbitrary). All these variants are known to be NP-hard, and the two variants involving unrelated machines are also MAX-SNP hard. The specific results obtained are as follows: For identical job weights and unrelated machines: a greedy 2-approximation algorithm. For identical job weights and k identical machines: the same greedy algorithm achieves a tight $\\frac{(1+1\/k)^k}{(1+1\/k)^k-1}$ approximation factor. For arbitrary job weights and a single machine: an LP formulation achieves a 2-approximation for polynomially bounded integral input and a 3-approximation for arbitrary input. For unrelated machines, the factors are 3 and 4, respectively. For arbitrary job weights and k identical machines: the LP-based algorithm applied repeatedly achieves a $\\frac{(1+1\/k)^k}{(1+1\/k)^k-1}$ approximation factor for polynomially bounded integral input and a $\\frac{(1+1\/2k)^k}{(1+1\/2k)^k-1}$ approximation factor for arbitrary input. For arbitrary job weights and unrelated machines: a combinatorial $(3+2\\sqrt{2} \\approx 5.828)$-approximation algorithm.<\/jats:p>","DOI":"10.1137\/s0097539799354138","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"331-352","source":"Crossref","is-referenced-by-count":134,"title":["Approximating the Throughput of Multiple Machines in Real-Time Scheduling"],"prefix":"10.1137","volume":"31","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"M. Adler, A. L. Rosenberg, R. K. Sitaraman, and W. Unger,\n                      Scheduling time\u2010constrained communication in linear networks\n                      , in Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, ACM Press, New York, 1998, pp. 269\u2013278.","DOI":"10.1145\/277651.277693"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Susanne Albers, Naveen Garg, Stefano Leonardi, Minimizing stall time in single and parallel disk systems, ACM, New York, 1999, 454\u20134621715594","DOI":"10.1145\/276698.276858"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90037-0"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Baruch Awerbuch, Yossi Azar, Amos Fiat, Stefano Leonardi, Adi Ros\u00e9n, On\u2010line competitive algorithms for call admission in optical networks, Lecture Notes in Comput. Sci., Vol. 1136, Springer, Berlin, 1996, 431\u201344498d:68023","DOI":"10.1007\/3-540-61680-2_73"},{"key":"R5","unstructured":"B. Awerbuch, Y. Bartal, A. Fiat, and A. Ros\u00e9n,\n                      Competitive non\u2010preemptive call control\n                      , in Proceedings of the 5th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 1994, pp. 312\u2013320."},{"key":"R6","doi-asserted-by":"crossref","unstructured":"A. Bar\u2010Noy, R. Bar\u2010Yehuda, A. Freund, J. Naor, and B. Schieber,\n                      A unified approach to approximating resource allocation and scheduling\n                      , in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2000, pp. 735\u2013744.","DOI":"10.1145\/335305.335410"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797321237"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF00365406"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"P. Berman and B. DasGupta,\n                      Improvements in throughput maximization for real\u2010time scheduling\n                      , in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2000, pp. 680\u2013687.","DOI":"10.1145\/335305.335401"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s101079900102"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"J. Blazewicz, K. H. Ecker, G. Schmidt, and J. Weglarz,\n                      Scheduling in Computer and Manufacturing Systems\n                      , Springer\u2010Verlag, New York, 1994.","DOI":"10.1007\/978-3-662-00074-8"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"R13","unstructured":"T. Erlebach and K. Jansen,\n                      Conversion of coloring algorithms into maximum weight independent set algorithms\n                      , in Proceedings of the Workshop \u201cpproximation and Randomization Algorithms in Communication Networks\u201d (ARACNE 2000), Proceedings on Informatics 8, Carleton Scientific, Waterloo, ON, Canada, 2000, pp. 135\u2013145."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00112-5"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1287\/opre.35.6.849"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0821"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0206029"},{"key":"R18","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP\u2010Completeness\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"S. A. Goldman, J. Parwatikar, and S. Suri,\n                      On\u2010line scheduling with hard deadlines\n                      , in Proceedings of the 5th International Workshop on Algorithms and Data Structures, Lecture Notes in Comput. Sci. 1272, Springer\u2010Verlag, New York, 1997, pp. 258\u2013271.","DOI":"10.1007\/3-540-63307-3_65"},{"key":"R20","unstructured":"Michael Goldwasser, Patience is a virtue: the effect of slack on competitiveness for admission control, ACM, New York, 1999, 396\u20134051739968"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)90385-9"},{"key":"R22","unstructured":"Bala Kalyanasundaram, Kirk Pruhs, Eliminating migration in multi\u2010processor scheduling, ACM, New York, 1999, 499\u20135061739981"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.1.121"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236882"},{"key":"R25","first-page":"0","volume":"10","author":"Lawler E.","year":"1976","journal-title":"Rev. Fran\u010daise Automat. Informat. Recherche Op\u00e9rationelle S\u00e9r. Bleue"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/BF02248588"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys,\n                      Sequencing and Scheduling: Algorithms and Complexity\n                      , in Handbooks in Operations Research and Management Science, Vol. 4: Logistics for Production and Inventory, S. C. Graves, A. H. G. Rinnooy Kan, and P. H. Zipkin, eds., North Holland, Amsterdam, 1993, pp. 445\u2013522.","DOI":"10.1016\/S0927-0507(05)80189-6"},{"key":"R28","unstructured":"Richard Lipton, Andrew Tomkins, Online interval scheduling, ACM, New York, 1994, 302\u201331195c:90059"},{"key":"R29","unstructured":"Cynthia Phillips, R. Uma, Joel Wein, Off\u2010line admission control for general scheduling problems, ACM, New York, 2000, 879\u20138881755549"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321934"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199909\/10)2:5<215::AID-JOS27>3.0.CO;2-Y"},{"key":"R32","unstructured":"Gerhard Woeginger, When does a dynamic programming formulation guarantee the existence of an FPTAS? ACM, New York, 1999, 820\u20138291740016"},{"key":"R33","unstructured":"Mihalis Yannakakis, On the approximation of maximum satisfiability, ACM, New York, 1992, 1\u201391173875"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539799354138","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:21:16Z","timestamp":1787336476000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539799354138"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,1]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2001,1]]}},"alternative-id":["10.1137\/S0097539799354138"],"URL":"https:\/\/doi.org\/10.1137\/s0097539799354138","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,1]]}}}