{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T02:48:25Z","timestamp":1777603705083,"version":"3.51.4"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T00:00:00Z","timestamp":1595376000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T00:00:00Z","timestamp":1595376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010029","name":"University of Lancaster","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100010029","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider a queueing system with<jats:italic>N<\/jats:italic>heterogeneous service facilities, in which admission and routing decisions are made when customers arrive and the objective is to maximize long-run average net rewards. For this type of problem, it is well-known that structural properties of optimal policies are difficult to prove in general and dynamic programming methods are computationally infeasible unless<jats:italic>N<\/jats:italic>is small. In the absence of an optimal policy to refer to, the Whittle index heuristic (originating from the literature on multi-armed bandit problems) is one approach which might be used for decision-making. After establishing the required indexability property, we show that the Whittle heuristic possesses certain structural properties which do not extend to optimal policies, except in some special cases. We also present results from numerical experiments which demonstrate that, in addition to being consistently strong over all parameter sets, the Whittle heuristic tends to be more robust than other heuristics with respect to the number of service facilities and the amount of heterogeneity between the facilities.<\/jats:p>","DOI":"10.1007\/s00186-020-00722-w","type":"journal-article","created":{"date-parts":[[2020,7,22]],"date-time":"2020-07-22T18:03:38Z","timestamp":1595441018000},"page":"511-543","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A conservative index heuristic for routing problems with multiple heterogeneous service facilities"],"prefix":"10.1007","volume":"92","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5485-1180","authenticated-orcid":false,"given":"Rob","family":"Shone","sequence":"first","affiliation":[]},{"given":"Vincent A.","family":"Knight","sequence":"additional","affiliation":[]},{"given":"Paul R.","family":"Harper","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,22]]},"reference":[{"key":"722_CR1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s11134-016-9484-z","volume":"83","author":"S Aalto","year":"2016","unstructured":"Aalto S, Lassila P, Osti P (2016) Whittle index approach to size-aware scheduling for time-varying channels with multiple states. Queueing Syst 83:195\u2013225","journal-title":"Queueing Syst"},{"key":"722_CR2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1057\/palgrave.jors.2601504","volume":"54","author":"PS Ansell","year":"2003","unstructured":"Ansell PS, Glazebrook KD, Kirkbride C (2003a) Generalised \u201cjoin the shortest queue\u201d policies for the dynamic routing of jobs to multi-class queues. J Oper Res Soc 54:379\u2013389","journal-title":"J Oper Res Soc"},{"key":"722_CR3","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/s001860200257","volume":"57","author":"PS Ansell","year":"2003","unstructured":"Ansell PS, Glazebrook KD, Nino-Mora J, O\u2019Keeffe M (2003b) Whittle\u2019s index policy for a multi-class queueing system with convex holding costs. Math Methods Oper Res 57:21\u201339","journal-title":"Math Methods Oper Res"},{"key":"722_CR4","doi-asserted-by":"crossref","first-page":"314","DOI":"10.1287\/opre.1070.0505","volume":"57","author":"TW Archibald","year":"2009","unstructured":"Archibald TW, Black DP, Glazebrook KD (2009) Indexability and index heuristics for a simple class of inventory routing problems. Oper Res 57:314\u2013326","journal-title":"Oper Res"},{"issue":"2","key":"722_CR5","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1017\/S0269964809000138","volume":"23","author":"NT Argon","year":"2009","unstructured":"Argon NT, Ding L, Glazebrook KD, Ziya S (2009) Dynamic routing of customers with general delay costs in a multiserver queuing system. Probab Eng Inf Sci 23(2):175\u2013203","journal-title":"Probab Eng Inf Sci"},{"issue":"7","key":"722_CR6","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1287\/mnsc.29.7.831","volume":"29","author":"CE Bell","year":"1983","unstructured":"Bell CE, Stidham S (1983) Individual versus social optimization in the allocation of customers to alternative servers. Manag Sci 29(7):831\u2013839","journal-title":"Manag Sci"},{"key":"722_CR7","volume-title":"Dynamic programming","author":"RE Bellman","year":"1957","unstructured":"Bellman RE (1957) Dynamic programming. Princeton University Press, Princeton"},{"key":"722_CR8","volume-title":"Neuro-dynamic programming","author":"DP Bertsekas","year":"1996","unstructured":"Bertsekas DP, Tsitsiklis JN (1996) Neuro-dynamic programming. Athena Scientific, Nashua"},{"key":"722_CR9","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1287\/moor.21.2.257","volume":"21","author":"D Bertsimas","year":"1996","unstructured":"Bertsimas D, Nino-Mora J (1996) Conservation laws, extended polymatroids and multi-armed bandit problems: a polyhedral approach to indexable systems. Math Oper Res 21:257\u2013306","journal-title":"Math Oper Res"},{"key":"722_CR10","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1239\/jap\/1059060891","volume":"40","author":"S Bhulai","year":"2003","unstructured":"Bhulai S, Koole G (2003) On the structure of value functions for threshold policies in queueing models. J Appl Probab 40:613\u2013622","journal-title":"J Appl Probab"},{"key":"722_CR11","doi-asserted-by":"crossref","first-page":"6614","DOI":"10.1109\/TAC.2017.2715329","volume":"62","author":"VS Borkar","year":"2017","unstructured":"Borkar VS (2017) Whittle index for partially observed binary Markov decision processes. IEEE Trans Autom Control 62:6614\u20136618","journal-title":"IEEE Trans Autom Control"},{"key":"722_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-017-2622-0","author":"VS Borkar","year":"2017","unstructured":"Borkar VS, Pattathil S (2017) Whittle indexability in egalitarian processor sharing systems (available online). Ann Oper Res. https:\/\/doi.org\/10.1007\/s10479-017-2622-0","journal-title":"Ann Oper Res"},{"key":"722_CR13","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/j.ejor.2019.12.018","volume":"284","author":"S Ford","year":"2020","unstructured":"Ford S, Atkinson MP, Glazebrook KD, Jacko P (2020) On the dynamic allocation of assets subject to failure. Eur J Oper Res 284:227\u2013239","journal-title":"Eur J Oper Res"},{"key":"722_CR14","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1111\/j.2517-6161.1979.tb01068.x","volume":"B41","author":"JC Gittins","year":"1979","unstructured":"Gittins JC (1979) Bandit processes and dynamic allocation indices. J R Stat Soc B41:148\u2013177","journal-title":"J R Stat Soc"},{"issue":"3","key":"722_CR15","doi-asserted-by":"crossref","first-page":"876","DOI":"10.1214\/10-AAP705","volume":"21","author":"KD Glazebrook","year":"2011","unstructured":"Glazebrook KD, Hodge DJ, Kirkbride C (2011) General notions of indexability for queueing control and asset management. Ann Appl Probab 21(3):876\u2013907","journal-title":"Ann Appl Probab"},{"issue":"4","key":"722_CR16","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1287\/opre.1080.0632","volume":"57","author":"KD Glazebrook","year":"2009","unstructured":"Glazebrook KD, Kirkbride C, Ouenniche J (2009) Index policies for the admission control and routing of impatient customers to heterogeneous service stations. Oper Res 57(4):975\u2013989","journal-title":"Oper Res"},{"issue":"5","key":"722_CR17","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/s10951-013-0325-1","volume":"17","author":"KD Glazebrook","year":"2014","unstructured":"Glazebrook KD, Hodge DJ, Kirkbride C, Minty RJ (2014) Stochastic scheduling: a short history of index policies and new approaches to index generation for dynamic resource allocation. J Sched 17(5):407\u2013425","journal-title":"J Sched"},{"key":"722_CR18","doi-asserted-by":"crossref","first-page":"916","DOI":"10.2307\/3213605","volume":"20","author":"W Grassmann","year":"1983","unstructured":"Grassmann W (1983) The convexity of the mean queue size of the M\/M\/c queue with respect to the traffic intensity. J Appl Probab 20:916\u2013919","journal-title":"J Appl Probab"},{"key":"722_CR19","volume-title":"Fundamentals of queueing theory","author":"D Gross","year":"1998","unstructured":"Gross D, Harris C (1998) Fundamentals of queueing theory. Wiley, New York"},{"key":"722_CR20","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1287\/opre.45.1.42","volume":"45","author":"A Ha","year":"1997","unstructured":"Ha A (1997) Optimal dynamic scheduling policy for a make-to-stock production system. Oper Res 45:42\u201353","journal-title":"Oper Res"},{"key":"722_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0359-0","volume-title":"To queue or not to queue: equilibrium behavior in queueing systems","author":"R Hassin","year":"2003","unstructured":"Hassin R, Haviv M (2003) To queue or not to queue: equilibrium behavior in queueing systems. Kluwer Academic Publishers, Norwell"},{"issue":"4","key":"722_CR22","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1016\/j.orl.2006.09.005","volume":"35","author":"M Haviv","year":"2007","unstructured":"Haviv M, Roughgarden T (2007) The price of anarchy in an exponential multi-server. Oper Res Lett 35(4):421\u2013426","journal-title":"Oper Res Lett"},{"issue":"4","key":"722_CR23","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/s11134-011-9217-2","volume":"67","author":"DJ Hodge","year":"2011","unstructured":"Hodge DJ, Glazebrook KD (2011) Dynamic resource allocation in a multi-product make-to-stock production system. Queueing Syst 67(4):333\u2013364","journal-title":"Queueing Syst"},{"issue":"4","key":"722_CR24","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1017\/S0269964800001777","volume":"4","author":"A Hordijk","year":"1990","unstructured":"Hordijk A, Koole G (1990) On the optimality of the generalised shortest queue policy. Probab Eng Inf Sci 4(4):477\u2013487","journal-title":"Probab Eng Inf Sci"},{"issue":"4","key":"722_CR25","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1017\/S0269964800002692","volume":"6","author":"A Hordijk","year":"1992","unstructured":"Hordijk A, Koole G (1992) On the assignment of customers to parallel queues. Probab Eng Inf Sci 6(4):495\u2013511","journal-title":"Probab Eng Inf Sci"},{"key":"722_CR26","volume-title":"Dynamic programming and markov processes","author":"R Howard","year":"1960","unstructured":"Howard R (1960) Dynamic programming and markov processes. MIT Press, Cambridge"},{"key":"722_CR27","doi-asserted-by":"crossref","unstructured":"Hsu Y-P (2018) Age of information: whittle index for scheduling stochastic arrivals. In: Proceedings of the 2018 IEEE international symposium on information theory (ISIT), Vail, CO","DOI":"10.1109\/ISIT.2018.8437712"},{"key":"722_CR28","doi-asserted-by":"crossref","first-page":"1052","DOI":"10.1239\/jap\/1354716657","volume":"49","author":"E Hyytia","year":"2012","unstructured":"Hyytia E, Aalto S, Penttinen A, Virtamo J (2012) On the value function of the $$M\/G\/1$$, FCFS and LCFS queues. J Appl Probab 49:1052\u20131071","journal-title":"J Appl Probab"},{"issue":"1","key":"722_CR29","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.ejor.2013.04.003","volume":"230","author":"VA Knight","year":"2013","unstructured":"Knight VA, Harper PR (2013) Selfish routing in public services. Eur J Oper Res 230(1):122\u2013132","journal-title":"Eur J Oper Res"},{"key":"722_CR30","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1057\/s41274-016-0100-8","volume":"68","author":"VA Knight","year":"2017","unstructured":"Knight VA, Komenda I, Griffiths JD (2017) Measuring the price of anarchy in critical care unit interactions. J Oper Res Soc 68:630\u2013642","journal-title":"J Oper Res Soc"},{"key":"722_CR31","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1239\/jap\/1032374764","volume":"36","author":"G Koole","year":"1999","unstructured":"Koole G, Sparaggis PD, Towsley D (1999) Minimizing response times and queue lengths in systems of parallel queues. J Appl Probab 36:1185\u20131193","journal-title":"J Appl Probab"},{"key":"722_CR32","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1109\/9.45156","volume":"35","author":"KR Krishnan","year":"1990","unstructured":"Krishnan KR (1990) Joining the right queue: a state-dependent decision rule. IEEE Trans Autom Control 35:104\u2013108","journal-title":"IEEE Trans Autom Control"},{"issue":"6","key":"722_CR33","doi-asserted-by":"crossref","first-page":"3812","DOI":"10.1109\/TNET.2016.2562564","volume":"24","author":"M Larranaga","year":"2016","unstructured":"Larranaga M, Ayesta U, Verloop IM (2016) Dynamic control of birth-and-death restless bandits: application to resource-allocation problems. IEEE\/ACM Trans Netw 24(6):3812\u20133825","journal-title":"IEEE\/ACM Trans Netw"},{"key":"722_CR34","doi-asserted-by":"crossref","first-page":"920","DOI":"10.2307\/3213606","volume":"20","author":"HL Lee","year":"1983","unstructured":"Lee HL, Cohen AM (1983) A note on the convexity of performance measures of M\/M\/c queueing systems. J Appl Probab 20:920\u2013923","journal-title":"J Appl Probab"},{"issue":"2","key":"722_CR35","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1111\/poms.13105","volume":"29","author":"D Li","year":"2020","unstructured":"Li D, Ding L, Connor S (2020) When to switch? Index policies for resource scheduling in emergency response. Prod Oper Manag 29(2):241\u2013262","journal-title":"Prod Oper Manag"},{"issue":"4","key":"722_CR36","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1287\/opre.23.4.687","volume":"23","author":"SA Lippman","year":"1975","unstructured":"Lippman SA (1975) Applying a new device in the optimisation of exponential queueing systems. Oper Res 23(4):687\u2013710","journal-title":"Oper Res"},{"key":"722_CR37","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1007\/BF01159224","volume":"9","author":"R Menich","year":"1991","unstructured":"Menich R, Serfozo R (1991) Optimality of shortest-queue routing for dependent service stations. Queueing Syst 9:403\u2013418","journal-title":"Queueing Syst"},{"key":"722_CR38","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1017\/S0001867800010648","volume":"33","author":"J Nino-Mora","year":"2001","unstructured":"Nino-Mora J (2001) Restless bandits, partial conservation laws and indexability. Adv Appl Probab 33:76\u201398","journal-title":"Adv Appl Probab"},{"issue":"3","key":"722_CR39","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/s10107-002-0362-6","volume":"93","author":"J Nino-Mora","year":"2002","unstructured":"Nino-Mora J (2002) Dynamic allocation indices for restless projects and queueing admission control: a polyhedral approach. Math Program 93(3):361\u2013413","journal-title":"Math Program"},{"key":"722_CR40","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/j.ejor.2012.02.033","volume":"220","author":"J Nino-Mora","year":"2012","unstructured":"Nino-Mora J (2012) Towards minimum loss job routing to parallel heterogeneous multiserver queues via index policies. Eur J Oper Res 220:705\u2013715","journal-title":"Eur J Oper Res"},{"key":"722_CR41","doi-asserted-by":"crossref","DOI":"10.1002\/9780470182963","volume-title":"Approximate dynamic programming: solving the curses of dimensionality","author":"WB Powell","year":"2007","unstructured":"Powell WB (2007) Approximate dynamic programming: solving the curses of dimensionality. Wiley, New York"},{"key":"722_CR42","doi-asserted-by":"crossref","DOI":"10.1002\/9780470316887","volume-title":"Markov decision processes\u2014discrete stochastic dynamic programming","author":"ML Puterman","year":"1994","unstructured":"Puterman ML (1994) Markov decision processes\u2014discrete stochastic dynamic programming. Wiley, New York"},{"key":"722_CR43","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1111\/1467-9574.00040","volume":"51","author":"SAE Sassen","year":"1997","unstructured":"Sassen SAE, Tijms HC, Nobel RD (1997) A heuristic rule for routing customers to parallel servers. Stat Neerl 51:107\u2013121","journal-title":"Stat Neerl"},{"issue":"3","key":"722_CR44","doi-asserted-by":"crossref","first-page":"616","DOI":"10.1287\/opre.27.3.616","volume":"27","author":"R Serfozo","year":"1979","unstructured":"Serfozo R (1979) An equivalence between continuous and discrete time Markov decision processes. Oper Res 27(3):616\u2013620","journal-title":"Oper Res"},{"key":"722_CR45","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1057\/jors.2015.98","volume":"67","author":"R Shone","year":"2016","unstructured":"Shone R, Knight VA, Harper PR, Williams JE, Minty J (2016) Containment of socially optimal policies in multiple-facility Markovian queueing systems. J Oper Res Soc 67:629\u2013643","journal-title":"J Oper Res Soc"},{"key":"722_CR46","volume-title":"Reinforcement learning: an introduction","author":"R Sutton","year":"1998","unstructured":"Sutton R, Barto A (1998) Reinforcement learning: an introduction. MIT Press, Cambridge"},{"key":"722_CR47","doi-asserted-by":"crossref","first-page":"406","DOI":"10.2307\/3213411","volume":"15","author":"RR Weber","year":"1978","unstructured":"Weber RR (1978) On the optimal assignment of customers to parallel servers. J Appl Probab 15:406\u2013413","journal-title":"J Appl Probab"},{"issue":"1","key":"722_CR48","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1287\/opre.34.1.55","volume":"34","author":"W Whitt","year":"1986","unstructured":"Whitt W (1986) Deciding which queue to join: some counterexamples. Oper Res 34(1):55\u201362","journal-title":"Oper Res"},{"key":"722_CR49","doi-asserted-by":"crossref","first-page":"287","DOI":"10.2307\/3214163","volume":"25","author":"P Whittle","year":"1988","unstructured":"Whittle P (1988) Restless bandits: activity allocation in a changing world. J Appl Probab 25:287\u2013298","journal-title":"J Appl Probab"},{"key":"722_CR50","doi-asserted-by":"crossref","first-page":"181","DOI":"10.2307\/3213271","volume":"14","author":"W Winston","year":"1977","unstructured":"Winston W (1977) Optimality of the shortest line discipline. J Appl Probab 14:181\u2013189","journal-title":"J Appl Probab"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-020-00722-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-020-00722-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-020-00722-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,10]],"date-time":"2024-08-10T15:24:31Z","timestamp":1723303471000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-020-00722-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,22]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["722"],"URL":"https:\/\/doi.org\/10.1007\/s00186-020-00722-w","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"value":"1432-2994","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,22]]},"assertion":[{"value":"10 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}