nach oben

Queueing Systems

Erschienen in:

01.11.2013

Dynamic scheduling of a GI/GI/1+GI queue with multiple customer classes

verfasst von: Jeunghyun Kim, Amy R. Ward

Erschienen in: Queueing Systems | Ausgabe 2-4/2013

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider a dynamic control problem for a GI/GI/1+GI queue with multiclass customers. The customer classes are distinguished by their interarrival time, service time, and abandonment time distributions. There is a cost c _k>0 for every class k∈{1,2,…,N} customer that abandons the queue before receiving service. The objective is to minimize average cost by dynamically choosing which customer class the server should next serve each time the server becomes available (and there are waiting customers from at least two classes).

It is not possible to solve this control problem exactly, and so we formulate an approximating Brownian control problem. The Brownian control problem incorporates the entire abandonment distribution of each customer class. We solve the Brownian control problem under the assumption that the abandonment distribution for each customer class has an increasing failure rate. We then interpret the solution to the Brownian control problem as a control for the original dynamic scheduling problem. Finally, we perform a simulation study to demonstrate the effectiveness of our proposed control.

Vorheriger Artikel Abandonment versus blocking in many-server queues: asymptotic optimality in the QED regime

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!

Jetzt informieren

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!

Jetzt informieren

Nur mit Berechtigung zugänglich

Although many statements of Ito’s lemma require a twice continuously differentiable function, it follows from Problem 3.7.3 in [17] that a sufficient condition to apply Ito’s lemma is that the function is twice differentiable. See also the discussion at the end of Sect. 4.6 in [13]. This is important because the function \(\tilde{u}\) may not have a continuous second derivative, because the function g may not be continuous.

Akan, M., Ata, B., Olsen, T.L.: Congestion-based leadtime quotation for heterogeneous customers with convex-concave delay costs: optimality of a cost-balancing policy based on convex hull functions. Oper. Res. (2011, in press)

Armony, M., Ward, A.R.: Fair dynamic routing in large-scale heterogeneous-server systems. Oper. Res. 58(3), 624–637 (2010) CrossRef

Ata, B., Olsen, T.L.: Near-optimal dynamic leadtime quotation and scheduling under convex-concave customer delay costs. Oper. Res. 57(3), 753–768 (2009) CrossRef

Ata, B., Olsen, T.L.: Congestion-based leadtime quotation and pricing for revenue maximization with heterogeneous customers. Working Paper, Northwestern University, Evanston, IL (2011)

Ata, B., Rubino, M.: Dynamic control of a make-to-order parallel-server system with cancellations. Oper. Res. 57(1), 94–108 (2009) CrossRef

Ata, B., Tongarlak, M.H.: On scheduling a multiclass queue with abandonments under general delay costs. Working paper (2012)

Atar, R., Giat, C., Shimkin, N.: The \(\frac{c\mu}{\theta}\) rule for many-server queues with abandonment. Oper. Res. 58(5), 1427–1439 (2010) CrossRef

Atar, R., Giat, C., Shimkin, N.: On the asymptotic optimality of the \(\frac{c\mu}{\theta}\) rule under ergodic cost. Queueing Syst. 67(2), 127–144 (2011) CrossRef

Cox, D., Smith, W.: Queues. Methuen, London (1961)

10.

Down, D.G., Koole, G., Lewis, M.: Dynamic control of a single server system with abandonments. Queueing Syst. 67(1), 63–90 (2011) CrossRef

11.

Ghosh, A., Weerasinghe, A.: Optimal buffer size for a stochastic processing network in heavy traffic. Queueing Syst. 55, 147–159 (2007) CrossRef

12.

Harrison, J.M.: Brownian Motion and Stochastic Flow Systems, 1st edn. Wiley Series in Probability and Statistics. Wiley, New York (1985)

13.

Harrison, J.M.: Brownian models of open processing networks: canonical representation of workload. Ann. Appl. Probab. 10(1), 75–103 (2001)

14.

Harrison, J.M., Van Mieghem, J.A.: Dynamic control of Brownian networks: state space collapse and equivalent workload formulations. Ann. Appl. Probab. 7(3), 747–771 (1997) CrossRef

15.

