Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-30T20:36:06.287Z Has data issue: false hasContentIssue false
  • English
  • Français

TWO-CLASS ROUTING WITH ADMISSION CONTROL AND STRICT PRIORITIES

Published online by Cambridge University Press:  13 June 2017

Kenneth C. Chong ,
Shane G. Henderson  and
Mark E. Lewis
Kenneth C. Chong
Affiliation:
E-mail: [email protected]
Shane G. Henderson
Affiliation:
230 Rhodes Hall, Cornell University, Ithaca, NY 14850 E-mail: [email protected]
Mark E. Lewis
Affiliation:
221 Rhodes Hall, Cornell University, Ithaca, NY 14850 E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider the problem of routing and admission control in a loss system featuring two classes of arriving jobs (high-priority and low-priority jobs) and two types of servers, in which decision-making for high-priority jobs is forced, and rewards influence the desirability of each of the four possible routing decisions. We seek a policy that maximizes expected long-run reward, under both the discounted reward and long-run average reward criteria, and formulate the problem as a Markov decision process. When the reward structure favors high-priority jobs, we demonstrate that there exists an optimal monotone switching curve policy with slope of at least −1. When the reward structure favors low-priority jobs, we demonstrate that the value function, in general, lacks structure, which complicates the search for structure in optimal policies. However, we identify conditions under which optimal policies can be characterized in greater detail. We also examine the performance of heuristic policies in a brief numerical study.

Keywords

Markov decision processesqueueing controlstochastic dynamic programmingtwo-class queue
Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 32 , Issue 2 , April 2018 , pp. 163 - 178
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Altman, E., Jimenez, T. & Koole, G. (2001). On optimal call admission control in resource-sharing system. IEEE Transactions on Communications 49(9): 1659–1668.Google Scholar
2. Bakalos, G., Mamali, M., Komninos, C., Koukou, E., Tsantilas, A., Tzima, S. & Rosenberg, T. (2011). Advanced life support versus basic life support in the pre-hospital setting: a meta-analysis. Resuscitation 82(9): 1130–1137.CrossRefGoogle ScholarPubMed
3. Bell, S.L. & Williams, R.J. (2001). Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy. The Annals of Applied Probability 11(3): 608–649.Google Scholar
4. Berman, O. (1981). Dynamic repositioning of indistinguishable service units on transportation networks. Transportation Science 15(2): 115–136.CrossRefGoogle Scholar
5. Berman, O. (1981). Repositioning of distinguishable urban service units on networks. Computers & Operations Research 8(2): 105–118.CrossRefGoogle Scholar
6. Bhulai, S. & Koole, G. (2000). A queueing model for call blending in call centers. IEEE Transactions on Automatic Control 48(8): 1434–1438.Google Scholar
7. Blanc, J.P.C., de Wall, P.R., Nain, P. & Towsley, D. (1992). Optimal control of admission to a multi-server queue with two arrival streams. IEEE Transactions on Automatic Control 37(6): 785–797.CrossRefGoogle Scholar
8. Carrizosa, E., Conde, E. & Muñoz-Márquez, M. (1998). Admission policies in loss queueing models with heterogeneous arrivals. Management Science 44(3): 311–320.Google Scholar
9. Chong, K.C., Henderson, S.G. & Lewis, M.E. (2016). The vehicle mix decision in emergency medical service systems. Manufacturing & Service Operations Management 18(3): 347–360.Google Scholar
10. Derman, C., Lieberman, G.J. & Ross, S.M. (1972). A sequential stochastic assignment problem. Management Science 18(7): 349–355.Google Scholar
11. Down, D.G. & Lewis, M.E. (2010). The N-network model with upgrades. Journal of Information Science and Engineering 24(2): 171–200.Google Scholar
12. Feinberg, E.A. & Reiman, M.I. (1994). Optimality of randomized trunk reservation. Journal of Information Science and Engineering 8(4): 463–489.Google Scholar
13. Gans, N. & Savin, S. (2007). Pricing and capacity rationing for rentals with uncertain durations. Management Science 53(3): 390–407.CrossRefGoogle Scholar
14. Gans, N. & Zhou, Y.-P. (2003). A call-routing problem with service-level constraints. Operations Research 51(2): 255–271.Google Scholar
15. Harrison, J.M. (1998). Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policies. The Annals of Applied Probability 8(3): 822–848.Google Scholar
16. Jacobs, L.M., Sinclair, A., Beiser, A. & D'agostino, R.B. (1984). Prehospital advanced life support: benefits in trauma. The Journal of Trauma 24(1): 8–12.CrossRefGoogle ScholarPubMed
17. Jarvis, J.P. (1975). Optimization in stochastic service systems with distinguishable servers. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
18. Lewis, M.E., Ayhan, H. & Foley, R.D. (1999). Bias optimality in a queue with admission control. Probability in the Engineering and Informational Sciences 13(3): 309–327.CrossRefGoogle Scholar
19. Lippman, S.A. (1975). Applying a new device in the optimization of exponential queuing systems. Operations Research 23(4): 687–710.Google Scholar
20. McLay, L.A. & Mayorga, M.E. (2013). A model for optimally dispatching ambulances to emergency calls with classification errors in patient priorities. IIE Transactions 45(1): 1–24.Google Scholar
21. Miller, B.L. (1969). A queueing reward system with several customer classes. Management Science 16(3): 234–245.CrossRefGoogle Scholar
22. Örmeci, E.L. & van der Wal, J. (2006). Admission policies for a two class loss system with general interarrival times. Stochastic Models 22(1): 37–53.Google Scholar
23. Papier, F. & Thonemann, U.W. (2010). Capacity rationing in stochastic rental systems with advance demand information. Operations Research 58(2): 274–288.Google Scholar
24. Puterman, M.L. (1994). Markov decision processes: discrete stochastic dynamic programming. Hoboken, NJ: John Wiley and Sons.Google Scholar
25. Ross, S.M. & Wu, D.T. (2013). A generalized coupon collecting model as a parsimonious optimal stochastic assignment model. Annals of Operations Research 208(1): 133–146.Google Scholar
26. Ross, S.M. & Wu, D.T. (2015). A stochastic assignment problem. Naval Research Logistics 62(1): 23–31.Google Scholar
27. Savin, S.V., Cohen, M.A., Gans, N. & Katalan, Z. (2005). Capacity management in rental businesses with two customer bases. Operations Research 53(4): 617–631.Google Scholar
28. Serfozo, R.F. (1979). Technical notean equivalence between continuous and discrete time Markov decision processes. Operations Research 27(3): 616–620.Google Scholar
29. Stidham, S. (1985). Optimal control of admission to a queueing system. IEEE Transactions on Automatic Control 30(8): 705–713.Google Scholar
30. Stidham, S. & Weber, R. (1993). A survey of Markov decision models for control of networks of queues. Queueing Systems 13: 291–314. doi: 10.1007/bf01158935. http://dx.doi.org/10.1007/BF01158935.Google Scholar
31. Zhang, L. (2012). Simulation optimisation and Markov models for dynamic ambulance redeployment. Ph.D. thesis, The University of Auckland, Auckland, New Zealand.Google Scholar
Supplementary material: PDF

Chong supplementary material

Appendix

Download Chong supplementary material(PDF)
PDF 282.1 KB