{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T13:34:39Z","timestamp":1767965679049,"version":"3.49.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T00:00:00Z","timestamp":1711929600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T00:00:00Z","timestamp":1711929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-15-IDEX-02"],"award-info":[{"award-number":["ANR-15-IDEX-02"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Oper. Res. Forum"],"DOI":"10.1007\/s43069-024-00300-4","type":"journal-article","created":{"date-parts":[[2024,4,1]],"date-time":"2024-04-01T11:01:50Z","timestamp":1711969310000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Algorithms for Scheduling Deadline-Sensitive Malleable Tasks"],"prefix":"10.1007","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3699-5241","authenticated-orcid":false,"given":"Xiaohu","family":"Wu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick","family":"Loiseau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,4,1]]},"reference":[{"key":"300_CR1","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/ALLERTON.2015.7447050","volume-title":"In: Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton)","author":"X Wu","year":"2015","unstructured":"Wu X, Loiseau P (2015) Algorithms for scheduling deadline-sensitive malleable tasks. In: Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, pp 530\u2013537"},{"key":"300_CR2","doi-asserted-by":"crossref","unstructured":"Jain N, Menache I, Naor J, Yaniv J (2011) A truthful mechanism for value-based scheduling in cloud computing. Proceedings of the 4th International Conference on Algorithmic Game Theory. SAGT\u201911. Springer-Verlag, Berlin, Heidelberg, pp 178\u2013189. https:\/\/dl.acm.org\/doi\/abs\/10.5555\/2050805.2050827","DOI":"10.1007\/978-3-642-24829-0_17"},{"key":"300_CR3","first-page":"255","volume-title":"In: Proceedings of the Twenty-fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures","author":"N Jain","year":"2012","unstructured":"Jain N, Menache I, Naor J, Yaniv J (2012) Near-optimal scheduling mechanisms for deadline-sensitive jobs in large computing clusters. In: Proceedings of the Twenty-fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures. ACM, pp 255\u2013266"},{"issue":"4","key":"300_CR4","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/s10951-018-0576-y","volume":"22","author":"V Nagarajan","year":"2019","unstructured":"Nagarajan V, Wolf J, Balmin A, Hildrum K (2019) Malleable scheduling for flows of jobs and applications to MapReduce. J Sched 22(4):393\u2013411","journal-title":"J Sched"},{"key":"300_CR5","doi-asserted-by":"crossref","unstructured":"Wu X, Loiseau P, Hyyti\u00e4 E (2019) Towards designing cost-optimal policies to utilize IaaS Clouds with Online Learning. IEEE Trans Parallel Distrib Syst","DOI":"10.1109\/TPDS.2019.2935199"},{"key":"300_CR6","first-page":"1","volume-title":"In: Proceedings of the Second International Workshop on Data Intensive Computing in the Clouds","author":"GC Fox","year":"2011","unstructured":"Fox GC (2011) Data intensive applications on clouds. In: Proceedings of the Second International Workshop on Data Intensive Computing in the Clouds. ACM, pp 1\u20132"},{"key":"300_CR7","first-page":"460","volume-title":"In: Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing (HPDC\u201910)","author":"T Gunarathne","year":"2010","unstructured":"Gunarathne T, Wu T-L, Qiu J, Fox G (2010) Cloud computing paradigms for pleasingly parallel biomedical applications. In: Proceedings of the 19th ACM International Symposium on High Performance Distributed Computing (HPDC\u201910). ACM, pp 460\u2013469"},{"issue":"1","key":"300_CR8","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF02248588","volume":"26","author":"Eugene L Lawler","year":"1990","unstructured":"Lawler Eugene L (1990) A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Ann Oper Res 26(1):125\u2013133","journal-title":"Ann Oper Res"},{"key":"300_CR9","doi-asserted-by":"crossref","unstructured":"Karger D, Stein C, Wein J (1997) Scheduling algorithms. In: CRC Handbook of Computer Science","DOI":"10.1201\/9781420049503-c36"},{"key":"300_CR10","unstructured":"Jackson JR (1955) Scheduling a production line to minimize maximum tardiness. Management Science Research Project Research Report 43, University of California, Los Angeles"},{"key":"300_CR11","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/nav.3800210113","volume":"21","author":"WA Horn","year":"1974","unstructured":"Horn WA (1974) Some simple scheduling algorithms. Nav Res Logist Q 21:177\u2013185","journal-title":"Nav Res Logist Q"},{"issue":"1","key":"300_CR12","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1287\/mnsc.16.1.77","volume":"16","author":"EL Lawler","year":"1969","unstructured":"Lawler EL, Moore JM (1969) A Functional equation and its application to resource allocation and sequencing problems. Manage Sci 16(1):77\u201384","journal-title":"Manage Sci"},{"key":"300_CR13","doi-asserted-by":"crossref","unstructured":"Stankovic JA, Spuri M, Ramamritham K, Buttazzo G (1998) Deadline scheduling for real-time systems: EDF and related algorithms. Springer New York, NY. https:\/\/link.springer.com\/book\/10.1007\/978-1-4615-5535-3","DOI":"10.1007\/978-1-4615-5535-3"},{"key":"300_CR14","first-page":"305","volume-title":"In: Proceedings of the Twenty-fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures","author":"B Lucier","year":"2013","unstructured":"Lucier B, Menache I, Naor J, Yaniv J (2013) Efficient online scheduling for deadline-sensitive jobs. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Parallelism in Algorithms and Architectures. ACM, pp 305\u2013314"},{"key":"300_CR15","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1145\/2764468.2764535","volume-title":"In: Proceedings of the Sixteenth ACM Conference on Economics and Computation","author":"Y Azar","year":"2015","unstructured":"Azar Y, Kalp-Shaltiel I, Lucier B, Menache I, Naor J, Yaniv J (2015) Truthful online scheduling with commitments. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation. ACM, pp 715\u2013732"},{"key":"300_CR16","first-page":"81","volume-title":"In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science","author":"J Sudipto Guha","year":"2004","unstructured":"Sudipto Guha J, Khanna S, Naor J (2004) Machine minimization for scheduling jobs with interval constraints. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE, pp 81\u201390"},{"key":"300_CR17","volume-title":"Fundamentals of algorithmics","author":"G Brassard","year":"1996","unstructured":"Brassard G, Bratley P (1996) Fundamentals of algorithmics. Prentice-Hall, Inc"},{"key":"300_CR18","first-page":"211","volume-title":"In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures","author":"P Bod\u00edk","year":"2014","unstructured":"Bod\u00edk P, Menache I, Naor J, Yaniv J (2014) Brief announcement: deadline-aware scheduling of big-data processing jobs. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, pp 211\u2013213"},{"key":"300_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithm","author":"DP Williamson","year":"2011","unstructured":"Williamson DP, Shmoys DB (2011) The design of approximation algorithm. Cambridge University Press"},{"issue":"12","key":"300_CR20","doi-asserted-by":"publisher","first-page":"3511","DOI":"10.1109\/TPDS.2017.2731843","volume":"28","author":"L Guo","year":"2017","unstructured":"Guo L, Shen H (2017) Efficient approximation algorithms for the bounded flexible scheduling problem in clouds. IEEE Trans Parallel Distrib Syst 28(12):3511\u20133520","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"300_CR21","volume-title":"Handbook of Scheduling: Algorithms, Models, and Performance Analysis","author":"P-F Dutot","year":"2004","unstructured":"Dutot P-F, Mouni\u00e9 G, Trystram D (2004) Scheduling parallel tasks: approximation algorithms. In: Leung JY-T (ed) Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Boca Raton"},{"key":"300_CR22","first-page":"62:1","volume-title":"In: Proceedings of the 27th Annual European Symposium on Algorithms (ESA\u201919)","author":"K Jansen","year":"2019","unstructured":"Jansen K, Rau M (2019) Closing the gap for pseudo-polynomial strip packing. In: Proceedings of the 27th Annual European Symposium on Algorithms (ESA\u201919). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, p 62:1-62:14"},{"key":"300_CR23","doi-asserted-by":"crossref","unstructured":"Jansen K, Rau M (2019) Improved approximation for two dimensional strip packing with polynomial bounded width. Theor Comput Sci","DOI":"10.1016\/j.tcs.2019.04.002"},{"issue":"04","key":"300_CR24","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1142\/S1793830911001413","volume":"3","author":"M Bougeret","year":"2011","unstructured":"Bougeret M, Dutot P-F, Jansen K, Robenek C, Trystram D (2011) Approximation algorithms for multiple strip packing and scheduling parallel jobs in platforms. Discrete Math Algorithms Appl 3(04):553\u2013586","journal-title":"Discrete Math Algorithms Appl"},{"key":"300_CR25","doi-asserted-by":"publisher","unstructured":"Jansen K, Land F (2018) Scheduling monotone moldable jobs in linear time. 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, pp 172\u2013181. https:\/\/doi.org\/10.1109\/IPDPS.2018.00027, https:\/\/ieeexplore.ieee.org\/document\/8425171","DOI":"10.1109\/IPDPS.2018.00027"},{"issue":"9","key":"300_CR26","doi-asserted-by":"publisher","first-page":"2689","DOI":"10.1109\/TPDS.2017.2675891","volume":"28","author":"R Bleuse","year":"2017","unstructured":"Bleuse R, Hunold S, Kedad-Sidhoum S, Monna F, Mouni\u00e9 G, Trystram D (2017) Scheduling independent moldable tasks on multi-cores with GPUs. IEEE Trans Parallel Distrib Syst 28(9):2689\u20132702","journal-title":"IEEE Trans Parallel Distrib Syst"},{"key":"300_CR27","unstructured":"Wu X, Loiseau P (2016) Efficient algorithms for scheduling moldable tasks. Preprint at http:\/\/arxiv.org\/abs\/1609.08588v8"},{"issue":"1","key":"300_CR28","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.ejor.2023.02.044","volume":"310","author":"X Wu","year":"2023","unstructured":"Wu X, Loiseau P (2023) Efficient approximation algorithms for scheduling moldable tasks. Eur J Oper Res 310(1):71\u201383","journal-title":"Eur J Oper Res"},{"issue":"2","key":"300_CR29","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1137\/S0097539701385995","volume":"37","author":"G Mouni\u00e9","year":"2007","unstructured":"Mouni\u00e9 G, Rapine C, Trystram D (2007) A $$\\frac{3}{2}$$-approximation algorithm for scheduling independent monotonic malleable tasks. SIAM J Comput 37(2):401\u2013412","journal-title":"SIAM J Comput"},{"key":"300_CR30","first-page":"199","volume-title":"In: Proceedings of the Thirteenth annual ACM Symposium on Parallel Algorithms and Architectures","author":"P-F Dutot","year":"2001","unstructured":"Dutot P-F, Trystram D (2001) Scheduling on hierarchical clusters using malleable tasks. In: Proceedings of the Thirteenth annual ACM Symposium on Parallel Algorithms and Architectures. ACM, pp 199\u2013208"},{"issue":"04","key":"300_CR31","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1142\/S0129054102001308","volume":"13","author":"R Lep\u00e8re","year":"2002","unstructured":"Lep\u00e8re R, Trystram D, Woeginger GJ (2002) Approximation algorithms for scheduling malleable tasks under precedence constraints. Int J Found Comput Sci 13(04):613\u2013627","journal-title":"Int J Found Comput Sci"},{"issue":"3","key":"300_CR32","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/s00453-001-0085-8","volume":"32","author":"K Jansen","year":"2002","unstructured":"Jansen K, Porkolab L (2002) Linear-time approximation schemes for scheduling malleable parallel tasks. Algorithmica 32(3):507\u2013520","journal-title":"Algorithmica"},{"key":"300_CR33","first-page":"167","volume-title":"In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"W Ludwig","year":"1994","unstructured":"Ludwig W, Tiwari P (1994) Scheduling malleable and nonmalleable parallel tasks. In: Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, pp 167\u2013179"},{"key":"300_CR34","volume-title":"Hadoop: the definitive guide","author":"T White","year":"2012","unstructured":"White T (2012) Hadoop: the definitive guide. O\u2019Reilly Media, Inc"},{"key":"300_CR35","doi-asserted-by":"crossref","unstructured":"Even G (2007) Recursive greedy methods. In: Gonzalez TF (ed) Handbook of Approximation Algorithms and Metaheuristics. CRC, Boca Raton, FL, ch. 5","DOI":"10.1201\/9781420010749.ch5"}],"container-title":["Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-024-00300-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-024-00300-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-024-00300-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T11:09:53Z","timestamp":1719918593000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-024-00300-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,1]]},"references-count":35,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2024,6]]}},"alternative-id":["300"],"URL":"https:\/\/doi.org\/10.1007\/s43069-024-00300-4","relation":{},"ISSN":["2662-2556"],"issn-type":[{"value":"2662-2556","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,1]]},"assertion":[{"value":"9 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 April 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"30"}}