Harrison, J.M., Zeevi, A.: Dynamic scheduling of a multiclass queue in the Halfin–Whitt heavy traffic regime. Oper. Res. 51, 243–257 (2004) CrossRef

16.

Hartman, P.: Ordinary Differential Equations. Wiley, New York (1964)

17.

Karatzas, I., Shreve, S.E.: Brownian Motion and Stochastic Calculus, 2nd edn. Graduate Texts in Mathematics, vol. 113. Springer, New York (1988) CrossRef

18.

Lee, C., Weerasinghe, A.: Convergence of a queueing system in heavy traffic with general patience-time distributions. In: Stochastic Processes and their Applications, vol. 121, pp. 2507–2552 (2011)

19.

Mandelbaum, A., Momcilovic, P.: Queues with many servers and impatient customers. Math. Oper. Res. 37(1), 41–65 (2012) CrossRef

20.

Mandelbaum, A., Stolyar, A.L.: Scheduling flexible servers with convex delay costs: heavy-traffic optimality of the generalized cμ-rule. Oper. Res. 52(6), 836–855 (2004) CrossRef

21.

Mandelbaum, A., Zeltyn, S.: Call centers with impatient customers: many-serve asymptotics of the M/M/N+G queue. Queueing Syst. 51(3/4), 361–402 (2005)

22.

Van Mieghem, J.: Dynamic scheduling with convex delay costs: the generalized cμ rule. Ann. Appl. Probab. 5(3), 809–833 (1995) CrossRef

23.

Ramanan, K., Kang, W.: Fluid limits of many-server queues with reneging. Ann. Appl. Probab. 20, 2204–2260 (2010) CrossRef

24.

Reed, J.E., Ward, A.R.: Approximating the GI/GI/1+GI queue with a nonlinear drift diffusion: hazard rate scaling in heavy traffic. Math. Oper. Res. 33(3), 606–644 (2008) CrossRef

25.

Reiman, M.I.: The heavy traffic diffusion approximation for sojourn times in Jackson networks. In: Disney, R.L., Ott, T.J. (eds.) Applied Probability-Computer Science, the Interface. Birkhauser, Boston (1982)

26.

Sigman, K.: Lecture Notes on Stochastic Modeling I (2011). Available from Karl Sigman’s web site

27.

Smith, W.: Various optimizers for single-stage production. Nav. Res. Logist. Q. 3, 59–66 (1956) CrossRef

28.

Tezcan, T., Dai, J.G.: Optimal control of parallel server systems with many servers in heavy traffic. Queueing Syst. 59, 95–134 (2008) CrossRef

29.

Tezcan, T., Dai, J.G.: Dynamic control of N-systems with many servers: asymptotic optimality of a static priority policy in heavy traffic. Oper. Res. 58(1), 94–110 (2010) CrossRef

30.

Ward, A.R., Glynn, P.W.: A diffusion approximation for a Markovian queue with reneging. Queueing Syst. 43(1/2), 103–128 (2003) CrossRef

31.

Ward, A.R., Glynn, P.W.: A diffusion approximation for a GI/GI/1 queue with balking or reneging. Queueing Syst. 50(4), 371–400 (2005) CrossRef

32.

Weber, T.: Optimal Control Theory with Applications in Economics. MIT press, Cambridge (2011)

33.

Whitt, W.: Stochastic Process Limits. Springer, New York (2002)

Titel: Dynamic scheduling of a GI/GI/1+GI queue with multiple customer classes
verfasst von: Jeunghyun Kim
Amy R. Ward
Publikationsdatum: 01.11.2013
Verlag: Springer US
Erschienen in: Queueing Systems / Ausgabe 2-4/2013
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI: https://doi.org/10.1007/s11134-012-9325-7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2-4/2013

Analysis of an $$M/M/1+G$$ M / M / 1 + G queue operated under the FCFS policy with exact admission control

Data-stories about (im)patient customers in tele-queues

Erratum to: Data-stories about (im)patient customers in tele-queues

On the time-dependent moments of Markovian queues with reneging

Abandonment versus blocking in many-server queues: asymptotic optimality in the QED regime

Introduction: queueing systems special issue on queueing systems with abandonments

Premium Partner