{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,4]],"date-time":"2024-03-04T11:21:31Z","timestamp":1709551291106},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,1,21]],"date-time":"2009-01-21T00:00:00Z","timestamp":1232496000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,10]]},"DOI":"10.1007\/s00453-008-9271-2","type":"journal-article","created":{"date-parts":[[2009,1,20]],"date-time":"2009-01-20T19:55:25Z","timestamp":1232481325000},"page":"391-404","source":"Crossref","is-referenced-by-count":12,"title":["Approximation Algorithms for Scheduling with\u00a0Reservations"],"prefix":"10.1007","volume":"58","author":[{"given":"Florian","family":"Diedrich","sequence":"first","affiliation":[]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[]},{"given":"Fanny","family":"Pascual","sequence":"additional","affiliation":[]},{"given":"Denis","family":"Trystram","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,1,21]]},"reference":[{"key":"9271_CR1","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1137\/S1052623498348481","volume":"11","author":"A. Caprara","year":"2000","unstructured":"Caprara, A., Kellerer, H., Pferschy, U.: The multiple subset sum problem. SIAM J. Optim. 11, 308\u2013319 (2000)","journal-title":"SIAM J. Optim."},{"issue":"3\u20134","key":"9271_CR2","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/S0020-0190(00)00010-7","volume":"73","author":"A. Caprara","year":"2000","unstructured":"Caprara, A., Kellerer, H., Pferschy, U.: A PTAS for the multiple subset sum problem with different knapsack capacities. Inf. Process. Lett. 73(3\u20134), 111\u2013118 (2000)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9271_CR3","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1023\/A:1022584312032","volume":"9","author":"A. Caprara","year":"2003","unstructured":"Caprara, A., Kellerer, H., Pferschy, U.: A 3\/4-approximation algorithm for multiple subset sum. J.\u00a0Heuristics 9(2), 99\u2013111 (2003)","journal-title":"J.\u00a0Heuristics"},{"issue":"3","key":"9271_CR4","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/S0097539700382820","volume":"35","author":"C. Chekuri","year":"2005","unstructured":"Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3), 713\u2013728 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9271_CR5","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1023\/A:1009894503716","volume":"4","author":"M. Dawande","year":"2000","unstructured":"Dawande, M., Kalagnanam, J., Keskinocak, P., Salman, F.S., Ravi, R.: Approximation algorithms for the multiple knapsack problem with assignment restrictions. J. Comb. Optim. 4(2), 171\u2013186 (2000)","journal-title":"J. Comb. Optim."},{"key":"9271_CR6","first-page":"1","volume-title":"IPDPS","author":"L. Eyraud-Dubois","year":"2007","unstructured":"Eyraud-Dubois, L., Mouni\u00e9, G., Trystram, D.: Analysis of scheduling algorithms with reservations. In: IPDPS, pp. 1\u20138. IEEE, New York (2007)"},{"key":"9271_CR7","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"1","key":"9271_CR8","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/7531.7535","volume":"34","author":"D.S. Hochbaum","year":"1987","unstructured":"Hochbaum, D.S., Shmoys, D.B.: Using dual approximation algorithms for scheduling problems: theoretical and practical results. J. ACM 34(1), 144\u2013162 (1987)","journal-title":"J. ACM"},{"issue":"3","key":"9271_CR9","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1137\/0217033","volume":"17","author":"D.S. Hochbaum","year":"1988","unstructured":"Hochbaum, D.S., Shmoys, D.B.: A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. SIAM J. Comput. 17(3), 539\u2013551 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9271_CR10","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.dam.2004.12.002","volume":"148","author":"H.-C. Hwang","year":"2005","unstructured":"Hwang, H.-C., Lee, K., Chang, S.Y.: The effect of machine availability on the worst-case performance of LPT. Discrete Appl. Math. 148(1), 49\u201361 (2005)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"9271_CR11","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"O.H. Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22(4), 463\u2013468 (1975)","journal-title":"J. ACM"},{"key":"9271_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-540-48413-4_6","volume-title":"RANDOM-APPROX","author":"H. Kellerer","year":"1999","unstructured":"Kellerer, H.: A polynomial time approximation scheme for the multiple knapsack problem. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM-APPROX. Lecture Notes in Computer Science, vol. 1671, pp. 51\u201362. Springer, Berlin (1999)"},{"issue":"2","key":"9271_CR13","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/S0022-0000(03)00006-0","volume":"66","author":"H. Kellerer","year":"2003","unstructured":"Kellerer, H., Mansini, R., Pferschy, U., Speranza, M.G.: An efficient fully polynomial approximation scheme for the subset-sum problem. J. Comput. Syst. Sci. 66(2), 349\u2013370 (2003)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9271_CR14","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1023\/A:1009813105532","volume":"3","author":"H. Kellerer","year":"1999","unstructured":"Kellerer, H., Pferschy, U.: A new fully polynomial time approximation scheme for the knapsack problem. J. Comb. Optim. 3(1), 59\u201371 (1999)","journal-title":"J. Comb. Optim."},{"key":"9271_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H. Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)"},{"issue":"4","key":"9271_CR16","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"E.L. Lawler","year":"1979","unstructured":"Lawler, E.L.: Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4(4), 339\u2013356 (1979)","journal-title":"Math. Oper. Res."},{"key":"9271_CR17","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/0166-218X(91)90013-M","volume":"30","author":"C.-Y. Lee","year":"1991","unstructured":"Lee, C.-Y.: Parallel machines scheduling with non-simultaneous machine available time. Discrete Appl. Math. 30, 53\u201361 (1991)","journal-title":"Discrete Appl. Math."},{"key":"9271_CR18","first-page":"363","volume":"9","author":"C.-Y. Lee","year":"1996","unstructured":"Lee, C.-Y.: Machine scheduling with an availability constraint. J. Glob. Optim. 9, 363\u2013384 (1996), Special Issue on Optimization of Scheduling Applications","journal-title":"J. Glob. Optim."},{"issue":"1\u20132","key":"9271_CR19","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/S0166-218X(99)00201-2","volume":"100","author":"C.-Y. Lee","year":"2000","unstructured":"Lee, C.-Y., He, Y., Tang, G.: A note on \u201cparallel machine scheduling with non-simultaneous machine available time. Discrete Appl. Math. 100(1\u20132), 133\u2013135 (2000)","journal-title":"Discrete Appl. Math."},{"key":"9271_CR20","volume-title":"Handbook of Scheduling","year":"2004","unstructured":"Leung, J.Y.-T. (ed.): Handbook of Scheduling. Chapman & Hall, London (2004)"},{"key":"9271_CR21","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1016\/j.ejor.2003.08.034","volume":"160","author":"C.-J. Liao","year":"2003","unstructured":"Liao, C.-J., Shyur, D.-L., Lin, C.-H.: Makespan minimization for two parallel machines with an availability constraint. Eur. J. Oper. Res. 160, 445\u2013456 (2003)","journal-title":"Eur. J. Oper. Res."},{"key":"9271_CR22","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1016\/j.ejor.2006.11.027","volume":"184","author":"L.-W. Liao","year":"2008","unstructured":"Liao, L.-W., Sheen, G.-J.: Parallel machine scheduling with machine availability and eligibility constraints. Eur. J. Oper. Res. 184, 458\u2013467 (2008)","journal-title":"Eur. J. Oper. Res."},{"key":"9271_CR23","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S. Martello","year":"1990","unstructured":"Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, New York (1990)"},{"issue":"1","key":"9271_CR24","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S. Sahni","year":"1976","unstructured":"Sahni, S.: Algorithms for scheduling independent tasks. J. ACM 23(1), 116\u2013127 (1976)","journal-title":"J. ACM"},{"key":"9271_CR25","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1002\/(SICI)1099-1425(199911\/12)2:6<267::AID-JOS31>3.0.CO;2-H","volume":"2","author":"M. Scharbrodt","year":"1999","unstructured":"Scharbrodt, M., Steger, A., Weisser, H.: Approximability of scheduling with fixed jobs. J. Sched. 2, 267\u2013284 (1999)","journal-title":"J. Sched."},{"issue":"1","key":"9271_CR26","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1287\/ijoc.12.1.57.11901","volume":"12","author":"G.J. Woeginger","year":"2000","unstructured":"Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?. INFORMS J. Comput. 12(1), 57\u201374 (2000)","journal-title":"INFORMS J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9271-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9271-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9271-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:03Z","timestamp":1559137503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9271-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,21]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["9271"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9271-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,21]]}}}