Skip to main content
SpringerLink
Log in

Dynamic scheduling in multiclass queueing networks: Stability under discrete-review policies

  • Published:
Queueing Systems Aims and scope Submit manuscript

Abstract

This paper describes a family of discrete-review policies for scheduling open multiclass queueing networks. Each of the policies in the family is derived from what we call a dynamic reward function: such a function associates with each queue length vector q and each job class k a positive value r k (q), which is treated as a reward rate for time devoted to processing class k jobs. Assuming that each station has a traffic intensity parameter less than one, all policies in the family considered are shown to be stable. In such a policy, system status is reviewed at discrete points in time, and at each such point the controller formulates a processing plan for the next review period, based on the queue length vector observed. Stability is proved by combining elementary large deviations theory with an analysis of an associated fluid control problem. These results are extended to systems with class dependent setup times as well as systems with alternate routing and admission control capabilities.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. N. Bambos and J. Walrand, Scheduling and stability aspects of a general class of parallel processing systems, Adv. in Appl. Probab. 25 (1993) 176–202.

    Article  Google Scholar 

  2. D. Bertsimas, D. Gamarnik and J.N. Tsitsiklis, Stability conditions for multiclass fluid queueing networks, IEEE Trans. Automat. Control 41(11) (1996) 1618–1631.

    Article  Google Scholar 

  3. D. Bertsimas and G. Van Ryzin, A stochastic and dynamic vehicle routing problem in the Euclidean plane, Oper. Res. 39(4) (1991) 601–615.

    Google Scholar 

  4. M. Bramson, Instability of FIFO queueing networks, Ann. Appl. Probab. 4(2) (1994) 414–431.

    Google Scholar 

  5. M. Bramson, Stability of two families of queueing networks and a discussion of fluid limits, Queueing Systems (1998) to appear.

  6. H. Chen, Fluid approximations and stability of multiclass queueing networks: work-conserving policies, Ann. Appl. Probab. 5 (1995) 637–655.

    Google Scholar 

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

    Google Scholar 

  8. J.G. Dai, Stability of open multiclass queueing networks via fluid models, in: Stochastic Networks, eds. F. Kelly and R. Williams, Proceedings of the IMA, Vol. 71 (Springer, New York, 1995) pp. 71–90.

    Google Scholar 

  9. J.G. Dai, A fluid limit model criterion for instability of multiclass queueing networks, Ann. Appl. Probab. 6 (1996) 751–757.

    Article  Google Scholar 

  10. J.G. Dai and S. Meyn, Stability and convergence of moments for multiclass queueing networks via fluid limit models, IEEE Trans. Automat. Control 40(11) (1995) 1889–1904.

    Article  Google Scholar 

  11. J.G. Dai and G. Weiss, Stability and instability of fluid models for certain re-entrant lines, Math. Oper. Res. 21 (1996) 115–134.

    Google Scholar 

  12. J.G. Dai and R.J.Williams, Existence and uniqueness of semimartingale reflecting Brownian motions in convex polyhedrons, Theory Probab. Appl. 40 (1994) 3–53 (in Russian). To appear in the SIAM translation of the journal with the same name.

    Google Scholar 

  13. M.H.A. Davis, Piecewise-deterministic Markov processes: A general class of nondiffusion stochastic models, J. Roy. Statist. Soc. Ser. B 46(3) (1984) 353–388.

    Google Scholar 

  14. A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications (Jones and Bartlett, 1993).

  15. A. Federgruen and Z. Katalan, Approximating queue size and workload distributions in general polling systems, Queueing Systems 18 (1994) 353–386.

    Article  Google Scholar 

  16. N. Gans and G. Van Ryzin, Optimal control of a multiclass, flexible queueing system, Oper. Res. 45(5) (1997) 677–693.

    Google Scholar 

  17. J.M. Harrison, Brownian models of queueing networks with heterogeneous customer populations, in: Stochastic Differential Systems, Stochastic Control Theory and Applications, eds. W. Fleming and P.L. Lions, Proceedings of the IMA, Vol. 10 (Springer, New York, 1988) pp. 147–186.

    Google Scholar 

  18. J.M. Harrison, The BIGSTEP approach to flow management in stochastic processing networks, in: Stochastic Networks: Theory and Applications, eds. F. Kelly, S. Zachary and I. Ziedins (Oxford Univ. Press, Oxford, 1996) pp. 57–90.

    Google Scholar 

  19. J.M. Harrison, Brownian models of open processing networks: Canonical representation of workload, Ann. Appl. Probab. (1996) submitted.

  20. C. Humes Jr., A regulator stabilization technique: Kumar-Seidman revisited, IEEE Trans. Automat. Control 39(1) (1994) 191–196.

    Article  Google Scholar 

  21. E.G. Coffman Jr., A.A. Puhalskii and M.I. Reiman, Polling systems in heavy traffic: A Bessel process limit, Math. Oper. Res. 23(2) (1998) 257–304.

    Article  Google Scholar 

  22. P.R. Kumar, Re-entrant lines, Queueing Systems 13 (1993) 87–110.

    Article  Google Scholar 

  23. P.R. Kumar and S.P. Meyn, Duality and linear programs for stability and performance analysis of queuing networks and scheduling policies, IEEE Trans. Automat. Control 41(1) (1996) 4–17.

    Article  Google Scholar 

  24. P.R. Kumar and T.I. Seidman, Dynamic instabilities and stabilization methods in distributed realtime scheduling of manufacturing systems, IEEE Trans. Automat. Control 35(3) (1990) 289–298.

    Article  Google Scholar 

  25. S. Kumar and P.R. Kumar, Fluctuation smoothing policies are stable for stochastic re-entrant lines, Discrete Event Dynamic Systems 6 (1996) 361–370.

    Article  Google Scholar 

  26. J. LaSalle and S. Lefschetz, Stability by Liapunov's Direct Method (Academic Press, New York, 1961).

    Google Scholar 

  27. S.H. Lu and P.R. Kumar, Distributed scheduling based on due dates and buffer priorities, IEEE Trans. Automat. Control 36(12) (1991) 1406–1416.

    Article  Google Scholar 

  28. C. Maglaras, Discrete-review policies for scheduling stochastic networks: Trajectory tracking and fluid-scale asymptotic optimality, Ann. Appl. Probab. (1999) submitted.

  29. C. Maglaras, Dynamic control for stochastic processing networks: A fluid model approach, Ph.D. thesis, Stanford University (1998).

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

    Google Scholar 

  31. J.R. Perkins, C. Humes Jr. and P.R. Kumar, Distributed scheduling of flexible manufacturing systems: Stability and performance, IEEE Trans. Robotics Automat. 10(2) (1994) 133–141.

    Article  Google Scholar 

  32. A.N. Rybko and A.L. Stolyar, Ergodicity of stochastic processes describing the operations of open queueing networks, Problems Inform. Transmission 28 (1992) 199–220.

    Google Scholar 

  33. J. Sethuraman and D. Bertsimas, Personal communication (1998).

  34. A. Shwartz and A. Weiss, Large Deviations for Performance Analysis: Queues, Communications and Computing (Chapman & Hall, London, 1995).

    Google Scholar 

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

    Google Scholar 

  36. H. Takagi, Queueing analysis of polling models: an update, in: Stochastic Analysis of Computer and Communication Systems, ed. H. Takagi (North-Holland, Amsterdam, 1990).

    Google Scholar 

  37. L. Tassiulas and S. Papavassiliou, Optimal anticipative scheduling with asynchronous transmission oportunities, IEEE Trans. Automat. Control 40(12) (1995) 2052–2062.

    Article  Google Scholar 

  38. J.A. Van Mieghem, Dynamic scheduling with convex delay costs: The generalized cµ rule, Ann. Appl. Probab. 5 (1995) 809–833.

    Google Scholar 

  39. A. Weiss, An introduction to large deviations for communication networks, IEEE J. Selected Areas Commun. 13(6) (1995) 938–952.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Columbia Business School, Uris Hall 409, 3022 Broadway, New York, NY, 10027-6902, USA

    Constantinos Maglaras

Authors
  1. Constantinos Maglaras
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Maglaras, C. Dynamic scheduling in multiclass queueing networks: Stability under discrete-review policies. Queueing Systems 31, 171–206 (1999). https://doi.org/10.1023/A:1019106213778

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1019106213778

Search

Navigation