{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T02:10:24Z","timestamp":1740103824107,"version":"3.37.3"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,8,7]],"date-time":"2018-08-07T00:00:00Z","timestamp":1533600000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2019,8]]},"DOI":"10.1007\/s10951-018-0576-y","type":"journal-article","created":{"date-parts":[[2018,8,7]],"date-time":"2018-08-07T10:50:20Z","timestamp":1533639020000},"page":"393-411","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Malleable scheduling for flows of jobs and applications to MapReduce"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9514-5581","authenticated-orcid":false,"given":"Viswanath","family":"Nagarajan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joel","family":"Wolf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrey","family":"Balmin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kirsten","family":"Hildrum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,7]]},"reference":[{"issue":"4","key":"576_CR1","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1137\/0209064","volume":"9","author":"B Baker","year":"1980","unstructured":"Baker, B., Coffman, E., & Rivest, R. (1980). Orthogonal packings in two dimensions. SIAM Journal on Computing, 9(4), 846\u2013855.","journal-title":"SIAM Journal on Computing"},{"key":"576_CR2","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1016\/j.jpdc.2010.12.004","volume":"71","author":"J Berlinska","year":"2011","unstructured":"Berlinska, J., & Drozdowski, M. (2011). Scheduling divisible MapReduce computations. Journal of Parallel and Distributed Computing, 71, 450\u2013459.","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"12","key":"576_CR3","doi-asserted-by":"crossref","first-page":"1272","DOI":"10.14778\/3402755.3402761","volume":"4","author":"K Beyer","year":"2011","unstructured":"Beyer, K., Ercegovac, V., Gemulla, R., Balmin, A., Eltabakh, M., Kanne, C.-C., et al. (2011). Jaql: A scripting language for large scale semistructured data analysis. Proceedings of VLDB, 4(12), 1272\u20131283.","journal-title":"Proceedings of VLDB"},{"issue":"8","key":"576_CR4","doi-asserted-by":"publisher","first-page":"1479","DOI":"10.1109\/TPDS.2012.258","volume":"24","author":"C-Y Chen","year":"2013","unstructured":"Chen, C.-Y., & Chu, C.-P. (2013). A 3.42-approximation algorithm for scheduling malleable tasks under precedence constraints. IEEE Transactions on Parallel and Distributed Systems, 24(8), 1479\u20131488.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"issue":"4","key":"576_CR5","doi-asserted-by":"publisher","first-page":"808","DOI":"10.1137\/0209062","volume":"9","author":"E Coffman","year":"1980","unstructured":"Coffman, E., Garey, M., Johnson, D., & Tarjan, R. (1980). Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing, 9(4), 808\u2013826.","journal-title":"SIAM Journal on Computing"},{"doi-asserted-by":"crossref","unstructured":"Daitch, S. I., & Spielman, D. A. (2008) Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th annual ACM symposium on theory of computing (pp. 451\u2013460).","key":"576_CR6","DOI":"10.1145\/1374376.1374441"},{"issue":"1","key":"576_CR7","first-page":"107","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., & Ghemawat, S. (2008). Mapreduce: Simplified data processing on large clusters. ACM Transactions on Computer Systems, 51(1), 107\u2013113.","journal-title":"ACM Transactions on Computer Systems"},{"issue":"1","key":"576_CR8","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0020-0190(95)00174-3","volume":"57","author":"M Drozdowski","year":"1996","unstructured":"Drozdowski, M. (1996). Real-time scheduling of linear speedup parallel tasks. Information Processing Letters, 57(1), 35\u201340.","journal-title":"Information Processing Letters"},{"issue":"4","key":"576_CR9","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/jos.76","volume":"4","author":"M Drozdowski","year":"2001","unstructured":"Drozdowski, M. (2001). New applications of the Munz and Coffman algorithm. Journal of Scheduling, 4(4), 209\u2013223.","journal-title":"Journal of Scheduling"},{"key":"576_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84882-310-5","volume-title":"Scheduling for parallel processing","author":"M Drozdowski","year":"2009","unstructured":"Drozdowski, M. (2009). Scheduling for parallel processing. Heidelberg: Springer."},{"key":"576_CR11","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1023\/A:1018964732122","volume":"90","author":"M Drozdowski","year":"1999","unstructured":"Drozdowski, M., & Kubiak, W. (1999). Scheduling parallel tasks with sequential heads and tails. Annals of Operations Research, 90, 221\u2013246.","journal-title":"Annals of Operations Research"},{"issue":"2","key":"576_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s101070100238","volume":"91","author":"L Fleischer","year":"2002","unstructured":"Fleischer, L., & Wayne, K. (2002). Fast and simple approximation schemes for generalized flow. Mathematical Programming, 91(2), 215\u2013238.","journal-title":"Mathematical Programming"},{"unstructured":"Fotakis, D., Milis, I., Papadigenopoulos, O., Vassalos, V. & Zois, G. (2016). Scheduling MapReduce jobs under multi-round precedences. In Euro-Par 2016: Parallel processing\u201422nd international conference on parallel and distributed computing (pp. 209\u2013222).","key":"576_CR13"},{"issue":"2","key":"576_CR14","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/0204015","volume":"4","author":"M Garey","year":"1975","unstructured":"Garey, M., & Graham, R. (1975). Bounds for multiprocessor scheduling with resource constraints. SIAM Journal on Computing, 4(2), 187\u2013200.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"576_CR15","doi-asserted-by":"publisher","first-page":"1414","DOI":"10.14778\/1687553.1687568","volume":"2","author":"A Gates","year":"2009","unstructured":"Gates, A., Natkovich, O., Chopra, S., Kamath, P., Narayanamurthy, S., Olston, C., et al. (2009). Building a high-level dataflow system on top of MapReduce: The pig experience. Proceedings of VLDB, 2(2), 1414\u20131425.","journal-title":"Proceedings of VLDB"},{"issue":"9","key":"576_CR16","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1002\/j.1538-7305.1966.tb01709.x","volume":"45","author":"RL Graham","year":"1966","unstructured":"Graham, R. L. (1966). Bounds for certain multiprocessing anomalies. Bell System Technical Journal, 45(9), 1563\u20131581.","journal-title":"Bell System Technical Journal"},{"issue":"1","key":"576_CR17","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/s10878-012-9498-3","volume":"27","author":"E G\u00fcnther","year":"2014","unstructured":"G\u00fcnther, E., K\u00f6nig, F. G., & Megow, N. (2014). Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width. Journal of Combinatorial Optimization, 27(1), 164\u2013181.","journal-title":"Journal of Combinatorial Optimization"},{"issue":"3","key":"576_CR18","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"DS Hochbaum","year":"1986","unstructured":"Hochbaum, D. S., & Shmoys, D. B. (1986). A unified approach to approximation algorithms for bottleneck problems. Journal of the ACM, 33(3), 533\u2013550.","journal-title":"Journal of the ACM"},{"issue":"4","key":"576_CR19","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O. H., & Kim, C. E. (1975). Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4), 463\u2013468.","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Islam, M., Huang, A., Battisha, M., Chiang, M., Srinivasan, S., Peters, C., et al. (2012) Oozie: Towards a scalable workflow management system for Hadoop. In Proceedings of the ACM workshop on scalable workflow execution engines and technologies.","key":"576_CR20","DOI":"10.1145\/2443416.2443420"},{"issue":"3","key":"576_CR21","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1145\/1159892.1159899","volume":"2","author":"K Jansen","year":"2006","unstructured":"Jansen, K., & Zhang, H. (2006). An approximation algorithm for scheduling malleable tasks under general precedence constraints. ACM Transactions on Algorithms, 2(3), 416\u2013434.","journal-title":"ACM Transactions on Algorithms"},{"issue":"1","key":"576_CR22","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.jcss.2011.04.003","volume":"78","author":"K Jansen","year":"2012","unstructured":"Jansen, K., & Zhang, H. (2012). Scheduling malleable tasks with precedence constraints. Journal of Computer and System Sciences, 78(1), 245\u2013259.","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"576_CR23","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1145\/347476.347479","volume":"47","author":"B Kalyanasundaram","year":"2000","unstructured":"Kalyanasundaram, B., & Pruhs, K. (2000). Speed is as powerful as clairvoyance. Journal of the ACM, 47(4), 617\u2013643.","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"Karloff, H., Suri, S., & Vassilvitskii, S. (2010) A model of computation for MapReduce. In SODA (pp. 938\u2013948).","key":"576_CR24","DOI":"10.1137\/1.9781611973075.76"},{"doi-asserted-by":"crossref","unstructured":"Koutris, P., & Suciu, D. (2011) Parallel evaluation of conjunctive queries. In PODS (pp. 223\u2013234).","key":"576_CR25","DOI":"10.1145\/1989284.1989310"},{"key":"576_CR26","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/B978-0-12-566780-7.50020-9","volume-title":"Progress in combinatorial optimization","author":"J Labetoulle","year":"1984","unstructured":"Labetoulle, J., Lawler, E., Lentra, J., & Rinnoy Kan, A. (1984). Preemptive scheduling of uniform machines subject to release dates. In W. Pulleyblank (Ed.), Progress in combinatorial optimization (pp. 245\u2013261). New York: Academic Press."},{"doi-asserted-by":"crossref","unstructured":"Lep\u00e9re, R., Trystram, D., & Woeginger, G. J. (2001) Approximation algorithms for scheduling malleable tasks under precedence constraints. In ESA (pp. 146\u2013157).","key":"576_CR27","DOI":"10.1007\/3-540-44676-1_12"},{"key":"576_CR28","doi-asserted-by":"crossref","DOI":"10.1201\/9780203489802","volume-title":"Handbook of scheduling","author":"J Leung","year":"2004","unstructured":"Leung, J. (2004). Handbook of scheduling. London: Chapman and Hall\/CRC."},{"unstructured":"Ludwig, W., & Tiwari, P. (1994). Scheduling malleable and nonmalleable parallel tasks. In Symposium on discrete algorithms, Arlington, VA (pp. 167\u2013176).","key":"576_CR29"},{"issue":"1","key":"576_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/mnsc.6.1.1","volume":"6","author":"R McNaughton","year":"1959","unstructured":"McNaughton, R. (1959). Scheduling with deadlines and loss functions. Management Science, 6(1), 1\u201312.","journal-title":"Management Science"},{"doi-asserted-by":"crossref","unstructured":"Moseley, B., Dasgupta, A., Kumar, R., & Sarl\u00f3s, T. (2011). On scheduling in map-reduce and flow-shops. In Symposium on parallel algorithms and architectures. San Jose, CA.","key":"576_CR31","DOI":"10.1145\/1989493.1989540"},{"doi-asserted-by":"crossref","unstructured":"Nagarajan, V., Wolf, J., Balmin, A., & Hildrum, K. (2013) Flowflex: Malleable scheduling for flows of MapReduce jobs. In International middleware conference, Beijing, China (pp. 103\u2013122).","key":"576_CR32","DOI":"10.1007\/978-3-642-45065-5_6"},{"key":"576_CR33","volume-title":"Scheduling: Theory, algorithms and systems","author":"M Pinedo","year":"1995","unstructured":"Pinedo, M. (1995). Scheduling: Theory, algorithms and systems. London: Prentice Hall."},{"doi-asserted-by":"crossref","unstructured":"Popescu, A., Ercegovac, V., Balmin, A., Branco, M., & Ailamaki, A. (2012) Same queries, different data: Can we predict runtime performance? In International conference in data engineering, Washington, DC (pp. 275\u2013280).","key":"576_CR34","DOI":"10.1109\/ICDEW.2012.66"},{"issue":"1\u20132","key":"576_CR35","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/S0304-3975(98)00157-1","volume":"237","author":"P Schuurman","year":"2000","unstructured":"Schuurman, P., & Woeginger, G. J. (2000). A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem. Theoretical Computer Science, 237(1\u20132), 105\u2013122.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"576_CR36","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1137\/S0097539795286831","volume":"28","author":"U Schwiegelshohn","year":"1999","unstructured":"Schwiegelshohn, U., Ludwig, W., Wolf, J., Turek, J., & Yu, P. (1999). Smart SMART bounds for weighted response time scheduling. SIAM Journal on Computing, 28(1), 237\u2013253.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"576_CR37","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0020-0190(80)90121-0","volume":"10","author":"D Sleator","year":"1980","unstructured":"Sleator, D. (1980). A 2.5 times optimal algorithm for packing in two dimensions. Information Processing Letters, 10(1), 37\u201340.","journal-title":"Information Processing Letters"},{"doi-asserted-by":"crossref","unstructured":"Thusoo, A., Sarma, J., Jain, N., Shao, Z., Chakka, P., Zhang, N., Anthony, S., Liu, H., & Murthy, R. (2010) Hive\u2014A petabyte scale data warehouse using Hadoop. In International conference on data engineering, Long Beach, CA (pp. 996\u20131005).","key":"576_CR38","DOI":"10.1109\/ICDE.2010.5447738"},{"doi-asserted-by":"crossref","unstructured":"Turek, J., Wolf, J., & Yu, P. (1992) Approximate algorithms for scheduling parallelizable tasks. In Symposium on parallel algorithms and architectures, San Diego, CA (pp. 323\u2013332).","key":"576_CR39","DOI":"10.1145\/140901.141909"},{"issue":"3","key":"576_CR40","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/0041-5553(82)90143-4","volume":"22","author":"V Vizing","year":"1982","unstructured":"Vizing, V. (1982). Minimization of the maximum delay in servicing systems with interruption. USSR Computational Mathematics and Methematical Physics, 22(3), 227\u2013233.","journal-title":"USSR Computational Mathematics and Methematical Physics"},{"doi-asserted-by":"crossref","unstructured":"Wolf, J., Rajan, D., Hildrum, K., Khandekar, R., Kumar, R., Parekh, S., et al. (2010) FLEX: A slot allocation scheduling optimizer for MapReduce workloads. In International middleware conference, Bangalore, India (pp. 1\u201320).","key":"576_CR41","DOI":"10.1007\/978-3-642-16955-7_1"},{"issue":"5","key":"576_CR42","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00778-012-0279-5","volume":"21","author":"J Wolf","year":"2012","unstructured":"Wolf, J., Balmin, A., Rajan, D., Hildrum, K., Khandekar, R., Parekh, S., et al. (2012). On the optimization of schedules for MapReduce workloads in the presence of shared scans. VLDB Journal, 21(5), 589\u2013609.","journal-title":"VLDB Journal"},{"unstructured":"Zaharia, M., Borthakur, D., Sarma, J., Elmeleegy, K., Schenker, S., & Stoica, I. (2009) Job scheduling for multi-user MapReduce clusters. UC Berkeley technical report EECS-2009-55.","key":"576_CR43"},{"doi-asserted-by":"crossref","unstructured":"Zaharia, M., Borthakur, D., Sarma, J., Elmeleegy, K., Shenker, S., & Stoica, I. (2010) Delay scheduling: A simple technique for achieving locality and fairness in cluster scheduling. In European conference on computer systems, Paris (pp. 265\u2013278).","key":"576_CR44","DOI":"10.1145\/1755913.1755940"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-018-0576-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10951-018-0576-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-018-0576-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,28]],"date-time":"2022-08-28T21:37:09Z","timestamp":1661722629000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10951-018-0576-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,7]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8]]}},"alternative-id":["576"],"URL":"https:\/\/doi.org\/10.1007\/s10951-018-0576-y","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"type":"print","value":"1094-6136"},{"type":"electronic","value":"1099-1425"}],"subject":[],"published":{"date-parts":[[2018,8,7]]},"assertion":[{"value":"7 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}