{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:33:38Z","timestamp":1740123218241,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T00:00:00Z","timestamp":1649289600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T00:00:00Z","timestamp":1649289600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CMMI-1938909","CSR-1763701"],"award-info":[{"award-number":["CMMI-1938909","CSR-1763701"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Queueing Syst"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Optimal scheduling in single-server queueing systems is a classic problem in queueing theory. The Gittins index policy is known to be the optimal nonanticipating policy minimizing the mean delay in the M\/G\/1 queue. While the Gittins index is thoroughly characterized for ordinary jobs whose state is described by the attained service, it is not at all the case with jobs that have more complex structure. Recently, a class of such jobs, multistage jobs, were introduced, and it was shown that the computation of Gittins index of a multistage job decomposes into separable computations for the individual stages. The characterization is, however, indirect in the sense that it relies on the recursion for an auxiliary function (the so-called SJP\u2014single-job profit\u2014function) and not for the Gittins index itself. In this paper, we focus on sequential multistage jobs, which have a fixed sequence of stages, and prove that, for them, it is possible to compute the Gittins index directly by recursively combining the Gittins indices of its individual stages. In addition, we give sufficient conditions for the optimality of the FCFS and SERPT disciplines for scheduling sequential multistage jobs. On the other hand, we demonstrate that, for nonsequential multistage jobs, it is better to compute the Gittins index by utilizing the SJP functions.<\/jats:p>","DOI":"10.1007\/s11134-022-09760-z","type":"journal-article","created":{"date-parts":[[2022,4,7]],"date-time":"2022-04-07T07:02:54Z","timestamp":1649314974000},"page":"353-371","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the Gittins index for multistage jobs"],"prefix":"10.1007","volume":"102","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1040-4095","authenticated-orcid":false,"given":"Samuli","family":"Aalto","sequence":"first","affiliation":[]},{"given":"Ziv","family":"Scully","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,7]]},"reference":[{"key":"9760_CR1","doi-asserted-by":"crossref","unstructured":"Aalto, S.: Characterization of the Gittins index for sequential multistage jobs. arXiv:2103.10646v1 (2021)","DOI":"10.1007\/s11134-022-09760-z"},{"key":"9760_CR2","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s11134-009-9141-x","volume":"63","author":"S Aalto","year":"2009","unstructured":"Aalto, S., Ayesta, U., Righter, R.: On the Gittins index in the M\/G\/1 queue. Queueing Syst. 63, 437\u2013458 (2009)","journal-title":"Queueing Syst."},{"key":"9760_CR3","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1017\/S0269964811000015","volume":"25","author":"S Aalto","year":"2011","unstructured":"Aalto, S., Ayesta, U., Righter, R.: Properties of the Gittins index with application to optimal scheduling. Probab. Eng. Inf. Sci. 25, 269\u2013288 (2011)","journal-title":"Probab. Eng. Inf. Sci."},{"key":"9760_CR4","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1017\/S0269964802164047","volume":"16","author":"H-S Ahn","year":"2002","unstructured":"Ahn, H.-S., Duenyas, I., Lewis, M.E.: The optimal control of a two-stage tandem queueing system with flexible servers. Probab. Eng. Inf. Sci. 16, 453\u2013469 (2002)","journal-title":"Probab. Eng. Inf. Sci."},{"key":"9760_CR5","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1239\/aap\/1158684995","volume":"38","author":"H-S Ahn","year":"2006","unstructured":"Ahn, H.-S., Righter, R.: Dynamic load balancing with flexible workers. Adv. Appl. Probab. 38, 621\u2013642 (2006)","journal-title":"Adv. Appl. Probab."},{"key":"9760_CR6","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1287\/opre.46.2.218","volume":"46","author":"I Duenyas","year":"1998","unstructured":"Duenyas, I., Gupta, D., Olsen, T.: Control of a single server tandem queueing system with setups. Oper. Res. 46, 218\u2013230 (1998)","journal-title":"Oper. Res."},{"key":"9760_CR7","volume-title":"Multi-armed Bandit Allocation Indices","author":"J Gittins","year":"1989","unstructured":"Gittins, J.: Multi-armed Bandit Allocation Indices. Wiley, New York (1989)"},{"key":"9760_CR8","doi-asserted-by":"publisher","DOI":"10.1002\/9780470980033","volume-title":"Multi-armed Bandit Allocation Indices","author":"J Gittins","year":"2011","unstructured":"Gittins, J., Glazebrook, K., Weber, R.: Multi-armed Bandit Allocation Indices, 2nd edn. Wiley, New York (2011)","edition":"2"},{"key":"9760_CR9","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1023\/A:1019181124314","volume":"26","author":"SMR Iravani","year":"1997","unstructured":"Iravani, S.M.R., Posner, M.J.M., Buzacott, J.A.: A two-stage tandem queue attended by a moving server with holding and switching costs. Queueing Syst. 26, 203\u2013228 (1997)","journal-title":"Queueing Syst."},{"key":"9760_CR10","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1080\/07362998808809149","volume":"6","author":"PK Johri","year":"1988","unstructured":"Johri, P.K., Katehakis, M.N.: Scheduling service in tandem queues attended by a single server. Stoch. Anal. Appl. 6, 279\u2013288 (1988)","journal-title":"Stoch. Anal. Appl."},{"key":"9760_CR11","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1287\/opre.16.3.687","volume":"16","author":"L Schrage","year":"1968","unstructured":"Schrage, L.: A proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 16, 687\u2013690 (1968)","journal-title":"Oper. Res."},{"key":"9760_CR12","doi-asserted-by":"crossref","unstructured":"Scully, Z., Harchol-Balter, M.: The Gittins policy in the M\/G\/1 queue. In: Proceedings of WiOpt (2021)","DOI":"10.23919\/WiOpt52861.2021.9589051"},{"key":"9760_CR13","doi-asserted-by":"crossref","unstructured":"Scully, Z., Harchol-Balter, M., Scheller-Wolf, A.: Optimal scheduling and exact response time analysis for multistage jobs. arXiv:1805.06865v2 (2018)","DOI":"10.1145\/3179419"},{"key":"9760_CR14","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1287\/opre.26.1.197","volume":"26","author":"D Smith","year":"1978","unstructured":"Smith, D.: A new proof of the optimality of the shortest remaining processing time discipline. Oper. Res. 26, 197\u2013199 (1978)","journal-title":"Oper. Res."},{"key":"9760_CR15","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1080\/07408170108936871","volume":"33","author":"MP Van Oyen","year":"2001","unstructured":"Van Oyen, M.P., Gel, E.G.S., Hopp, W.J.: Performance opportunity for workforce agility in collaborative and noncollaborative work systems. IIE Trans. 33, 761\u2013777 (2001)","journal-title":"IIE Trans."},{"key":"9760_CR16","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1287\/opre.50.1.227.17792","volume":"50","author":"P Whittle","year":"2002","unstructured":"Whittle, P.: Applied probability in Great Britain. Oper. Res. 50, 227\u2013239 (2002)","journal-title":"Oper. Res."},{"key":"9760_CR17","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1239\/jap\/1127322025","volume":"42","author":"P Whittle","year":"2005","unstructured":"Whittle, P.: Tax problems in the undiscounted case. J. Appl. Probab. 42, 754\u2013765 (2005)","journal-title":"J. Appl. Probab."}],"container-title":["Queueing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-022-09760-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11134-022-09760-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11134-022-09760-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,4]],"date-time":"2022-11-04T14:10:31Z","timestamp":1667571031000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11134-022-09760-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,7]]},"references-count":17,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["9760"],"URL":"https:\/\/doi.org\/10.1007\/s11134-022-09760-z","relation":{},"ISSN":["0257-0130","1572-9443"],"issn-type":[{"type":"print","value":"0257-0130"},{"type":"electronic","value":"1572-9443"}],"subject":[],"published":{"date-parts":[[2022,4,7]]},"assertion":[{"value":"22 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 April 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}