{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T10:57:28Z","timestamp":1649156248402},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2016,6]]},"abstract":"<jats:p> In this paper, we consider optimal scheduling algorithms for scientific workows with two typical structures, fork&amp;join and tree, on a set of provisioned (virtual) machines under budget and deadline constraints in cloud computing. First, given a total budget B, by leveraging a bi-step dynamic programming technique, we propose optimal algorithms in pseudo-polynomial time for both workows with minimum scheduling length as a goal. Our algorithms are efficient if the total budget B is polynomially bounded by the number of jobs in respective workows, which is usually the common case in practice. Second, we consider the dual of this optimization problem to minimize the cost when the deadline of the computation D is fixed. We change this problem into the standard multiple-choice knapsack problem via a parallel transformation. <\/jats:p>","DOI":"10.1142\/s0129626416500092","type":"journal-article","created":{"date-parts":[[2016,6,7]],"date-time":"2016-06-07T05:54:09Z","timestamp":1465278849000},"page":"1650009","source":"Crossref","is-referenced-by-count":2,"title":["On Optimal Scheduling Algorithms for Well-Structured Workflows in the Cloud with Budget and Deadline Constraints"],"prefix":"10.1142","volume":"26","author":[{"given":"Yang","family":"Wang","sequence":"first","affiliation":[{"name":"Center for Cloud Computing, Shenzhen Institute of Advanced Technology, Chinese Academy of Science, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Shi","sequence":"additional","affiliation":[{"name":"Faculty of Business and I.T., University of Ontario Institute of Technology, Oshawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kenneth B.","family":"Kent","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, University of New Brunswick, Fredericton, NB, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2016,6,7]]},"reference":[{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920881"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024000426962"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1145\/1734160.1734166"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1007\/s10723-012-9207-6"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.994"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1461"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00015-I"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1145\/356004.356006"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.3.503"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1145\/1084805.1084814"},{"issue":"9","key":"p_29","first-page":"1884","volume":"24","author":"Zhang Yanfeng","year":"2013","journal-title":"IEEE Transactions on"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626416500092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:17:46Z","timestamp":1565137066000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626416500092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6]]},"references-count":11,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2016,6,7]]},"published-print":{"date-parts":[[2016,6]]}},"alternative-id":["10.1142\/S0129626416500092"],"URL":"https:\/\/doi.org\/10.1142\/s0129626416500092","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"value":"0129-6264","type":"print"},{"value":"1793-642X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,6]]}}}