{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T18:17:09Z","timestamp":1769019429018,"version":"3.49.0"},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,6,28]],"date-time":"2016-06-28T00:00:00Z","timestamp":1467072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1409130, CCF-1008065, CCF-1115575, CNS-1253218"],"award-info":[{"award-number":["CCF-1409130, CCF-1008065, CCF-1115575, CNS-1253218"]}]},{"name":"IBM Faculty Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2016,6,28]]},"abstract":"<jats:p>\n            We introduce a scheduling algorithm Intermediate-SRPT, and show that it is\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>P<\/jats:italic>\n            )-competitive with respect to average flow time when scheduling jobs whose parallelizability is intermediate between being fully parallelizable and sequential. Here, the parameter\n            <jats:italic>P<\/jats:italic>\n            denotes the ratio between the maximum job size to the minimum. We also show a general matching lower bound on the competitive ratio. Our analysis builds on an interesting combination of potential function and local competitiveness arguments.\n          <\/jats:p>","DOI":"10.1145\/2938378","type":"journal-article","created":{"date-parts":[[2016,7,19]],"date-time":"2016-07-19T11:59:22Z","timestamp":1468929562000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Competitively Scheduling Tasks with Intermediate Parallelizability"],"prefix":"10.1145","volume":"3","author":[{"given":"Sungjin","family":"Im","sequence":"first","affiliation":[{"name":"University of California, Merced, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[{"name":"Washington University in St. Louis, St. Louis, MO"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kirk","family":"Pruhs","sequence":"additional","affiliation":[{"name":"University of Pittsburgh, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Torng","sequence":"additional","affiliation":[{"name":"Michigan State University, East Lansing, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7,18]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"http:\/\/www.tilera.com\/.  http:\/\/www.tilera.com\/."},{"key":"e_1_2_1_2_1","unstructured":"http:\/\/projects.csail.mit.edu\/angstrom\/.  http:\/\/projects.csail.mit.edu\/angstrom\/."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9349-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00186-3"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00738-7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229163.2229172"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627885"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998037.1998058"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347479"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.10.018"},{"key":"e_1_2_1_11_1","volume-title":"Intel\u2019s big shift after hitting technical wall. New York Times (17","author":"Markoff John","year":"2004","unstructured":"John Markoff . 2004. Intel\u2019s big shift after hitting technical wall. New York Times (17 May 2004 ). John Markoff. 2004. Intel\u2019s big shift after hitting technical wall. New York Times (17 May 2004)."},{"key":"e_1_2_1_12_1","volume-title":"CPU designers debate multi-core future. EE Times (6","author":"Merritt Rick","year":"2008","unstructured":"Rick Merritt . 2008. CPU designers debate multi-core future. EE Times (6 February 2008 ). Rick Merritt. 2008. CPU designers debate multi-core future. EE Times (6 February 2008)."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0068-9"},{"key":"e_1_2_1_14_1","volume-title":"Workshop on Approximation and Online Algorithms, WAOA. 237--248","author":"Pruhs Kirk","year":"2010","unstructured":"Kirk Pruhs , Julien Robert , and Nicolas Schabanel . 2010 . Minimizing maximum flowtime of jobs with arbitrary parallelizability . In Workshop on Approximation and Online Algorithms, WAOA. 237--248 . Kirk Pruhs, Julien Robert, and Nicolas Schabanel. 2010. Minimizing maximum flowtime of jobs with arbitrary parallelizability. In Workshop on Approximation and Online Algorithms, WAOA. 237--248."},{"key":"e_1_2_1_15_1","unstructured":"Kirk Pruhs Jiri Sgall and Eric Torng. 2004. Handbook of Scheduling: Algorithms Models and Performance Analysis. Chapter Online Scheduling.  Kirk Pruhs Jiri Sgall and Eric Torng. 2004. Handbook of Scheduling: Algorithms Models and Performance Analysis. Chapter Online Scheduling."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778648"},{"key":"e_1_2_1_17_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms, SODA. 491--500","author":"Robert Julien","year":"2008","unstructured":"Julien Robert and Nicolas Schabanel . 2008 . Non-clairvoyant scheduling with precedence constraints . In ACM-SIAM Symposium on Discrete Algorithms, SODA. 491--500 . Julien Robert and Nicolas Schabanel. 2008. Non-clairvoyant scheduling with precedence constraints. In ACM-SIAM Symposium on Discrete Algorithms, SODA. 491--500."}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2938378","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2938378","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:38:20Z","timestamp":1750282700000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2938378"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,28]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,6,28]]}},"alternative-id":["10.1145\/2938378"],"URL":"https:\/\/doi.org\/10.1145\/2938378","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6,28]]},"assertion":[{"value":"2014-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}