{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,22]],"date-time":"2023-09-22T06:21:05Z","timestamp":1695363665699},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,11,9]],"date-time":"2016-11-09T00:00:00Z","timestamp":1478649600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00224-016-9722-0","type":"journal-article","created":{"date-parts":[[2016,11,9]],"date-time":"2016-11-09T01:58:09Z","timestamp":1478656689000},"page":"304-318","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Scheduling Parallel Jobs Online with Convex and Concave Parallelizability"],"prefix":"10.1007","volume":"62","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,11,9]]},"reference":[{"key":"9722_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., Krishnaswamy, R., Nagarajan, V.: Better Scalable Algorithms for Broadcast Scheduling. In: Proceedings of the Thirty-Seventh Annual International Colloquium on Automata, Languages, and Processing (ICALP), pp 324\u2013335 (2010)","DOI":"10.1007\/978-3-642-14165-2_28"},{"key":"9722_CR2","doi-asserted-by":"crossref","unstructured":"Beaumont, O., Guermouche, A.: Task Scheduling for Parallel Multifrontal Methods. In: Euro-Par Parallel Processing, pp 758\u2013766. Springer (2007)","DOI":"10.1007\/978-3-540-74466-5_80"},{"issue":"4","key":"9722_CR3","doi-asserted-by":"crossref","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-4","key":"9722_CR4","doi-asserted-by":"crossref","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-4), 65\u201380 (2004)","journal-title":"Ann. Oper. Res."},{"key":"9722_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":"9722_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":"9722_CR7","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 235(1), 109\u2013141 (2000). Preliminary version in STOC 1999","journal-title":"Theor. Comput. Sci."},{"key":"9722_CR8","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Im, S., Moseley, B.: Online Scalable Scheduling for the \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)","DOI":"10.1137\/1.9781611973082.9"},{"issue":"3","key":"9722_CR9","doi-asserted-by":"crossref","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 Transactions on Algorithms 8(3), 28:1\u201328:10 (2012)","journal-title":"ACM Transactions on Algorithms"},{"key":"9722_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":"9722_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":"9722_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":"9722_CR13","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B.: Online scalable algorithm for minimizing \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"},{"issue":"2","key":"9722_CR14","doi-asserted-by":"crossref","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(2), 83\u201397 (2011)","journal-title":"SIGACT News"},{"key":"9722_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":"9722_CR16","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(4), 617\u2013643 (2000)","journal-title":"J. ACM"},{"issue":"6","key":"9722_CR17","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(6), 875\u2013891 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"9722_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":"9722_CR19","doi-asserted-by":"crossref","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":"9722_CR20","unstructured":"Pruhs, K., Sgall, J., Torng, E.: Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chap. Online Scheduling. CRC press (2004)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9722-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9722-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9722-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T11:27:49Z","timestamp":1568546869000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9722-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,9]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["9722"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9722-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,9]]}}}