Skip to main content
Erschienen in: Queueing Systems 1-2/2020

20.06.2019

Admission control in a two-class loss system with periodically varying parameters and abandonments

verfasst von: Gabriel Zayas-Cabán, Mark E. Lewis

Erschienen in: Queueing Systems | Ausgabe 1-2/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Motivated by service systems, such as telephone call centers and emergency departments, we consider admission control for a two-class multi-server loss system with periodically varying parameters and customers who may abandon from service. Assuming mild conditions for the parameters, a dynamic programming formulation is developed. We show that under the infinite horizon discounted problem, there exists an optimal threshold policy and provide conditions for a customer class to be preferred for each fixed time, extending stationary results to the non-stationary setting. We approximate the non-stationary problem by discretizing the time horizon into equally spaced intervals and examine how policies for this approximation change as a function of time and parameters numerically. We compare the performance of these approximations with several admission policies used in practice in a discrete-event simulation study. We show that simpler admission policies that ignore non-stationarity or abandonments lead to significant losses in rewards.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Zurück zum Zitat Altman, E., Jiménez, T., Koole, G.: On optimal call admission control in resource-sharing system. IEEE Trans. Commun. 49(9), 1659–1668 (2001)CrossRef Altman, E., Jiménez, T., Koole, G.: On optimal call admission control in resource-sharing system. IEEE Trans. Commun. 49(9), 1659–1668 (2001)CrossRef
2.
Zurück zum Zitat Blackwell, D.: Discrete dynamic programming. Ann. Math. 33, 719–726 (1962)CrossRef Blackwell, D.: Discrete dynamic programming. Ann. Math. 33, 719–726 (1962)CrossRef
3.
Zurück zum Zitat Buyukkoc, C., Varaiya, P., Walrand, J.: The \(c\mu \)-rule revisited. Adv. Appl. Probab. 17(1), 237–238 (1985)CrossRef Buyukkoc, C., Varaiya, P., Walrand, J.: The \(c\mu \)-rule revisited. Adv. Appl. Probab. 17(1), 237–238 (1985)CrossRef
4.
Zurück zum Zitat Chavis, J.T., Cochran, A.L., Kocher, K.E., Washington, V.N., Zayas-Caban, G.: A simulation model of patient flow through the emergency department to determine the impact of a short stay unit on hospital congestion. In: Roeder, T.M.K., Frazier, P.I., Szechtman, R., Zhou, E., Huschka, T., Chick, S.E. (eds.) Proceedings of the 2016 Winter Simulation Conference, pp. 1982–1993. Institute of Electrical and Electronics Engineers Inc, Piscataway, NJ (2016)CrossRef Chavis, J.T., Cochran, A.L., Kocher, K.E., Washington, V.N., Zayas-Caban, G.: A simulation model of patient flow through the emergency department to determine the impact of a short stay unit on hospital congestion. In: Roeder, T.M.K., Frazier, P.I., Szechtman, R., Zhou, E., Huschka, T., Chick, S.E. (eds.) Proceedings of the 2016 Winter Simulation Conference, pp. 1982–1993. Institute of Electrical and Electronics Engineers Inc, Piscataway, NJ (2016)CrossRef
5.
Zurück zum Zitat Cudina, M., Ramanan, K.: Asymptotically optimal controls for time-inhomogeneous networks. SIAM J. Control Optim. 49(2), 611–645 (2011)CrossRef Cudina, M., Ramanan, K.: Asymptotically optimal controls for time-inhomogeneous networks. SIAM J. Control Optim. 49(2), 611–645 (2011)CrossRef
6.
Zurück zum Zitat Feinberg, E.A., Reiman, M.I.: Optimality of randomized trunk reservation. Probab. Eng. Inf. Sci. 8(04), 463–489 (1994)CrossRef Feinberg, E.A., Reiman, M.I.: Optimality of randomized trunk reservation. Probab. Eng. Inf. Sci. 8(04), 463–489 (1994)CrossRef
7.
Zurück zum Zitat Fischer, W., Meier-Hellstern, K.: The Markov-modulated Poisson process (MMPP) cookbook. Perform. Eval. 18(2), 149–171 (1993)CrossRef Fischer, W., Meier-Hellstern, K.: The Markov-modulated Poisson process (MMPP) cookbook. Perform. Eval. 18(2), 149–171 (1993)CrossRef
8.
Zurück zum Zitat Fu, M.C., Marcus, S.I., Wang, I.-J.: Monotone optimal policies for a transient queueing staffing problem. Oper. Res. 48(2), 327–331 (2000)CrossRef Fu, M.C., Marcus, S.I., Wang, I.-J.: Monotone optimal policies for a transient queueing staffing problem. Oper. Res. 48(2), 327–331 (2000)CrossRef
9.
Zurück zum Zitat Green, L., Kolesar, P.: The pointwise stationary approximation for queues with nonstationary arrivals. Manag. Sci. 37(1), 84–97 (1991)CrossRef Green, L., Kolesar, P.: The pointwise stationary approximation for queues with nonstationary arrivals. Manag. Sci. 37(1), 84–97 (1991)CrossRef
10.
Zurück zum Zitat Green, L.V., Kolesar, P.J.: On the accuracy of the simple peak hour approximation for Markovian queues. Manag. Sci. 41(8), 1353–1370 (1995)CrossRef Green, L.V., Kolesar, P.J.: On the accuracy of the simple peak hour approximation for Markovian queues. Manag. Sci. 41(8), 1353–1370 (1995)CrossRef
11.
Zurück zum Zitat Green, L.V., Kolesar, P.J.: The lagged PSA for estimating peak congestion in multiserver Markovian queues with periodic arrival rates. Manag. Sci. 43(1), 80–87 (1997)CrossRef Green, L.V., Kolesar, P.J.: The lagged PSA for estimating peak congestion in multiserver Markovian queues with periodic arrival rates. Manag. Sci. 43(1), 80–87 (1997)CrossRef
12.
Zurück zum Zitat Green, L.V., Kolesar, P.J.: A note on approximating peak congestion in \(M_t/G/\infty \) queues with sinusoidal arrivals. Manag. Sci. 44(11–part–2), S137–S144 (1998)CrossRef Green, L.V., Kolesar, P.J.: A note on approximating peak congestion in \(M_t/G/\infty \) queues with sinusoidal arrivals. Manag. Sci. 44(11–part–2), S137–S144 (1998)CrossRef
13.
Zurück zum Zitat Green, L.V., Kolesar, P.J., Soares, J.: Improving the SIPP approach for staffing service systems that have cyclic demands. Oper. Res. 49(4), 549–564 (2001)CrossRef Green, L.V., Kolesar, P.J., Soares, J.: Improving the SIPP approach for staffing service systems that have cyclic demands. Oper. Res. 49(4), 549–564 (2001)CrossRef
14.
Zurück zum Zitat Hampshire, R.C., Massey, W.A.: Dynamic Optimization with Applications to Dynamic Rate Queues. TUTORIALS in Operations Research, pp. 210–247. INFORMS Society, Catonsville (2010) Hampshire, R.C., Massey, W.A.: Dynamic Optimization with Applications to Dynamic Rate Queues. TUTORIALS in Operations Research, pp. 210–247. INFORMS Society, Catonsville (2010)
15.
Zurück zum Zitat Hordijk, A., Puterman, M.L.: On the convergence of policy iteration in finite state undiscounted Markov decision processes: the unichain case. Math. Oper. Res. 12(1), 163–176 (1987)CrossRef Hordijk, A., Puterman, M.L.: On the convergence of policy iteration in finite state undiscounted Markov decision processes: the unichain case. Math. Oper. Res. 12(1), 163–176 (1987)CrossRef
16.
Zurück zum Zitat Ingolfsson, A., Akhmetshina, E., Budge, S., Li, Y., Wu, X.: A survey and experimental comparison of service-level-approximation methods for nonstationary M (t)/M/s (t) queueing systems with exhaustive discipline. INFORMS J. Comput. 19(2), 201–214 (2007)CrossRef Ingolfsson, A., Akhmetshina, E., Budge, S., Li, Y., Wu, X.: A survey and experimental comparison of service-level-approximation methods for nonstationary M (t)/M/s (t) queueing systems with exhaustive discipline. INFORMS J. Comput. 19(2), 201–214 (2007)CrossRef
17.
Zurück zum Zitat Jain, A., Elmaraghy, H.: Production scheduling/rescheduling in flexible manufacturing. Int. J. Prod. Res. 35(1), 281–309 (1997)CrossRef Jain, A., Elmaraghy, H.: Production scheduling/rescheduling in flexible manufacturing. Int. J. Prod. Res. 35(1), 281–309 (1997)CrossRef
18.
Zurück zum Zitat Jaśkiewicz, A.: A fixed point approach to solve the average cost optimality equation for semi-Markov decision processes with Feller transition probabilities. Commun. Stat. Theory Methods 36(14), 2559–2575 (2007)CrossRef Jaśkiewicz, A.: A fixed point approach to solve the average cost optimality equation for semi-Markov decision processes with Feller transition probabilities. Commun. Stat. Theory Methods 36(14), 2559–2575 (2007)CrossRef
19.
Zurück zum Zitat Kim, S.-H., Whitt, W.: Are call center and hospital arrivals well modeled by nonhomogeneous Poisson processes? Manuf. Serv. Oper. Manag. 16(3), 464–480 (2014)CrossRef Kim, S.-H., Whitt, W.: Are call center and hospital arrivals well modeled by nonhomogeneous Poisson processes? Manuf. Serv. Oper. Manag. 16(3), 464–480 (2014)CrossRef
20.
Zurück zum Zitat Koole, G.: Structural results for the control of queueing systems using event-based dynamic programming. Queueing Syst. 30(3–4), 323–339 (1998)CrossRef Koole, G.: Structural results for the control of queueing systems using event-based dynamic programming. Queueing Syst. 30(3–4), 323–339 (1998)CrossRef
21.
Zurück zum Zitat Koole, G., Mandelbaum, A.: Queueing models of call centers: an introduction. Ann. Oper. Res. 113(1–4), 41–59 (2002)CrossRef Koole, G., Mandelbaum, A.: Queueing models of call centers: an introduction. Ann. Oper. Res. 113(1–4), 41–59 (2002)CrossRef
22.
Zurück zum Zitat Lewis, M.E., Ayhan, H., Foley, R.D.: Bias optimal admission control policies for a multiclass nonstationary queueing system. J. Appl. Probab. 39, 20–37 (2002)CrossRef Lewis, M.E., Ayhan, H., Foley, R.D.: Bias optimal admission control policies for a multiclass nonstationary queueing system. J. Appl. Probab. 39, 20–37 (2002)CrossRef
23.
Zurück zum Zitat Lewis, P.A.: Some results on tests for Poisson processes. Biometrika 52, 67–77 (1965)CrossRef Lewis, P.A.: Some results on tests for Poisson processes. Biometrika 52, 67–77 (1965)CrossRef
24.
Zurück zum Zitat Lippman, S.: Applying a new device in the optimization of exponential queuing systems. Oper. Res. 23(4), 687–710 (1975)CrossRef Lippman, S.: Applying a new device in the optimization of exponential queuing systems. Oper. Res. 23(4), 687–710 (1975)CrossRef
25.
Zurück zum Zitat Martin-Löf, A.: Optimal control of a continuous-time Markov chain with periodic transition probabilities. Oper. Res. 15(5), 872–881 (1967)CrossRef Martin-Löf, A.: Optimal control of a continuous-time Markov chain with periodic transition probabilities. Oper. Res. 15(5), 872–881 (1967)CrossRef
26.
Zurück zum Zitat Miller, B.L.: A queueing reward system with several customer classes. Manag. Sci. 16(3), 234–245 (1969)CrossRef Miller, B.L.: A queueing reward system with several customer classes. Manag. Sci. 16(3), 234–245 (1969)CrossRef
27.
Zurück zum Zitat Örmeci, E.L., Burnetas, A., van der Wal, J.: Admission policies for a two class loss system. Stoch. Model 17(4), 513–539 (2001)CrossRef Örmeci, E.L., Burnetas, A., van der Wal, J.: Admission policies for a two class loss system. Stoch. Model 17(4), 513–539 (2001)CrossRef
28.
Zurück zum Zitat Örmeci, E.L., van der Wal, J.: Admission policies for a two class loss system with general interarrival times. Stoch. Models 22(1), 37–53 (2006)CrossRef Örmeci, E.L., van der Wal, J.: Admission policies for a two class loss system with general interarrival times. Stoch. Models 22(1), 37–53 (2006)CrossRef
29.
Zurück zum Zitat Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Mathematical Statistics. Wiley, New York (1994)CrossRef Puterman, M.L.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Mathematical Statistics. Wiley, New York (1994)CrossRef
30.
Zurück zum Zitat Puterman, M.L., Shin, M.C.: Modified policy iteration algorithms for discounted Markov decision problems. Manag. Sci. 24(11), 1127–1137 (1978)CrossRef Puterman, M.L., Shin, M.C.: Modified policy iteration algorithms for discounted Markov decision problems. Manag. Sci. 24(11), 1127–1137 (1978)CrossRef
31.
Zurück zum Zitat Roubos, A., Bhulai, S., Koole, G.: Flexible staffing for call centers with non-stationary arrival rates In: Markov decision processes in practice, pp. 487–503. Springer, Cham (2017) Roubos, A., Bhulai, S., Koole, G.: Flexible staffing for call centers with non-stationary arrival rates In: Markov decision processes in practice, pp. 487–503. Springer, Cham (2017)
32.
Zurück zum Zitat Roubos, D., Bhulai, S.: Approximate dynamic programming techniques for the control of time-varying queuing systems applied to call centers with abandonments and retrials. Probab. Eng. Inf. Sci. 24(01), 27–45 (2010)CrossRef Roubos, D., Bhulai, S.: Approximate dynamic programming techniques for the control of time-varying queuing systems applied to call centers with abandonments and retrials. Probab. Eng. Inf. Sci. 24(01), 27–45 (2010)CrossRef
33.
Zurück zum Zitat Rowe, B.H., Channan, P., Bullard, M., Blitz, S., Saunders, L.D., Rosychuk, R.J., Lari, H., Craig, W.R., Holroyd, B.R.: Characteristics of patients who leave emergency departments without being seen. Acad. Emerg. Med. 13(8), 848–852 (2006)CrossRef Rowe, B.H., Channan, P., Bullard, M., Blitz, S., Saunders, L.D., Rosychuk, R.J., Lari, H., Craig, W.R., Holroyd, B.R.: Characteristics of patients who leave emergency departments without being seen. Acad. Emerg. Med. 13(8), 848–852 (2006)CrossRef
34.
Zurück zum Zitat Savin, S.V., Cohen, M.A., Gans, N., Katalan, Z.: Capacity management in rental businesses with two customer bases. Oper. Res. 53(4), 617–631 (2005)CrossRef Savin, S.V., Cohen, M.A., Gans, N., Katalan, Z.: Capacity management in rental businesses with two customer bases. Oper. Res. 53(4), 617–631 (2005)CrossRef
35.
Zurück zum Zitat Stidham Jr., S.: Optimal control of admission to a queueing system. IEEE Trans. Autom. Control 30(8), 705–713 (1985)CrossRef Stidham Jr., S.: Optimal control of admission to a queueing system. IEEE Trans. Autom. Control 30(8), 705–713 (1985)CrossRef
36.
Zurück zum Zitat Wakuta, K.: Arbitrary state semi-Markov decision processes. Optimization 18(3), 447–454 (1987)CrossRef Wakuta, K.: Arbitrary state semi-Markov decision processes. Optimization 18(3), 447–454 (1987)CrossRef
37.
Zurück zum Zitat Wei, Q., Guo, X.: New average optimality conditions for semi-Markov decision processes in Borel spaces. J. Optim. Theory Appl. 153(3), 709–732 (2012)CrossRef Wei, Q., Guo, X.: New average optimality conditions for semi-Markov decision processes in Borel spaces. J. Optim. Theory Appl. 153(3), 709–732 (2012)CrossRef
38.
Zurück zum Zitat Yoon, S., Lewis, M.E.: Optimal pricing and admission control in a queueing system with periodically varying parameters. Queueing Syst. 47(3), 177–199 (2004)CrossRef Yoon, S., Lewis, M.E.: Optimal pricing and admission control in a queueing system with periodically varying parameters. Queueing Syst. 47(3), 177–199 (2004)CrossRef
39.
Zurück zum Zitat Zayas-Cabán, G., Xie, J., Green, L.V., Lewis, M.E.: Dynamic control of a tandem system with abandonments. Queueing Syst. 84(3–4), 279–293 (2016)CrossRef Zayas-Cabán, G., Xie, J., Green, L.V., Lewis, M.E.: Dynamic control of a tandem system with abandonments. Queueing Syst. 84(3–4), 279–293 (2016)CrossRef
Metadaten
Titel
Admission control in a two-class loss system with periodically varying parameters and abandonments
verfasst von
Gabriel Zayas-Cabán
Mark E. Lewis
Publikationsdatum
20.06.2019
Verlag
Springer US
Erschienen in
Queueing Systems / Ausgabe 1-2/2020
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI
https://doi.org/10.1007/s11134-019-09620-3

Weitere Artikel der Ausgabe 1-2/2020

Queueing Systems 1-2/2020 Zur Ausgabe