{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T02:02:43Z","timestamp":1769047363572,"version":"3.49.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,3,1]],"date-time":"2009-03-01T00:00:00Z","timestamp":1235865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","award":["IST-1999-14084"],"award-info":[{"award-number":["IST-1999-14084"]}],"id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p>\n            We consider the following scheduling with batching problem that has many applications, for example, in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of\n            <jats:italic>n<\/jats:italic>\n            jobs and\n            <jats:italic>k<\/jats:italic>\n            parallel machines. Each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or nonexplicitly), a weight, and a family. Each family is associated with a processing time. Jobs that belong to the same family can be batched and executed together on the same machine. The processing time of each batch is the processing time of the family of jobs it contains. The goal is to find a nonpreemptive schedule with batching that maximizes the weight of the scheduled jobs. We give constant factor (4 or 4 + \u03b5) approximation algorithms for two variants of the problem, depending on the precise representation of the input. When the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + \u03b5, respectively. We also give approximation algorithms for two special cases when all release times are the same.\n          <\/jats:p>","DOI":"10.1145\/1497290.1497294","type":"journal-article","created":{"date-parts":[[2009,4,6]],"date-time":"2009-04-06T16:34:22Z","timestamp":1239035662000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Throughput maximization of real-time scheduling with batching"],"prefix":"10.1145","volume":"5","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[{"name":"Brooklyn College, Bedford Avenue Brooklyn, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sudipto","family":"Guha","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoav","family":"Katz","sequence":"additional","affiliation":[{"name":"IBM Haifa Research Lab, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center, Yorktown Heights, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[{"name":"Technion, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,3,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0360-8352(01)00009-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109596"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001860000088"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithm, ACM","author":"Bar-Noy A.","unstructured":"Bar-Noy , A. , Guha , S. , Katz , Y. , Naor , J. , Schieber , B. , and Shachnai , H . 2002. Throughput maximization of real-time scheduling with batching . In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithm, ACM , New York, 742--751. Bar-Noy, A., Guha, S., Katz, Y., Naor, J., Schieber, B., and Shachnai, H. 2002. Throughput maximization of real-time scheduling with batching. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithm, ACM, New York, 742--751."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799354138"},{"key":"e_1_2_1_8_1","first-page":"27","article-title":"Local ratio theorem for approximating the weighted vertex cover problem","volume":"25","author":"Bar-Yehuda R.","year":"1985","unstructured":"Bar-Yehuda , R. , and Even , S. 1985 . Local ratio theorem for approximating the weighted vertex cover problem . Ann. Disc. Math. 25 , 27 -- 46 . Bar-Yehuda, R., and Even, S. 1985. Local ratio theorem for approximating the weighted vertex cover problem. Ann. Disc. Math. 25, 27--46.","journal-title":"Ann. Disc. Math."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009822211065"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2005.854383"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199806)1:1<31::AID-JOS4>3.0.CO;2-R"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0218"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s005300050016"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.1.52.11189"},{"key":"e_1_2_1_16_1","unstructured":"Gailis R. and Khuller S. 2003. Broadcast scheduling with deadlines. Unpublished mansucript. (www.cs.umd.edu\/users\/samir\/grant\/renars.ps)  Gailis R. and Khuller S. 2003. Broadcast scheduling with deadlines. Unpublished mansucript. (www.cs.umd.edu\/users\/samir\/grant\/renars.ps)"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147956"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.45.6.874"},{"key":"e_1_2_1_20_1","article-title":"Multimedia-on-demand systems with broadcast, batch and interactive services. IEICE","author":"Lee V. W. H.","year":"2005","unstructured":"Lee , V. W. H. , Wong , E. W. M. , Ko , K.-T. , and Tang , K.-S. 2005 . Multimedia-on-demand systems with broadcast, batch and interactive services. IEICE Trans. Commun. E88-B, 3097--3100. Lee, V. W. H., Wong, E. W. M., Ko, K.-T., and Tang, K.-S. 2005. Multimedia-on-demand systems with broadcast, batch and interactive services. IEICE Trans. Commun. E88-B, 3097--3100.","journal-title":"Trans. Commun. E88-B, 3097--3100."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1080\/07408179808966448"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(03)00239-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010057"},{"key":"e_1_2_1_24_1","first-page":"442","article-title":"On the approximability of an interval scheduling problem","volume":"29","author":"Spieksma F. C. R.","year":"1999","unstructured":"Spieksma , F. C. R. 1999 . On the approximability of an interval scheduling problem . J. Sched. 29 , 442 -- 467 . Spieksma, F. C. R. 1999. On the approximability of an interval scheduling problem. J. Sched. 29, 442--467.","journal-title":"J. Sched."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1080\/00207549508904839"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497290.1497294","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1497290.1497294","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:40Z","timestamp":1750250740000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1497290.1497294"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1145\/1497290.1497294"],"URL":"https:\/\/doi.org\/10.1145\/1497290.1497294","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3]]},"assertion":[{"value":"2006-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}