{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:23:22Z","timestamp":1750307002580,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["JA612\/14-1"],"award-info":[{"award-number":["JA612\/14-1"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["228021"],"award-info":[{"award-number":["228021"]}],"id":[{"id":"10.13039\/501100000781","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":[[2012,7]]},"abstract":"<jats:p>We study two closely related problems in nonpreemptive scheduling of jobs on identical parallel machines. In these two settings there are either fixed jobs or nonavailability intervals during which the machines are not available; in both cases, the objective is to minimize the makespan. Both formulations have different applications, for example, in turnaround scheduling or overlay computing.<\/jats:p>\n          <jats:p>For both problems we contribute approximation algorithms with an improved ratio of 3\/2. For scheduling with fixed jobs, a lower bound of 3\/2 on the approximation ratio has been obtained by Scharbrodt et al. [1999]; for scheduling with nonavailability we provide the same lower bound.<\/jats:p>\n          <jats:p>We use dual approximation, creation of a gap structure, and a PTAS for the multiple subset sum problem, combined with a postprocessing step to assign large jobs.<\/jats:p>","DOI":"10.1145\/2229163.2229171","type":"journal-article","created":{"date-parts":[[2012,7,26]],"date-time":"2012-07-26T14:41:09Z","timestamp":1343313669000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Tight approximation algorithms for scheduling with fixed jobs and nonavailability"],"prefix":"10.1145","volume":"8","author":[{"given":"Florian","family":"Diedrich","sequence":"first","affiliation":[{"name":"University of Kiel, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[{"name":"University of Kiel, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lars","family":"Pr\u00e4del","sequence":"additional","affiliation":[{"name":"University of Kiel, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrich M.","family":"Schwarz","sequence":"additional","affiliation":[{"name":"University of Kiel, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ola","family":"Svensson","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Sciences, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,7,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00010-7"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022584312032"},{"volume-title":"Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00)","author":"Chekuri C.","key":"e_1_2_1_3_1","unstructured":"Chekuri , C. and Khanna , S . 2000. A PTAS for the multiple knapsack problem . In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00) . 213--222. Chekuri, C. and Khanna, S. 2000. A PTAS for the multiple knapsack problem. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'00). 213--222."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9271-2"},{"volume-title":"Proceedings of the 21th International Parallel and Distributed Processing Symposium (IPDPS'07)","author":"Eyraud-Dubois L.","key":"e_1_2_1_6_1","unstructured":"Eyraud-Dubois , L. , Mounie , G. , and Trystram , D . 2007. Analysis of scheduling algorithms with reservations . In Proceedings of the 21th International Parallel and Distributed Processing Symposium (IPDPS'07) . IEEE, 1--8. Eyraud-Dubois, L., Mounie, G., and Trystram, D. 2007. Analysis of scheduling algorithms with reservations. In Proceedings of the 21th International Parallel and Distributed Processing Symposium (IPDPS'07). IEEE, 1--8."},{"key":"e_1_2_1_7_1","unstructured":"Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company New York.   Garey M. R. and Johnson D. S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company New York."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0117039"},{"volume-title":"Approximation Algorithms for NP-Hard Problems","author":"Hochbaum D. S.","key":"e_1_2_1_9_1","unstructured":"Hochbaum , D. S. 1996. Approximation Algorithms for NP-Hard Problems . PWS Publishing Company . Hochbaum, D. S. 1996. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/7531.7535"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217033"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(98)00126-6"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.12.002"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/080731207"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27660-6_26"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-007-9102-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/07408179808966555"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Kellerer H. Pferschy U. and Pisinger D. 2004. Knapsack Problems. Springer.  Kellerer H. Pferschy U. and Pisinger D. 2004. Knapsack Problems. Springer.","DOI":"10.1007\/978-3-540-24777-7"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.4.339"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90013-M"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00121681"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00201-2"},{"volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"Leung J. Y.-T.","key":"e_1_2_1_24_1","unstructured":"Leung , J. Y.-T. 2004. Handbook of Scheduling: Algorithms, Models, and Performance Analysis . Chapman and Hall\/CRC. Leung, J. Y.-T. 2004. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman and Hall\/CRC."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2003.08.034"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/98124"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1100.0393"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050143"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<267::AID-JOS31>3.0.CO;2-H"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00022-I"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229171","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2229163.2229171","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:52Z","timestamp":1750236532000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2229163.2229171"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.1145\/2229163.2229171"],"URL":"https:\/\/doi.org\/10.1145\/2229163.2229171","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,7]]},"assertion":[{"value":"2009-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}