×

zbMATH — the first resource for mathematics

Iterative approximation of \(k\)-limited polling systems. (English) Zbl 1122.60083
The paper considers a polling model with a \(k\)-limited service strategy. Under this strategy the server continues working at a queue until either a predefined number of \(k\) customers is served or until the queue becomes empty, whichever happens first. The paper aims to study the marginal queue length distribution under the assumption of general arrival, service and setup distributions. Its goal is the development of a computationally efficient iterative approximation method. The algorithm developed in the paper only needs information on the first two moments of all distributions.

MSC:
60K25 Queueing theory (aspects of probability theory)
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90B22 Queues and service in operations research
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Asmussen S, Koole G. Marked point processes as limits of Markovian arrival streams. J Appl Probab 1993;30:365–72. · Zbl 0778.60035 · doi:10.2307/3214845
[2] Blanc JPC. An algorithmic solution of polling models with limited service disciplines. IEEE Trans Commun 1992;40(7):1152–5. · doi:10.1109/26.153357
[3] Borst SC, Boxma OJ, Levy H. The use of service limits for efficient operation of multistation single-medium communication systems. IEEE/ACM Trans Netw 1995;3(5):602–12. · doi:10.1109/90.469947
[4] Boxma OJ. Workloads and waiting times in single-server systems with multiple customer classes. Queueing Syst 1989;5:185–214. · Zbl 0681.60098 · doi:10.1007/BF01149192
[5] Chang KC, Sandhu D. Pseudo-conservation laws in cyclic-service systems with a class of limited service policies. Ann Oper Res 1992;35:209–29. · Zbl 0755.60078 · doi:10.1007/BF02188705
[6] Chang KC, Sandhu D. Mean waiting time approximations in cyclic-service systems with exhaustive limited service policy. Perform Eval 1992;15(1):21–40. · Zbl 0743.68042 · doi:10.1016/0166-5316(92)90082-R
[7] Charzinski J, Renger T, Tangemann M. Simulative comparison of the waiting time distributions in cyclic polling system with different service strategies. In: Proceedings of the 14th international teletraffic congress. Antibes Juan-les-Pins; 1994. p. 719–728.
[8] Coffman EG Jr, Gilbert EN. A continuous polling system with constant service times. IEEE Trans Inf Theory 1986;32(4):584–91. · doi:10.1109/TIT.1986.1057199
[9] Dallery Y, David R, Xie X. Approximate analysis of transfer lines with unreliable machines and finite buffers. IEEE Trans Autom Control 1989;34(9):943–53. · Zbl 0689.68118 · doi:10.1109/9.35807
[10] Doshi BT. Queueing systems with vacations–a survey. Queueing Syst 1986;1(1):29–66. · Zbl 0655.60089 · doi:10.1007/BF01149327
[11] Doshi BT. Single server queues with vacations. In: Takagi H, editors. Stochastic analysis of computer and communication systems. Amsterdam: North-Holland; 1990. p. 217–65.
[12] Everitt D. A note on the pseudoconservation laws for cyclic service systems with limited service disciplines. IEEE Trans Commun 1989;37(7):781–3. · doi:10.1109/26.31172
[13] Federgruen A, Katalan Z. Approximating queue size and waiting time distributions in general polling systems. Queueing Syst 1994;18:353–86. · Zbl 0938.68544 · doi:10.1007/BF01158768
[14] Federgruen A, Katalan Z. The stochastic economic lot scheduling problem: cyclical base-stock policies with idle times. Manag Sci 1996;42(6):783–96. · Zbl 0880.90031 · doi:10.1287/mnsc.42.6.783
[15] Federgruen A, Katalan Z. Determining production schedules under base-stock policies in single facility multi-item production systems. Oper Res 1998;46(6):883–98. · Zbl 0987.90029 · doi:10.1287/opre.46.6.883
[16] Fricker C, Jaibi R. Monotonicity and stability of periodic polling models. Queueing Syst 1994;15:211–38. · Zbl 0789.60092 · doi:10.1007/BF01189238
[17] Fuhrmann SW. Performance analysis of a class of cyclic schedules. Bell laboratories technical memorandum 81-59531-1; 1981.
[18] Gershwin SB, Burman MH. A decomposition method for analyzing inhomogeneous assembly/disassembly systems. Ann Oper Res 2000;93:91–115. · Zbl 0953.90016 · doi:10.1023/A:1018940310682
[19] Johnson MA. An empirical study of queueing approximations based on phase-type distributions. Stoch Models 1993;9(4):531–61. · Zbl 0780.60092 · doi:10.1080/15326349308807280
[20] Keilson J, Servi LD. The distributional form of Little’s law and the Fuhrmann-Cooper decomposition. Oper Res Lett 1990;9(4):239–47. · Zbl 0717.60110 · doi:10.1016/0167-6377(90)90068-G
[21] Kroese DP, Schmidt V. A continuous polling system with general service times. Ann Appl Probab 1992;2:906–27. · Zbl 0772.60075 · doi:10.1214/aoap/1177005580
[22] Kühn PJ. Multiqueue systems with nonexhaustive cyclic service. Bell Syst Tech J 1979;58(3):671–98.
[23] Lang M, Bosch M. Performance analysis of finite capacity polling systems with limited-M service. In: Proceedings of the 13th international teletraffic congress. Copenhagen; 1991. p. 731–735.
[24] Lee D-S, Sengupta B. An approximate analysis of a cyclic server queue with limited service and reservations. Queueing Syst 1992;11:153–78. · Zbl 0752.60080 · doi:10.1007/BF01159293
[25] Lee D-S. A two-queue model with exhaustive and limited service disciplines. Stoch Models 1996;12(2):285–305. · Zbl 0852.60099 · doi:10.1080/15326349608807385
[26] Leung KK. Cyclic-service systems with probabilistically-limited service. IEEE J Sel Areas Commun 1991;9(2):185–93. · doi:10.1109/49.68446
[27] Levy Y. A class of scheduling policies for real-time processors with switching system applications. In: Proceedings of the 11th international teletraffic congress. Yokohama; 1985. p. 760–766.
[28] Levy H, Sidi M. Polling systems: applications, modeling and optimization. IEEE Trans Commun 1990;COM-38(10):1750–60. · doi:10.1109/26.61446
[29] Mack C, Murphy T, Webb NL. The efficiency of N machines uni-directionally patrolled by one operative when walking time and repair times are constants. J Roy Stat Soc Ser B 1957;19(1):166–72. · Zbl 0090.35301
[30] Mack C. The efficiency of N machines uni-directionally patrolled by one operative when walking time is constant and repair times are variable. J Roy Stat Soc Ser B 1957;19(1):173–8. · Zbl 0090.35302
[31] Marie RA. Calculating equilibrium probabilities for \(\lambda\)(n)/C k /1/N queue. In: Proceedings Performance ’80. Toronto; 1980. p. 117–125.
[32] van der Mei RD, Winands EMM. Mean value analysis for polling systems in heavy traffic. In: Proceedings Valuetools. Pisa: ACM Press; 2006.
[33] van der Mei RD. Towards a unifying theory on branching-type polling models in heavy traffic. Report. Free University; 2006.
[34] Naoumov VA, Krieger UR, Wagner D. Analysis of a multiserver delay-loss system with a general markovian arrival process. In: Alfa AS, Chakravarthy SR, editors. Matrix-analytic methods in stochastic models. New York: Dekker; 1997. p. 43–66. · Zbl 0872.60070
[35] Neuts MF. Matrix-geometric solutions in stochastic models, an algorithmic approach. Baltimore: Johns Hopkins Press; 1981. · Zbl 0469.60002
[36] Ozawa T. Alternating service queues with mixed exhaustive and K-limited services. Perform Eval 1990;11:165–75. · doi:10.1016/0166-5316(90)90009-8
[37] Ozawa T. Waiting time distribution in a two-queue model with mixed exhaustive and gated-type K-limit service. In: Proceedings of international conference on the performance and management of complex communication networks. Tsukuba; 1997. p. 231–250.
[38] Resing JAC. Polling systems and multitype branching processes. Queueing Syst 1993;13:409–26. · Zbl 0772.60069 · doi:10.1007/BF01149263
[39] Takagi H. Queueing analysis of polling models: an update. In: Takagi H, editor. Stochastic analysis of computer and communication systems. Amsterdam: North-Holland; 1990. p. 267–318.
[40] Takagi H. Queueing analysis: a foundation of performance evaluation, vacation and priority systems, part 1. Amsterdam: North-Holland; 1991. · Zbl 0744.60114
[41] Takagi H. Queueing analysis of polling models: progress in 1990–1994. In: Dshalalow JH, editor. Frontiers in queueing: models, methods and problems. Boca Raton: CRC Press; 1997. p. 119–46. · Zbl 0871.60077
[42] Takagi H. Analysis and application of polling models. In: Haring G, Lindemann C, Reiser M, editors. Performance evaluation: origins and directions. Lecture notes in computer science, vol 1769. Berlin: Springer; 2000. p. 423–42.
[43] Tijms HC. Stochastic models: an algorithmic approach. Chichester: Wiley; 1994. · Zbl 0838.60075
[44] van Vuuren M, Adan IJBF, Resing-Sassen SA. Performance analysis of multi-server tandem queues with finite buffers and blocking. OR Spectr 2005;27(2–3):315–38. · Zbl 1124.90307 · doi:10.1007/s00291-004-0189-z
[45] van Vuuren M, Adan IJBF. Performance analysis of assembly systems. In: Proceedings of the Markov anniversary meeting. Charleston; 2006. p. 89–100.
[46] Winands EMM, Adan IJBF, van Houtum GJ. The stochastic economic lot scheduling problem: a survey. Eindhoven: BETA WP-133, Beta Research School for Operations Management and Logistics; 2005.
[47] Winands EMM, Adan IJBF, van Houtum GJ. A two-queue model with alternating limited service and state-dependent setups. In: Proceedings of analysis of manufacturing systems–production management. Zakynthos; 2005. p. 200–208.
[48] Winands EMM, Adan IJBF, van Houtum GJ. Mean value analysis for polling systems. Queueing Syst 2006;54(1):45–54. · Zbl 1137.90434 · doi:10.1007/s11134-006-7898-8
[49] Winands EMM. Branching-type polling systems with large setups. Report. Eindhoven University of Technology; 2006.
[50] Zipkin PH. Foundations of inventory management. London: McGraw–Hill; 2000. · Zbl 1370.90005
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.