SpringerLink
Log in

Stability analysis of N-model systems under a static priority rule

  • Published:
Queueing Systems Aims and scope Submit manuscript

Abstract

We consider the stability of N-model systems that consist of two customer classes and two server pools. Servers in one of the pools can serve both classes, but those in the other pool can serve only one of the classes. The standard fluid models in general are not sufficient to establish the stability region of these systems under static priority policies. Therefore, we use a novel and a general approach to augment the fluid model equations based on induced Markov chains. Using this new approach, we establish the stability region of these systems under a static priority rule with thresholds when the service and interarrival times have phase-type distributions. We show that, in certain cases, the stability region depends on the distributions of the service and interarrival times (beyond their mean), on the number of servers in the system, and on the threshold value. We also show that it is possible to expand the stability region in these systems by increasing the variability of the service times (without changing their mean) while kee** the other parameters fixed. The extension of our results to parallel server systems and general service time distributions is also discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Baccelli, F., Makowski, A.M.: Stability and bounds for single server queues in random environment. Commun. Stat., Stoch. Models 2, 281–291 (1986)

    Article  Google Scholar 

  2. Baharian, G., Tezcan, T.: Stability analysis of parallel server systems under longest queue first. Math. Methods Oper. Res. 74, 257–279 (2011)

    Article  Google Scholar 

  3. Bell, S.L., Williams, R.J.: Dynamic scheduling of a system with two parallel servers in heavy traffic with resource pooling: asymptotic optimality of a threshold policy. Ann. Appl. Probab. 11, 608–649 (2001)

    Article  Google Scholar 

  4. Bertsimas, D., Gamarnik, D., Tsitsiklis, J.N.: Performance bounds for multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Ann. Appl. Probab. 11, 1384–1428 (2001)

    Article  Google Scholar 

  5. Bramson, M.: State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Syst. 30, 89–148 (1998)

    Article  Google Scholar 

  6. Bramson, M.: Stability of earliest-due-date, first-served queueing networks. Queueing Syst. 39, 79–102 (2001)

    Article  Google Scholar 

  7. Bramson, M.: Stability of queueing networks. Probab. Surv. 5, 165–345 (2008)

    Google Scholar 

  8. Chen, H.: Fluid approximations and stability of multiclass queueing networks I: work-conserving disciplines. Ann. Appl. Probab. 5, 637–665 (1995)

    Article  Google Scholar 

  9. Chen, H., Yao, D.: Fundamentals of Queueing Networks: Performance, Asymptotics, and Optimization. Springer, New York (2001)

    Google Scholar 

  10. Chen, H., Zhang, H.: Stability of multiclass queueing networks under FIFO service discipline. Math. Oper. Res. 22, 691–725 (1997)

    Article  Google Scholar 

  11. Chen, H., Zhang, H.: Stability of multiclass queueing networks under priority service disciplines. Oper. Res. 48, 26–37 (2000)

    Article  Google Scholar 

  12. Dai, J.G.: On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models. Ann. Appl. Probab. 5, 49–77 (1995)

    Article  Google Scholar 

  13. Dai, J.G.: Stability of Fluid and Stochastic Processing Networks. MaPhySto, Aarhus (1999)

    Google Scholar 

  14. Dai, J.G., Jennings, O.B.: The stability of open stochastic multi-server processing networks with batch processing and setups. In: Yao, H.Z.D.D., Zhou, X.Y. (eds.) Stochastic Models and Optimization, pp. 193–243. Springer, New York (2003)

    Chapter  Google Scholar 

  15. Dai, J.G., Jennings, O.B.: Stabilizing queueing networks with setups. Math. Oper. Res. 29, 891–922 (2004)

    Article  Google Scholar 

  16. Dai, J.G., Lin, W.: Maximum pressure policies in stochastic processing networks. Oper. Res. 53, 197–218 (2005)

    Article  Google Scholar 

  17. Dai, J.G., Vande Vate, J.H.: The stability of two-station multitype fluid networks. Oper. Res. 48, 721–744 (2000)

    Article  Google Scholar 

  18. Dai, J.G., Hasenbein, J.J., Vande Vate, J.: Stability and instability of a two-station queueing network. Ann. Appl. Probab. 41, 326–377 (2004)

    Google Scholar 

  19. Dai, J.G., Hasenbein, J.J., Kim, B.: Stability of join-the-shortest-queue networks. Queueing Syst. 57, 129–145 (2007)

    Article  Google Scholar 

  20. Down, D., Lewis, M.: The N-network model with upgrades. In: Probability in the Engineering and Informational Sciences, pp. 171–200 (2010)

    Google Scholar 

  21. Fayolle, G., Malyshev, V., Menshikov, M.: Topics in the Constructive Theory of Countable Markov Chains. Cambridge University Press, Cambridge (1995)

    Book  Google Scholar 

  22. Foss, S., Kovalevskii, A.: A stability criterion via fluid limits and its application to a polling system. Queueing Syst. 32, 131–168 (1999)

    Article  Google Scholar 

  23. Garnett, O., Mandelbaum, A., Reiman, M.: Designing a call center with impatient customers. Manuf. Serv. Oper. Manag. 48, 566–583 (2002)

    Google Scholar 

  24. Harrison, J.M.: Heavy traffic analysis of a system with parallel servers: asymptotic optimality of discrete-review policies. Ann. Appl. Probab. 8(3), 822–848 (1998)

    Article  Google Scholar 

  25. Johnson, M.A., Taaffe, M.R.: The denseness of phase distributions. Technical report, Purdue School of Industrial Engineering Research Memoranda (1988)

  26. Lu, S., Kumar, P.: Distributed scheduling based on due dates and buffer priorities. IEEE Trans. Autom. Control 36, 1406–1416 (1991)

    Article  Google Scholar 

  27. Meyn, S.: Transience of multiclass queueing networks via fluid limit models. Ann. Appl. Probab. 5, 946–957 (1995)

    Article  Google Scholar 

  28. Rybko, A., Stolyar, A.: Ergodicity of stochastic processes describing the operation of open queueing networks. Probl. Inf. Transm. 28, 199–220 (1992)

    Google Scholar 

  29. Stolyar, A.: On the stability of multiclass queueing networks: a relaxed sufficient condition via limiting fluid processes. In: Markov Processes and Related Fields, pp. 491–512 (1995)

    Google Scholar 

  30. Stolyar, A., Ramakrishnan, K.: The stability of a flow merge point with non-interleaving cut-through scheduling disciplines. In: INFOCOM ’99, March, vol. 3, pp. 1231–1238 (1999)

    Google Scholar 

  31. 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, 94–110 (2010)

    Article  Google Scholar 

Download references

Acknowledgements

Research supported by NSF Grant CMMI-0954126.

Author information

Authors and Affiliations

  1. Simon Graduate School of Business, University of Rochester, Rochester, NY, USA

    Tolga Tezcan

Authors
  1. Tolga Tezcan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tolga Tezcan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tezcan, T. Stability analysis of N-model systems under a static priority rule. Queueing Syst 73, 235–259 (2013). https://doi.org/10.1007/s11134-012-9304-z

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11134-012-9304-z

Keywords

Mathematics Subject Classification

Search

Navigation