{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T03:40:08Z","timestamp":1748749208371,"version":"3.41.0"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319286839"},{"type":"electronic","value":"9783319286846"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"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":[[2015]]},"DOI":"10.1007\/978-3-319-28684-6_16","type":"book-chapter","created":{"date-parts":[[2016,1,12]],"date-time":"2016-01-12T10:32:03Z","timestamp":1452594723000},"page":"183-195","source":"Crossref","is-referenced-by-count":1,"title":["Scheduling Parallel Jobs Online with Convex and Concave Parallelizability"],"prefix":"10.1007","author":[{"given":"Roozbeh","family":"Ebrahimi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"McCauley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,1,13]]},"reference":[{"key":"16_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-642-14165-2_28","volume-title":"Automata, Languages and Programming","author":"N Bansal","year":"2010","unstructured":"Bansal, N., Krishnaswamy, R., Nagarajan, V.: Better scalable algorithms for broadcast scheduling. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 324\u2013335. Springer, Heidelberg (2010)"},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1007\/978-3-540-74466-5_80","volume-title":"Euro-Par 2007 Parallel Processing","author":"O Beaumont","year":"2007","unstructured":"Beaumont, O., Guermouche, A.: Task scheduling for parallel multifrontal methods. In: Kermarrec, A.-M., Boug\u00e9, L., Priol, T. (eds.) Euro-Par 2007. LNCS, vol. 4641, pp. 758\u2013766. Springer, Heidelberg (2007)"},{"issue":"4","key":"16_CR3","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1109\/TC.2006.58","volume":"55","author":"J Blazewicz","year":"2006","unstructured":"Blazewicz, J., Kovalyov, M.Y., Machowiak, M., Trystram, D., Weglarz, J.: Preemptable malleable task scheduling problem. IEEE Trans. Comput. 55(4), 486\u2013490 (2006)","journal-title":"IEEE Trans. Comput."},{"issue":"1\u20134","key":"16_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1023\/B:ANOR.0000030682.25673.c0","volume":"129","author":"J Blazewicz","year":"2004","unstructured":"Blazewicz, J., Machowiak, M., Weglarz, J., Kovalyov, M.Y., Trystram, D.: Scheduling malleable tasks on parallel processors to minimize the makespan. Ann. Oper. Res. 129(1\u20134), 65\u201380 (2004)","journal-title":"Ann. Oper. Res."},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Chadha, J.S., Garg, N., Kumar, A., Muralidhara, V.N.: A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation. In: Proceedings of the 41st Symposium on Theory of Computation (STOC) (2009)","DOI":"10.1145\/1536414.1536506"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"Chan, S.H., Lam, T.W., Lee, L.K., Zhu, J.: Nonclairvoyant sleep management and flow-time scheduling on multiple processors. In: Proceedings of the 25th Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 261\u2013270 (2013)","DOI":"10.1145\/2486159.2486179"},{"issue":"1","key":"16_CR7","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0304-3975(99)00186-3","volume":"235","author":"J Edmonds","year":"2000","unstructured":"Edmonds, J.: Scheduling in the dark. Theoret. Comput. Sci. 235(1), 109\u2013141 (2000). Preliminary version in STOC 1999","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR8","unstructured":"Edmonds, J., Im, S., Moseley, B.: Online scalable scheduling for the $$\\ell _k$$ \u2113 k -norms of flow time without conservation of work. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2011)"},{"issue":"3","key":"16_CR9","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/2229163.2229172","volume":"8","author":"J Edmonds","year":"2012","unstructured":"Edmonds, J., Pruhs, K.: Scalably scheduling processes with arbitrary speedup curves. ACM Trans. Algorithms 8(3), 28:1\u201328:10 (2012)","journal-title":"ACM Trans. Algorithms"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Fox, K., Im, S., Moseley, B.: Energy efficient scheduling of parallelizable jobs. In: Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 948\u2013957 (2013)","DOI":"10.1137\/1.9781611973105.68"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Fox, K., Moseley, B.: Online scheduling on identical machines using SRPT. In: Proceedings of the 22nd ACM Symposium on Discrete Algorithms (SODA) (2011)","DOI":"10.1137\/1.9781611973082.10"},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"Gupta, A., Im, S., Krishnaswamy, R., Moseley, B., Pruhs, K.: Scheduling jobs with varying parallelizability to reduce variance. In: Proceedings of the Twenty-Second Syposium on Parallel Algorithms and Architectures (SPAA), pp. 11\u201320 (2010)","DOI":"10.1145\/1810479.1810482"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B.: Online scalable algorithm for minimizing $$\\ell _k$$ \u2113 k -norms of weighted flow time on unrelated machines. In: Proceedings of the Twenty-Second Annual ACM Symposium on Discrete Algorithms (SODA), pp. 95\u2013108 (2011)","DOI":"10.1137\/1.9781611973082.8"},{"key":"16_CR14","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/1998037.1998058","volume":"42","author":"S Im","year":"2011","unstructured":"Im, S., Moseley, B., Pruhs, K.: A tutorial on amortized local competitiveness in online scheduling. SIGACT News 42, 83\u201397 (2011)","journal-title":"SIGACT News"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B., Pruhs, K., Torng, E.: Competitively scheduling tasks with intermediate parallelizability. In: Proceedings of the Twenty-Sixth ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 22\u201329 (2014)","DOI":"10.1145\/2612669.2612682"},{"issue":"4","key":"16_CR16","doi-asserted-by":"publisher","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(4), 617\u2013643 (2000)","journal-title":"J. ACM"},{"issue":"6","key":"16_CR17","doi-asserted-by":"publisher","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(6), 875\u2013891 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR18","unstructured":"Ludwig, W., Tiwari, P.: Scheduling malleable and nonmalleable parallel tasks. In: Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 167\u2013176 (1994)"},{"issue":"6","key":"16_CR19","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1109\/71.506703","volume":"7","author":"GNS Prasanna","year":"1996","unstructured":"Prasanna, G.N.S., Musicus, B.R.: Generalized multiprocessor scheduling and applications to matrix computations. IEEE Trans. Parallel Distrib. Syst. 7(6), 650\u2013664 (1996)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"16_CR20","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"K Pruhs","year":"2004","unstructured":"Pruhs, K., Sgall, J., Torng, E.: Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton (2004). Online Scheduling"}],"container-title":["Lecture Notes in Computer Science","Approximation and Online Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-28684-6_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T03:25:29Z","timestamp":1748748329000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-28684-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319286839","9783319286846"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-28684-6_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}