{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T22:46:26Z","timestamp":1777675586289,"version":"3.51.4"},"reference-count":38,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T00:00:00Z","timestamp":1559433600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of High Performance Computing Applications"],"published-print":{"date-parts":[[2020,3]]},"abstract":"<jats:p>This article discusses scheduling strategies for the problem of maximizing the expected number of tasks that can be executed on a cloud platform within a given budget and under a deadline constraint. The execution times of tasks follow independent and identically distributed probability laws. The main questions are how many processors to enroll and whether and when to interrupt tasks that have been executing for some time. We provide complexity results and an asymptotically optimal strategy for the problem instance with discrete probability distributions and without deadline. We extend the latter strategy for the general case with continuous distributions and a deadline and we design an efficient heuristic which is shown to outperform standard approaches when running simulations for a variety of useful distribution laws.<\/jats:p>","DOI":"10.1177\/1094342019852135","type":"journal-article","created":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T23:59:52Z","timestamp":1559519992000},"page":"246-264","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":12,"title":["Scheduling independent stochastic tasks under deadline and budget constraints"],"prefix":"10.1177","volume":"34","author":[{"given":"Louis-Claude","family":"Canon","sequence":"first","affiliation":[{"name":"FEMTO-ST, Universit\u00e9 de Bourgogne Franche-Comt\u00e9, France"},{"name":"Univ Lyon, ENSL, UCBL, CNRS, Inria, LIP, LYON Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aur\u00e9lie Kong Win","family":"Chang","sequence":"additional","affiliation":[{"name":"Univ Lyon, ENSL, UCBL, CNRS, Inria, LIP, LYON Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2361-055X","authenticated-orcid":false,"given":"Yves","family":"Robert","sequence":"additional","affiliation":[{"name":"Univ Lyon, ENSL, UCBL, CNRS, Inria, LIP, LYON Cedex, France"},{"name":"University of Tennessee, Knoxville, TN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0663-6152","authenticated-orcid":false,"given":"Fr\u00e9d\u00e9ric","family":"Vivien","sequence":"additional","affiliation":[{"name":"Univ Lyon, ENSL, UCBL, CNRS, Inria, LIP, LYON Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2019,6,2]]},"reference":[{"key":"bibr1-1094342019852135","doi-asserted-by":"crossref","unstructured":"Abrishami S, Naghibzadeh M, Epema DH (2013) Deadline-constrained workflow scheduling algorithms for infrastructure as a service clouds. Future Generation Computer Systems 29(1): 158\u2013169. Available at: http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0167739X12001008. Including Special section: AIRCC-NetCoM 2009 and Special section: Clouds and Service-Oriented Architectures.","DOI":"10.1016\/j.future.2012.05.004"},{"key":"bibr2-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2006.45"},{"key":"bibr3-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/eScience.2016.7870894"},{"key":"bibr4-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-10-6620-7_16"},{"key":"bibr5-1094342019852135","volume-title":"Real-time Systems, Architecture, Scheduling, and Application","author":"Buttazzo G","year":"2012"},{"key":"bibr6-1094342019852135","doi-asserted-by":"crossref","unstructured":"Byun EK, Kee YS, Kim JS, et al. (2011) Cost optimized provisioning of elastic resources for application workflows. Future Generation Computer Systems 27(8): 1011\u20131026. Available at: http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0167739X11000744","DOI":"10.1016\/j.future.2011.05.001"},{"key":"bibr7-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2013.238"},{"key":"bibr8-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2018.00014"},{"key":"bibr9-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/CAHPC.2018.8645931"},{"key":"bibr10-1094342019852135","doi-asserted-by":"crossref","unstructured":"Canon LC, Chang AKW, Vivien F, et al. (2018b) Code for scheduling independent stochastic tasks under deadline and budget constraints. DOI: 10.6084\/m9.figshare.6463223.v2.","DOI":"10.1109\/CAHPC.2018.8645931"},{"key":"bibr11-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15277-1_17"},{"key":"bibr12-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/12.57057"},{"key":"bibr13-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.257"},{"key":"bibr14-1094342019852135","unstructured":"Feitelson D (2014) Workload Modeling for Computer Systems Performance Evaluation. Cambridge: Cambridge University Press.\n                      Version\n                      1.0.3, pp. 1\u2013607."},{"key":"bibr15-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/RTA.1993.263112"},{"key":"bibr16-1094342019852135","volume-title":"Optimal Stopping and Applications","author":"Ferguson TS","year":"2008"},{"key":"bibr17-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/CODES-ISSS.2013.6659018"},{"key":"bibr18-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55195-6_1"},{"key":"bibr19-1094342019852135","doi-asserted-by":"crossref","unstructured":"Hassan H, Sim\u00f3 J, Crespo A (2001) Flexible real-time mobile robotic architecture based on behavioural models. Engineering Applications of Artificial Intelligence 14(5): 685\u2013702. Available at: http:\/\/www.sciencedirect.com\/science\/article\/pii\/S095219760100029X","DOI":"10.1016\/S0952-1976(01)00029-X"},{"key":"bibr20-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/Grid.2012.19"},{"key":"bibr21-1094342019852135","unstructured":"Jumel F, Simonot-Lion F (2003) Management of anytime tasks in real time applications. In: XIV Workshop on Supervising and Diagnostics of Machining Systems, Karpacz\/Pologne. Available at: https:\/\/hal.inria.fr\/inria-00099612. Colloque avec actes et comit\u00e9 de lecture. internationale"},{"key":"bibr22-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/RTTAS.2004.1317271"},{"key":"bibr23-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-3956-8_8"},{"key":"bibr24-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1177\/1094342010369114"},{"key":"bibr25-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2012.38"},{"key":"bibr26-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2015.01.004"},{"key":"bibr27-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/GRID.2010.5697966"},{"key":"bibr28-1094342019852135","volume-title":"IPDPS","author":"Meng J","year":"2009"},{"key":"bibr29-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2426-4"},{"key":"bibr30-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/CloudCom.2010.32"},{"key":"bibr31-1094342019852135","doi-asserted-by":"crossref","unstructured":"Oprescu AM, Kielmann T, Leahu H (2011) Budget estimation and control for bag-of-tasks scheduling in clouds. Parallel Processing Letters 21(02): 219\u2013243. Available at: https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626411000175","DOI":"10.1142\/S0129626411000175"},{"key":"bibr32-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/UCC.2012.23"},{"key":"bibr33-1094342019852135","first-page":"858","author":"Poola D","year":"2014","journal-title":"AINA"},{"key":"bibr34-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0922-3"},{"key":"bibr35-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1007\/s10723-015-9359-2"},{"key":"bibr36-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/CLOUD.2011.14"},{"key":"bibr37-1094342019852135","doi-asserted-by":"crossref","unstructured":"Vecchiola C, Calheiros RN, Karunamoorthy D, et al. (2012) Deadline-driven provisioning of resources for scientific applications in hybrid clouds with Aneka. Future Generation Computer Systems 28(1): 58\u201365. Available at: http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0167739X11000896","DOI":"10.1016\/j.future.2011.05.008"},{"key":"bibr38-1094342019852135","doi-asserted-by":"publisher","DOI":"10.1109\/TCC.2014.2358220"}],"container-title":["The International Journal of High Performance Computing Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342019852135","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/1094342019852135","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/1094342019852135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T08:15:55Z","timestamp":1777450555000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/1094342019852135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,2]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["10.1177\/1094342019852135"],"URL":"https:\/\/doi.org\/10.1177\/1094342019852135","relation":{},"ISSN":["1094-3420","1741-2846"],"issn-type":[{"value":"1094-3420","type":"print"},{"value":"1741-2846","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,2]]}}}