{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T22:41:39Z","timestamp":1789512099889,"version":"build-2803163510"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,4,13]],"date-time":"2015-04-13T00:00:00Z","timestamp":1428883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["954\/11"],"award-info":[{"award-number":["954\/11"]}]},{"name":"Technion-Microsoft Electronic Commerce Research Center"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2015,5,21]]},"abstract":"<jats:p>\n            We consider a market-based resource allocation model for batch jobs in cloud computing clusters. In our model, we incorporate the importance of the due date of a job rather than the number of servers allocated to it at any given time. Each batch job is characterized by the work volume of total computing units (e.g., CPU hours) along with a bound on maximum degree of parallelism. Users specify, along with these job characteristics, their desired due date and a value for finishing the job by its deadline. Given this specification, the primary goal is to determine the\n            <jats:italic>scheduling<\/jats:italic>\n            of cloud computing instances under capacity constraints in order to maximize the social welfare (i.e., sum of values gained by allocated users). Our main result is a new (CC-k\u010bss-1)-approximation algorithm for this objective, where\n            <jats:italic>C<\/jats:italic>\n            denotes cloud capacity,\n            <jats:italic>k<\/jats:italic>\n            is the maximal bound on parallelized execution (in practical settings,\n            <jats:italic>k<\/jats:italic>\n            &lt;\n            <jats:italic>C<\/jats:italic>\n            ) and\n            <jats:italic>s<\/jats:italic>\n            is the slackness on the job completion time, that is, the minimal ratio between a specified deadline and the earliest finish time of a job. Our algorithm is based on utilizing dual fitting arguments over a strengthened linear program to the problem.\n          <\/jats:p>\n          <jats:p>\n            Based on the new approximation algorithm, we construct truthful allocation and pricing mechanisms, in which reporting the true value and other properties of the job (deadline, work volume, and the parallelism bound) is a dominant strategy for all users. To that end, we extend known results for single-value settings to provide a general framework for transforming allocation algorithms into truthful mechanisms in domains of single-value and multi-properties. We then show that the basic mechanism can be extended under proper Bayesian assumptions to the objective of maximizing revenues, which is important for public clouds. We empirically evaluate the benefits of our approach through simulations on data-center job traces, and show that the revenues obtained under our mechanism are comparable with an\n            <jats:italic>ideal<\/jats:italic>\n            fixed-price mechanism, which sets an on-demand price using oracle knowledge of users\u2019 valuations. Finally, we discuss how our model can be extended to accommodate uncertainties in job work volumes, which is a practical challenge in cloud settings.\n          <\/jats:p>","DOI":"10.1145\/2742343","type":"journal-article","created":{"date-parts":[[2015,4,14]],"date-time":"2015-04-14T12:32:19Z","timestamp":1429014739000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":53,"title":["Near-Optimal Scheduling Mechanisms for Deadline-Sensitive Jobs in Large Computing Clusters"],"prefix":"10.1145","volume":"2","author":[{"given":"Navendu","family":"Jain","sequence":"first","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ishai","family":"Menache","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"CS Department, Technion, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Yaniv","sequence":"additional","affiliation":[{"name":"CS Department, Technion, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,4,13]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Reining in the outliers in map-reduce clusters using mantri","author":"Ananthanarayanan Ganesh"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1486877.1486882"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Aaron Archer and \u00c9va Tardos. 2001. Truthful mechanisms for one-parameter agents. In FOCS. 482--491.   Aaron Archer and \u00c9va Tardos. 2001. Truthful mechanisms for one-parameter agents. In FOCS. 482--491.","DOI":"10.1109\/SFCS.2001.959924"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/502102.502107"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799354138"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00365406"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0262.2006.00695.x"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612702"},{"key":"e_1_2_1_9_1","volume-title":"Scheduling Algorithms","author":"Brucker Peter","edition":"4"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998549.1998555"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795283292"},{"key":"e_1_2_1_12_1","volume-title":"Phillips","author":"Carr Robert D.","year":"2000"},{"key":"e_1_2_1_13_1","volume-title":"Retrieved","author":"Curino Carlo","year":"2013"},{"key":"e_1_2_1_14_1","volume-title":"Palis","author":"DasGupta Bhaskar","year":"2000"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993709"},{"key":"e_1_2_1_16_1","unstructured":"Juan A. Garay Joseph Naor B\u00fclent Yener and Peng Zhao. 2002. On-line admission control and packet scheduling with interleaving. In INFOCOM.  Juan A. Garay Joseph Naor B\u00fclent Yener and Peng Zhao. 2002. On-line admission control and packet scheduling with interleaving. In INFOCOM."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1496091.1496103"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Navendu Jain Ishai Menache Joseph Naor and Jonathan Yaniv. 2011. A truthful mechanism for value-based scheduling in cloud computing. In SAGT. 178--189.   Navendu Jain Ishai Menache Joseph Naor and Jonathan Yaniv. 2011. A truthful mechanism for value-based scheduling in cloud computing. In SAGT. 178--189.","DOI":"10.1007\/978-3-642-24829-0_17"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250947"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02248588"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486187"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.1.58"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301287"},{"key":"e_1_2_1_24_1","volume-title":"Vazirani","author":"Nisan Noam","year":"2007"},{"key":"e_1_2_1_25_1","unstructured":"Cynthia A. Phillips R. N. Uma and Joel Wein. 2000. Off-line admission control for general scheduling problems. In SODA. 879--888.   Cynthia A. Phillips R. N. Uma and Joel Wein. 2000. Off-line admission control for general scheduling problems. In SODA. 879--888."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988783"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(87)90007-3"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064009.1064040"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2742343","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2742343","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:00:32Z","timestamp":1750230032000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2742343"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,13]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,5,21]]}},"alternative-id":["10.1145\/2742343"],"URL":"https:\/\/doi.org\/10.1145\/2742343","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,13]]},"assertion":[{"value":"2013-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}