{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T06:21:03Z","timestamp":1725603663990},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_48","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T13:14:33Z","timestamp":1314710073000},"page":"567-578","source":"Crossref","is-referenced-by-count":7,"title":["Robust Algorithms for Preemptive Scheduling"],"prefix":"10.1007","author":[{"given":"Leah","family":"Epstein","sequence":"first","affiliation":[]},{"given":"Asaf","family":"Levin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"48_CR1","unstructured":"Alon, N., Azar, Y., Woeginger, G.J., Yadid, T.: Approximation schemes for scheduling. In: Proc. 8th Symp. on Discrete Algorithms (SODA), pp. 493\u2013500. ACM\/SIAM (1997)"},{"issue":"3","key":"48_CR2","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1145\/258128.258201","volume":"44","author":"J. Aspnes","year":"1997","unstructured":"Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., Waarts, O.: On-line load balancing with applications to machine scheduling and virtual circuit routing. Journal of the ACM\u00a044(3), 486\u2013504 (1997)","journal-title":"Journal of the ACM"},{"issue":"2","key":"48_CR3","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1006\/jagm.1995.1008","volume":"18","author":"Y. Azar","year":"1995","unstructured":"Azar, Y., Naor, J., Rom, R.: The competitiveness of on-line assignments. Journal of Algorithms\u00a018(2), 221\u2013237 (1995)","journal-title":"Journal of Algorithms"},{"key":"48_CR4","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1006\/jagm.1999.1070","volume":"35","author":"P. Berman","year":"2000","unstructured":"Berman, P., Charikar, M., Karpinski, M.: On-line load balancing for related machines. Journal of Algorithms\u00a035, 108\u2013121 (2000)","journal-title":"Journal of Algorithms"},{"key":"48_CR5","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1002\/nav.10058","volume":"92","author":"A. Caprara","year":"2003","unstructured":"Caprara, A., Kellerer, H., Pferschy, U.: Approximation schemes for ordered vector packing problems. Naval Research Logistics\u00a092, 58\u201369 (2003)","journal-title":"Naval Research Logistics"},{"key":"48_CR6","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0167-6377(95)00039-9","volume":"18","author":"B. Chen","year":"1995","unstructured":"Chen, B., van Vliet, A., Woeginger, G.J.: An optimal algorithm for preemptive on-line scheduling. Operations Research Letters\u00a018, 127\u2013131 (1995)","journal-title":"Operations Research Letters"},{"key":"48_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-642-03685-9_7","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"J.R. Correa","year":"2009","unstructured":"Correa, J.R., Skutella, M., Verschae, J.: The power of preemption on unrelated machines and applications to scheduling orders. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX 2009. LNCS, vol.\u00a05687, pp. 84\u201397. Springer, Heidelberg (2009)"},{"issue":"1","key":"48_CR8","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1137\/090766139","volume":"25","author":"G. D\u00f3sa","year":"2011","unstructured":"D\u00f3sa, G., Epstein, L.: Preemptive online scheduling with reordering. SIAM Journal on Discrete Mathematics\u00a025(1), 21\u201349 (2011)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"4","key":"48_CR9","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1007\/s00453-008-9235-6","volume":"53","author":"T. Ebenlendr","year":"2009","unstructured":"Ebenlendr, T., Jawor, W., Sgall, J.: Preemptive online scheduling: optimal algorithms for all speeds. Algorithmica\u00a053(4), 504\u2013522 (2009)","journal-title":"Algorithmica"},{"issue":"5","key":"48_CR10","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/s10951-009-0119-7","volume":"12","author":"T. Ebenlendr","year":"2009","unstructured":"Ebenlendr, T., Sgall, J.: Optimal and online preemptive scheduling on uniformly related machines. Journal of Scheduling\u00a012(5), 517\u2013527 (2009)","journal-title":"Journal of Scheduling"},{"key":"48_CR11","doi-asserted-by":"crossref","unstructured":"Englert, M., \u00d6zmen, D., Westermann, M.: The power of reordering for online minimum makespan scheduling. In: Proc. 48th Symp. Foundations of Computer Science (FOCS), pp. 603\u2013612 (2008)","DOI":"10.1109\/FOCS.2008.46"},{"issue":"2","key":"48_CR12","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0167-6377(01)00085-2","volume":"29","author":"L. Epstein","year":"2001","unstructured":"Epstein, L.: Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios. Operations Research Letters\u00a029(2), 93\u201398 (2001)","journal-title":"Operations Research Letters"},{"issue":"1","key":"48_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-007-0200-y","volume":"119","author":"L. Epstein","year":"2009","unstructured":"Epstein, L., Levin, A.: A robust APTAS for the classical bin packing problem. Mathemtical Programming\u00a0119(1), 33\u201349 (2009)","journal-title":"Mathemtical Programming"},{"issue":"6","key":"48_CR14","doi-asserted-by":"publisher","first-page":"3121","DOI":"10.1137\/090767613","volume":"20","author":"L. Epstein","year":"2010","unstructured":"Epstein, L., Levin, A.: AFPTAS results for common variants of bin packing: A new method for handling the small items. SIAM Journal on Optimization\u00a020(6), 3121\u20133145 (2010)","journal-title":"SIAM Journal on Optimization"},{"key":"48_CR15","unstructured":"Epstein, L., Levin, A.: Robust approximation schemes for cube packing (2010)"},{"issue":"2","key":"48_CR16","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1002\/jos.60","volume":"4","author":"L. Epstein","year":"2001","unstructured":"Epstein, L., Noga, J., Seiden, S.S., Sgall, J., Woeginger, G.J.: Randomized online scheduling on two uniform machines. Journal of Scheduling\u00a04(2), 71\u201392 (2001)","journal-title":"Journal of Scheduling"},{"issue":"1","key":"48_CR17","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0167-6377(99)00062-0","volume":"26","author":"L. Epstein","year":"2000","unstructured":"Epstein, L., Sgall, J.: A lower bound for on-line scheduling on uniformly related machines. Operations Research Letters\u00a026(1), 17\u201322 (2000)","journal-title":"Operations Research Letters"},{"issue":"1","key":"48_CR18","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/j.jcss.2005.08.002","volume":"72","author":"L. Epstein","year":"2006","unstructured":"Epstein, L., Tassa, T.: Optimal preemptive scheduling for general target functions. Journal of Computer and System Sciences\u00a072(1), 132\u2013162 (2006)","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"48_CR19","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/1099-1425(200011\/12)3:6<343::AID-JOS54>3.0.CO;2-2","volume":"3","author":"R. Fleischer","year":"2000","unstructured":"Fleischer, R., Wahl, M.: Online scheduling revisited. Journal of Scheduling\u00a03(5), 343\u2013353 (2000)","journal-title":"Journal of Scheduling"},{"key":"48_CR20","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1145\/322047.322055","volume":"25","author":"T.F. Gonzales","year":"1978","unstructured":"Gonzales, T.F., Sahni, S.: Preemptive scheduling of uniform processor systems. Journal of the ACM\u00a025, 92\u2013101 (1978)","journal-title":"Journal of the ACM"},{"key":"48_CR21","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"R.L. Graham","year":"1966","unstructured":"Graham, R.L.: Bounds for certain multiprocessing anomalies. Bell System Technical Journal\u00a045, 1563\u20131581 (1966)","journal-title":"Bell System Technical Journal"},{"issue":"1","key":"48_CR22","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/321992.321995","volume":"24","author":"E.C. Horvath","year":"1977","unstructured":"Horvath, E.C., Lam, S., Sethi, R.: A level algorithm for preemptive scheduling. Journal of the ACM\u00a024(1), 32\u201343 (1977)","journal-title":"Journal of the ACM"},{"issue":"4","key":"48_CR23","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/322092.322101","volume":"25","author":"E.L. Lawler","year":"1978","unstructured":"Lawler, E.L., Labetoulle, J.: On preemptive scheduling of unrelated parallel processors by linear programming. Journal of the ACM\u00a025(4), 612\u2013619 (1978)","journal-title":"Journal of the ACM"},{"key":"48_CR24","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/BF01585745","volume":"46","author":"J.K. Lenstra","year":"1990","unstructured":"Lenstra, J.K., Shmoys, D.B., Tardos, E.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program.\u00a046, 259\u2013271 (1990)","journal-title":"Math. Program."},{"key":"48_CR25","unstructured":"Liu, J.W.S., Liu, C.L.: Bounds on scheduling algorithms for heterogeneous computing systems. In: Rosenfeld, J.L. (ed.) Proceedings of IFIP Congress 1974. Information Processing, vol.\u00a074, pp. 349\u2013353 (1974)"},{"key":"48_CR26","first-page":"38","volume-title":"Proceedings of the ACM National Conference","author":"J.W.S. Liu","year":"1974","unstructured":"Liu, J.W.S., Yang, A.T.: Optimal scheduling of independent tasks on heterogeneous computing systems. In: Proceedings of the ACM National Conference, vol.\u00a01, pp. 38\u201345. ACM, New York (1974)"},{"key":"48_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"6","author":"R. McNaughton","year":"1959","unstructured":"McNaughton, R.: Scheduling with deadlines and loss functions. Management Science\u00a06, 1\u201312 (1959)","journal-title":"Management Science"},{"issue":"11","key":"48_CR28","doi-asserted-by":"publisher","first-page":"1014","DOI":"10.1109\/T-C.1969.222573","volume":"18","author":"R.R. Muntz","year":"1969","unstructured":"Muntz, R.R., Coffman Jr., E.G.: Optimal preemptive scheduling on two-processor systems. IEEE Transactions on Computers\u00a018(11), 1014\u20131020 (1969)","journal-title":"IEEE Transactions on Computers"},{"issue":"2","key":"48_CR29","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/321574.321586","volume":"17","author":"R.R. Muntz","year":"1970","unstructured":"Muntz, R.R., Coffman Jr., E.G.: Preemptive scheduling of real-time tasks on multiprocessor systems. Journal of the ACM\u00a017(2), 324\u2013338 (1970)","journal-title":"Journal of the ACM"},{"issue":"2","key":"48_CR30","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1287\/moor.1090.0381","volume":"34","author":"P. Sanders","year":"2009","unstructured":"Sanders, P., Sivadasan, N., Skutella, M.: Online scheduling with bounded migration. Mathematics of Operations Research\u00a034(2), 481\u2013498 (2009)","journal-title":"Mathematics of Operations Research"},{"issue":"1","key":"48_CR31","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/S0020-0190(97)00093-8","volume":"63","author":"J. Sgall","year":"1997","unstructured":"Sgall, J.: A lower bound for randomized on-line multiprocessor scheduling. Information Processing Letters\u00a063(1), 51\u201355 (1997)","journal-title":"Information Processing Letters"},{"issue":"3-4","key":"48_CR32","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s00453-005-1171-0","volume":"42","author":"H. Shachnai","year":"2005","unstructured":"Shachnai, H., Tamir, T., Woeginger, G.J.: Minimizing makespan and preemption costs on a system of uniform machines. Algorithmica\u00a042(3-4), 309\u2013334 (2005)","journal-title":"Algorithmica"},{"key":"48_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/978-3-642-15775-2_4","volume-title":"Algorithms \u2013 ESA 2010","author":"M. Skutella","year":"2010","unstructured":"Skutella, M., Verschae, J.: A robust PTAS for machine covering and packing. In: de Berg, M., Meyer, U. (eds.) ESA 2010. LNCS, vol.\u00a06346, pp. 36\u201347. Springer, Heidelberg (2010)"},{"key":"48_CR34","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0167-6377(98)00032-7","volume":"23","author":"J. Wen","year":"1998","unstructured":"Wen, J., Du, D.: Preemptive on-line scheduling for two uniform processors. Operations Research Letters\u00a023, 113\u2013116 (1998)","journal-title":"Operations Research Letters"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,14]],"date-time":"2019-06-14T16:08:28Z","timestamp":1560528508000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}