{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T05:59:10Z","timestamp":1725861550920},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319426334"},{"type":"electronic","value":"9783319426341"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-319-42634-1_41","type":"book-chapter","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T11:50:21Z","timestamp":1468929021000},"page":"510-519","source":"Crossref","is-referenced-by-count":1,"title":["From Preemptive to Non-preemptive Scheduling Using Rejections"],"prefix":"10.1007","author":[{"given":"Giorgio","family":"Lucarelli","sequence":"first","affiliation":[]},{"given":"Abhinav","family":"Srivastav","sequence":"additional","affiliation":[]},{"given":"Denis","family":"Trystram","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"41_CR1","volume-title":"Introduction to Sequencing and Scheduling","author":"KR Baker","year":"1974","unstructured":"Baker, K.R.: Introduction to Sequencing and Scheduling. Wiley, New York (1974)"},{"key":"41_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chan, H.-L.: Weighted flow time does not admit $$o(1)$$ -competitive algorithms. In: SODA, pp. 1238\u20131244 (2009)","DOI":"10.1137\/1.9781611973068.134"},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"Bansal, N., Chan, H.-L., Khandekar, R., Pruhs, K., Stein, C., Schieber, B.: Non-preemptive min-sum scheduling with resource augmentation. In: FOCS, pp. 614\u2013624 (2007)","DOI":"10.1109\/FOCS.2007.11"},{"issue":"4","key":"41_CR4","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/1290672.1290676","volume":"3","author":"N Bansal","year":"2007","unstructured":"Bansal, N., Dhamdhere, K.: Minimizing weighted flow time. ACM Trans. Algorithms 3(4), 39 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"41_CR5","doi-asserted-by":"crossref","first-page":"1684","DOI":"10.1137\/130911317","volume":"43","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Pruhs, K.: The geometry of scheduling. SIAM J. Comput. 43, 1684\u20131698 (2014)","journal-title":"SIAM J. Comput."},{"key":"41_CR6","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/j.jda.2005.12.001","volume":"4","author":"L Becchetti","year":"2006","unstructured":"Becchetti, L., Leonardi, S., Marchetti-Spaccamela, A., Pruhs, K.: Online weighted flow time and deadline scheduling. J. Discrete Algorithms 4, 339\u2013352 (2006)","journal-title":"J. Discrete Algorithms"},{"key":"41_CR7","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1023\/B:JOSH.0000019681.52701.8b","volume":"7","author":"MA Bender","year":"2004","unstructured":"Bender, M.A., Muthukrishnan, S., Rajaraman, R.: Approximation algorithms for average stretch scheduling. J. Sched. 7, 195\u2013222 (2004)","journal-title":"J. Sched."},{"key":"41_CR8","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/j.ipl.2004.02.013","volume":"90","author":"DP Bunde","year":"2004","unstructured":"Bunde, D.P.: SPT is optimally competitive for uniprocessor flow. Inf. Process. Lett. 90, 233\u2013238 (2004)","journal-title":"Inf. Process. Lett."},{"key":"41_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Zhu, A.: Algorithms for minimizing weighted flow time. In: STOC, pp. 84\u201393 (2001)","DOI":"10.1145\/380752.380778"},{"key":"41_CR10","doi-asserted-by":"crossref","unstructured":"Choudhury, A.R., Das, S., Garg, N., Kumar, A.: Rejecting jobs to minimize load and maximum flow-time. In: SODA, pp. 1114\u20131133 (2015)","DOI":"10.1137\/1.9781611973730.75"},{"key":"41_CR11","unstructured":"Choudhury, A.R., Das, S., Kumar, A.: Minimizing weighted lp-norm of flow-time in the rejection model. In: FSTTCS, pp. 25\u201337 (2015)"},{"key":"41_CR12","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1016\/j.dam.2005.05.016","volume":"154","author":"L Epstein","year":"2006","unstructured":"Epstein, L., van Stee, R.: Optimal on-line flow time with resource augmentation. Discrete Appl. Math. 154, 611\u2013621 (2006)","journal-title":"Discrete Appl. Math."},{"key":"41_CR13","doi-asserted-by":"crossref","unstructured":"Im, S., Li, S., Moseley, B., Torng, E.: A dynamic programming framework for non-preemptive scheduling problems on multiple machines [extended abstract]. In: SODA, pp. 1070\u20131086 (2015)","DOI":"10.1137\/1.9781611973730.72"},{"key":"41_CR14","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Speed is as powerful as clairvoyance. J. ACM 47, 617\u2013643 (2000)","journal-title":"J. ACM"},{"key":"41_CR15","doi-asserted-by":"crossref","first-page":"1155","DOI":"10.1137\/S0097539796305778","volume":"28","author":"H Kellerer","year":"1999","unstructured":"Kellerer, H., Tautenhahn, T., Woeginger, G.J.: Approximability and nonapproximability results for minimizing total flow time on a single machine. SIAM J. Comput. 28, 1155\u20131166 (1999)","journal-title":"SIAM J. Comput."},{"key":"41_CR16","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1016\/j.jcss.2006.10.018","volume":"73","author":"S Leonardi","year":"2007","unstructured":"Leonardi, S., Raz, D.: Approximating total flow time on parallel machines. J. Comput. Syst. Sci. 73, 875\u2013891 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"41_CR17","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1137\/S0097539701387544","volume":"34","author":"S Muthukrishnan","year":"2005","unstructured":"Muthukrishnan, S., Rajaraman, R., Shaheen, A., Gehrke, J.E.: Online scheduling to minimize average stretch. SIAM J. Comput. 34, 433\u2013452 (2005)","journal-title":"SIAM J. Comput."},{"key":"41_CR18","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s00453-001-0068-9","volume":"32","author":"CA Phillips","year":"2002","unstructured":"Phillips, C.A., Stein, C., Torng, E., Wein, J.: Optimal time-critical scheduling via resource augmentation. Algorithmica 32, 163\u2013200 (2002)","journal-title":"Algorithmica"},{"key":"41_CR19","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1287\/opre.16.3.687","volume":"16","author":"L Schrage","year":"1968","unstructured":"Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16, 687\u2013690 (1968)","journal-title":"Oper. Res."},{"key":"41_CR20","doi-asserted-by":"publisher","unstructured":"Tao, J., Liu, T.: WSPT\u2019s competitive performance for minimizing the total weighted flow time: from single to parallel machines. Math. Probl. Eng. (2013). doi: 10.1155\/2013\/343287","DOI":"10.1155\/2013\/343287"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-42634-1_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T07:04:32Z","timestamp":1568185472000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-42634-1_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319426334","9783319426341"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-42634-1_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}