{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T10:49:45Z","timestamp":1673434185271},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher"},{"name":"National Science Foundation","award":["CMMI-1938909, XPS-1629444, CSR-1763701"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2020,11,30]]},"abstract":"The Gittins scheduling policy minimizes the mean response in the single-server M\/G\/1 queue in a wide variety of settings. Most famously, Gittins is optimal when preemption is allowed and service requirements are unknown but drawn from a known distribution. Gittins is also optimal much more generally, adapting to any amount of available information and any preemption restrictions. However, scheduling to minimize mean response time in a multiserver setting, specifically the central-queue M\/G\/k, is a much more difficult problem. In this work we give the first general analysis of Gittins in the M\/G\/k. Specifically, we show that under extremely general conditions, Gittins's mean response time in the M\/G\/k is at most its mean response time in the M\/G\/1 plus an $O(\u0142og(1\/(1 - \u03c1)))$ additive term, where \u03c1 is the system load. A consequence of this result is that Gittins is heavy-traffic optimal in the M\/G\/k if the service requirement distribution S satisfies $\\mathbfE [S^2(\u0142og S)^+] < \\infty$. This is the most general result on minimizing mean response time in the M\/G\/k to date. To prove our results, we combine properties of the Gittins policy and Palm calculus in a novel way. Notably, our technique overcomes the limitations of tagged job methods that were used in prior scheduling analyses.<\/jats:p>","DOI":"10.1145\/3428328","type":"journal-article","created":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T19:54:15Z","timestamp":1606766055000},"page":"1-29","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["The Gittins Policy is Nearly Optimal in the M\/G\/k under Extremely General Conditions"],"prefix":"10.1145","volume":"4","author":[{"given":"Ziv","family":"Scully","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Isaac","family":"Grosof","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]},{"given":"Mor","family":"Harchol-Balter","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-009-9141-x"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964811000015"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2786385.2786389"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01149192"},{"key":"e_1_2_1_5_1","volume-title":"Gittins index, and its calculation. Methods and applications of statistics in clinical trials: Planning, analysis, and inferential methods 2","author":"Chakravorty Jhelum","year":"2014","unstructured":"Jhelum Chakravorty and Aditya Mahajan . 2014. Multi-armed bandits , Gittins index, and its calculation. Methods and applications of statistics in clinical trials: Planning, analysis, and inferential methods 2 ( 2014 ), 416--435. Jhelum Chakravorty and Aditya Mahajan. 2014. Multi-armed bandits, Gittins index, and its calculation. Methods and applications of statistics in clinical trials: Planning, analysis, and inferential methods 2 (2014), 416--435."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102408341"},{"key":"e_1_2_1_7_1","volume-title":"Multi-armed Bandit Allocation Indices","author":"Gittins John C.","unstructured":"John C. Gittins , Kevin D. Glazebrook , and Richard Weber . 2011. Multi-armed Bandit Allocation Indices . John Wiley & Sons . John C. Gittins, Kevin D. Glazebrook, and Richard Weber. 2011. Multi-armed Bandit Allocation Indices. John Wiley & Sons."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001860300278"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2777408.2777418"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3305218.3305223"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2462638"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428328"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1870178.1870183"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00296"},{"key":"e_1_2_1_15_1","volume-title":"11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs))","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher . 2020. Scheduling with Predictions and the Price of Misprediction . In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs)) , Thomas Vidick (Ed.), Vol. 151 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany , 14:1--14:18. Michael Mitzenmacher. 2020. Scheduling with Predictions and the Price of Misprediction. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs)), Thomas Vidick (Ed.), Vol. 151. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 14:1--14:18."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189231"},{"key":"e_1_2_1_17_1","volume-title":"Optimal Stopping and Free-Boundary Problems","author":"Peskir Goran","unstructured":"Goran Peskir and Albert Shiryaev . 2006. Optimal Stopping and Free-Boundary Problems . Springer . Goran Peskir and Albert Shiryaev. 2006. Optimal Stopping and Free-Boundary Problems. Springer."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3439602.3439615"},{"key":"e_1_2_1_19_1","unstructured":"Ziv Scully Mor Harchol-Balter and Alan Scheller-Wolf. 2018. Optimal Scheduling and Exact Response Time Analysis for Multistage Jobs. (2018). arXiv:1805.06865 Ziv Scully Mor Harchol-Balter and Alan Scheller-Wolf. 2018. Optimal Scheduling and Exact Response Time Analysis for Multistage Jobs. (2018). arXiv:1805.06865"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3179419"},{"key":"e_1_2_1_21_1","volume-title":"Optimal Stopping Rules","author":"Shiryaev Albert","unstructured":"Albert Shiryaev . 2007. Optimal Stopping Rules . Vol. 8 . Springer . Albert Shiryaev. 2007. Optimal Stopping Rules. Vol. 8. Springer."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177005588"},{"key":"e_1_2_1_23_1","series-title":"Series B (Methodological)","volume-title":"Multi-armed bandits and the Gittins index. Journal of the Royal Statistical Society","author":"Whittle Peter","year":"1980","unstructured":"Peter Whittle . 1980. Multi-armed bandits and the Gittins index. Journal of the Royal Statistical Society . Series B (Methodological) ( 1980 ), 143--149. Peter Whittle. 1980. Multi-armed bandits and the Gittins index. Journal of the Royal Statistical Society. Series B (Methodological) (1980), 143--149."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.30.2.223"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3428328","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T22:10:04Z","timestamp":1672611004000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3428328"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,30]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,11,30]]}},"alternative-id":["10.1145\/3428328"],"URL":"http:\/\/dx.doi.org\/10.1145\/3428328","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":["Computer Networks and Communications","Hardware and Architecture","Safety, Risk, Reliability and Quality","Computer Science (miscellaneous)"],"published":{"date-parts":[[2020,11,30]]},"assertion":[{"value":"2021-06-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}