{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:11Z","timestamp":1759638371478,"version":"3.41.0"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_55","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"755-776","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Scheduling Parallelizable Jobs Online to Maximize Throughput"],"prefix":"10.1007","author":[{"given":"Kunal","family":"Agrawal","sequence":"first","affiliation":[]},{"given":"Jing","family":"Li","sequence":"additional","affiliation":[]},{"given":"Kefu","family":"Lu","sequence":"additional","affiliation":[]},{"given":"Benjamin","family":"Moseley","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"55_CR1","unstructured":"OpenMP: OpenMP Application Program Interface v4.0, July 2013. http:\/\/www.openmp.org\/mp-documents\/OpenMP4.0.0.pdf"},{"key":"55_CR2","unstructured":"Intel: Intel CilkPlus, September 2013. https:\/\/www.cilkplus.org\/"},{"key":"55_CR3","volume-title":"Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism","author":"J Reinders","year":"2010","unstructured":"Reinders, J.: Intel Threading Building Blocks: Outfitting C++ for Multi-core Processor Parallelism. O\u2019Reilly Media, Inc., Sebastopol (2010)"},{"key":"55_CR4","volume-title":"A Parallel Programming with Microsoft Visual C++: Design Patterns for Decomposition and Coordination on Multicore Architectures","author":"C Campbell","year":"2011","unstructured":"Campbell, C., Miller, A.: A Parallel Programming with Microsoft Visual C++: Design Patterns for Decomposition and Coordination on Multicore Architectures. Microsoft Press, Redmond (2011)"},{"issue":"2","key":"55_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF00365406","volume":"4","author":"SK Baruah","year":"1992","unstructured":"Baruah, S.K., Koren, G., Mao, D., Mishra, B., Raghunathan, A., Rosier, L.E., Shasha, D., Wang, F.: On the competitiveness of on-line real-time task scheduling. Real-Time Syst. 4(2), 125\u2013144 (1992)","journal-title":"Real-Time Syst."},{"key":"55_CR6","doi-asserted-by":"crossref","unstructured":"Baruah, S.K., Koren, G., Mishra, B., Raghunathan, A., Rosier, L.E., Shasha, D., Wang, F.: On-line scheduling in the presence of overload. In: Symposium on Foundations of Computer Science, pp. 100\u2013110 (1991)","DOI":"10.1109\/SFCS.1991.185354"},{"issue":"2","key":"55_CR7","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1137\/S0097539792236882","volume":"24","author":"G Koren","year":"1995","unstructured":"Koren, G., Shasha, D.: Dover: an optimal on-line scheduling algorithm for overloaded uniprocessor real-time systems. SIAM J. Comput. 24(2), 318\u2013339 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"55_CR8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/0304-3975(94)90150-3","volume":"130","author":"GJ Woeginger","year":"1994","unstructured":"Woeginger, G.J.: On-line scheduling of jobs with fixed start and end times. Theor. Comput. Sci. 130(1), 5\u201316 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"55_CR9","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s004530010034","volume":"28","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., Pruhs, K.: Fault-tolerant real-time scheduling. Algorithmica 28(1), 125\u2013144 (2000)","journal-title":"Algorithmica"},{"issue":"1&2","key":"55_CR10","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/0304-3975(94)90165-1","volume":"128","author":"G Koren","year":"1994","unstructured":"Koren, G., Shasha, D.: MOCA: a multiprocessor on-line competitive algorithm for real-time system scheduling. Theor. Comput. Sci. 128(1&2), 75\u201397 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"55_CR11","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202\u2013208 (1985)","journal-title":"Commun. ACM"},{"issue":"4","key":"55_CR12","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":"4","key":"55_CR13","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/s00453-009-9321-4","volume":"59","author":"N Bansal","year":"2011","unstructured":"Bansal, N., Chan, H.-L., Pruhs, K.: Competitive algorithms for due date scheduling. Algorithmica 59(4), 569\u2013582 (2011)","journal-title":"Algorithmica"},{"key":"55_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/978-3-642-15369-3_27","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"K Pruhs","year":"2010","unstructured":"Pruhs, K., Stein, C.: How to schedule when you have to buy your energy. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX\/RANDOM 2010. LNCS, vol. 6302, pp. 352\u2013365. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15369-3_27"},{"key":"55_CR15","doi-asserted-by":"crossref","unstructured":"Im, S., Moseley, B.: General profit scheduling and the power of migration on heterogeneous machines. In: Symposium on Parallelism in Algorithms and Architectures (2016)","DOI":"10.1145\/2935764.2935771"},{"key":"55_CR16","doi-asserted-by":"crossref","unstructured":"Lucier, B., Menache, I., Naor, J., Yaniv, J.: Efficient online scheduling for deadline-sensitive jobs: extended abstract. In: 25th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2013, pp. 305\u2013314 (2013)","DOI":"10.1145\/2486159.2486187"},{"issue":"12","key":"55_CR17","doi-asserted-by":"publisher","first-page":"3242","DOI":"10.1109\/TPDS.2013.2297919","volume":"25","author":"A Saifullah","year":"2014","unstructured":"Saifullah, A., Ferry, D., Li, J., Agrawal, K., Lu, C., Gill, C.D.: Parallel real-time scheduling of dags. IEEE Trans. Parallel Distrib. Syst. 25(12), 3242\u20133252 (2014)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"55_CR18","doi-asserted-by":"crossref","unstructured":"Li, J., Chen, J.-J., Agrawal, K., Lu, C., Gill, C.D., Saifullah, A.: Analysis of federated and global scheduling for parallel real-time tasks. In: ECRTS 2014, pp. 85\u201396 (2014)","DOI":"10.1109\/ECRTS.2014.23"},{"key":"55_CR19","doi-asserted-by":"crossref","unstructured":"Agrawal, K., He, Y., Hsu, W.J., Leiserson, C.E.: Adaptive task scheduling with parallelism feedback. In: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP) (2006)","DOI":"10.1145\/1122971.1122988"},{"key":"55_CR20","doi-asserted-by":"crossref","unstructured":"Agrawal, K., He, Y., Leiserson, C.E.: Adaptive work stealing with parallelism feedback. In: Proceedings of the Annual ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), March 2007","DOI":"10.1145\/1229428.1229448"},{"key":"55_CR21","doi-asserted-by":"crossref","unstructured":"He, Y., Hsu, W.-J., Leiserson, C.E.: Provably efficient online non-clairvoyant adaptive scheduling. In: IPDPS (2007)","DOI":"10.1109\/IPDPS.2007.370303"},{"key":"55_CR22","doi-asserted-by":"crossref","unstructured":"Ma, L., Chamberlain, R.D., Agrawal, K.: Performance modeling for highly-threaded many-core GPUs. In: Proceedings of the International Conference on Application-Specific Systems, Architectures and Processors (ASAP), pp. 84\u201391, June 2014","DOI":"10.1109\/ASAP.2014.6868641"},{"key":"55_CR23","doi-asserted-by":"crossref","unstructured":"Agrawal, K., Li, J., Lu, K., Moseley, B.: Scheduling parallel DAG jobs online to minimize average flow time. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 176\u2013189 (2016)","DOI":"10.1137\/1.9781611974331.ch14"},{"key":"55_CR24","unstructured":"Robert, J., Schabanel, N.: Non-clairvoyant scheduling with precedence constraints. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 491\u2013500 (2008)"},{"key":"55_CR25","doi-asserted-by":"crossref","unstructured":"Baruah, S.: Improved multiprocessor global schedulability analysis of sporadic DAG task systems. In: 26th Euromicro Conference on Real-Time Systems, ECRTS 2014, Madrid, Spain, 8\u201311 July 2014, pp. 97\u2013105 (2014)","DOI":"10.1109\/ECRTS.2014.22"},{"key":"55_CR26","doi-asserted-by":"crossref","unstructured":"Baruah, S.: Federated scheduling of sporadic DAG task systems. In: 2015 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2015, Hyderabad, India, 25\u201329 May 2015, pp. 179\u2013186 (2015)","DOI":"10.1109\/IPDPS.2015.33"},{"key":"55_CR27","doi-asserted-by":"crossref","unstructured":"Baruah, S.: The federated scheduling of systems of conditional sporadic DAG tasks. In: 2015 International Conference on Embedded Software, EMSOFT 2015, Amsterdam, Netherlands, 4\u20139 October 2015, pp. 1\u201310 (2015)","DOI":"10.1109\/EMSOFT.2015.7318254"},{"key":"55_CR28","doi-asserted-by":"crossref","unstructured":"Baruah, S., Bonifaci, V., Marchetti-Spaccamela, A.: The global EDF scheduling of systems of conditional sporadic DAG tasks. In: 27th Euromicro Conference on Real-Time Systems, ECRTS 2015, pp. 222\u2013231 (2015)","DOI":"10.1109\/ECRTS.2015.27"},{"key":"55_CR29","doi-asserted-by":"crossref","unstructured":"Baruah, S.: The federated scheduling of constrained-deadline sporadic DAG task systems. In: Proceedings of the 2015 Design, Automation & Test in Europe Conference & Exhibition, DATE 2015, pp. 1323\u20131328 (2015)","DOI":"10.7873\/DATE.2015.0200"},{"key":"55_CR30","unstructured":"Li, J., Agrawal, K., Lu, C., Gill, C.: Analysis of global EDF for parallel tasks. In: ECRTS (2013)"},{"key":"55_CR31","doi-asserted-by":"crossref","unstructured":"Bonifaci, V., Marchetti-Spaccamela, A., Stiller, S., Wiese, A.: Feasibility analysis in the sporadic DAG task model. In: ECRTS (2013)","DOI":"10.1109\/ECRTS.2013.32"},{"key":"55_CR32","doi-asserted-by":"crossref","unstructured":"Svensson, O.: Conditional hardness of precedence constrained scheduling on identical machines. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 745\u2013754 (2010)","DOI":"10.1145\/1806689.1806791"}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_55","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:30:19Z","timestamp":1751481019000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}