article

A polling model with multiple priority levels

Authors:

I. J. B. F. Adan,

O. J. BoxmaAuthors Info & Claims

Performance Evaluation, Volume 67, Issue 6

Pages 468 - 484

https://doi.org/10.1016/j.peva.2010.01.002

Published: 01 June 2010 Publication History

Abstract

In this paper we consider a single-server cyclic polling system. Between visits to successive queues, the server is delayed by a random switch-over time. The order in which customers are served in each queue is determined by a priority level that is assigned to each customer at his arrival. For this situation the following service disciplines are considered: gated, exhaustive, and globally gated. We study the cycle time distribution, the waiting times for each customer type, the joint queue length distribution of all priority classes at all queues at polling epochs, and the steady-state marginal queue length distributions for each customer type.

References

[1]

Wierman, A., Winands, E.M.M. and Boxma, O.J., Scheduling in polling systems. Performance Evaluation. v64. 1009-1028.

[2]

E.M.M. Winands, Polling, Production & Priorities. Ph.D. Thesis, Eindhoven University of Technology, 2007

[3]

M.A.A. Boon, I.J.B.F. Adan, O.J. Boxma, A two-queue polling model with two priority levels in the first queue, Discrete Event Dynamic Systems (2009), in press ( Eurandom report 2008-016, Eurandom, 2008

[4]

M. Cicin-Sain, C.E.M. Pearce, J. Sunde, On the application of a polling model with non-zero walk times and priority processing to a medical emergency-room environment, in: Proceedings of the 23rd International Conference on Information Technology Interfaces, vol. 1, 2001, pp. 49-56

[5]

Takagi, H., Queuing analysis of polling models. ACM Computing Surveys, CSUR. v20. 5-28.

[6]

Levy, H. and Sidi, M., Polling systems: Applications, modeling, and optimization. IEEE Transactions on Communications. v38. 1750-1760.

[7]

Vishnevskii, V.M. and Semenova, O.V., Mathematical methods to study the polling systems. Automation and Remote Control. v67 i2. 173-220.

[8]

Fournier, L. and Rosberg, Z., Expected waiting times in polling systems under priority disciplines. Queueing Systems. v9 i4. 419-439.

[9]

S. Shimogawa, Y. Takahashi, A pseudo-conservation law in a cyclic-service system with priority classes, IEICE Research Report, (IN88-86), 1988, pp. 13-18

[10]

Winands, E.M.M., Adan, I.J.B.F. and van Houtum, G.-J., Mean value analysis for polling systems. Queueing Systems. v54. 35-44.

[11]

Choudhury, G.L. and Whitt, W., Computing distributions and moments in polling models by numerical transform inversion. Performance Evaluation. v25 i4. 267-292.

[12]

Takács, L., Two queues attended by a single server. Operations Research. v16 i3. 639-650.

[13]

Cooper, R.B. and Murray, G., Queues served in cyclic order. The Bell System Technical Journal. v48 i3. 675-689.

[14]

Eisenberg, M., Queues with periodic service and changeover time. Operations Research. v20 i2. 440-451.

[15]

Resing, J.A.C., Polling systems and multitype branching processes. Queueing Systems. v13. 409-426.

[16]

S.W. Fuhrmann, Performance analysis of a class of cyclic schedules. Technical memorandum 81-59531-1, Bell Laboratories, March 1981

[17]

Borst, S.C., . In: CWI Tracts, vol. 115.

[18]

Khamisy, A., Altman, E. and Sidi, M., Polling systems with synchronization constraints. Annals of Operations Research. v35. 231-267.

[19]

Borst, S.C. and Boxma, O.J., Polling models with and without switchover times. Operations Research. v45 i4. 536-543.

[20]

Fuhrmann, S.W. and Cooper, R.B., Stochastic decompositions in the M/G/1 queue with generalized vacations. Operations Research. v33 i5. 1117-1129.

[21]

Cohen, J.W., The Single Server Queue. 1982. revised edition. North-Holland, Amsterdam.

[22]

Quine, M.P., The multi-type Galton-Watson process with immigration. Journal of Applied Probability. v7 i2. 411-422.

[23]

Boxma, O.J., Bruin, J. and Fralix, B.H., Waiting times in polling systems with various service disciplines. Performance Evaluation. v66. 621-639.

[24]

Keilson, J. and Servi, L.D., The distributional form of Little's Law and the Fuhrmann-Cooper decomposition. Operations Research Letters. v9 i4. 239-247.

[25]

Boxma, O.J., Workloads and waiting times in single-server systems with multiple customer classes. Queueing Systems. v5. 185-214.

[26]

Boxma, O.J., Levy, H. and Yechiali, U., Cyclic reservation schemes for efficient operation of multiple-queue single-server systems. Annals of Operations Research. v35 i3. 187-208.

[27]

Kella, O. and Yechiali, U., Priorities in M/G/1 queue with server vacations. Naval Research Logistics. v35. 23-34.

[28]

Takagi, H., Priority queues with setup times. Operations Research. v38 i4. 667-677.

[29]

Boxma, O.J. and Groenendijk, W.P., Pseudo-conservation laws in cyclic-service systems. Journal of Applied Probability. v24 i4. 949-964.

Cited By

Bekker RVis PDorsman JMei RWinands E(2015)The impact of scheduling policies on the waiting-time distributions in polling systemsQueueing Systems: Theory and Applications10.1007/s11134-014-9416-879:2(145-172)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1007/s11134-014-9416-8
Bekker RDorsman Jvan der Mei RVis PWinands E(2013)Scheduling in polling systems in heavy trafficACM SIGMETRICS Performance Evaluation Review10.1145/2518025.251803241:2(41-43)Online publication date: 27-Aug-2013
https://dl.acm.org/doi/10.1145/2518025.2518032

A polling model with multiple priority levels
1. Mathematics of computing

Recommendations

Mixed gated/exhaustive service in a polling model with priorities

In this paper we consider a single-server polling system with switch-over times. We introduce a new service discipline, mixed gated/exhaustive service, that can be used for queues with two types of customers: high and low priority customers. At the ...
A Two-Queue Polling Model with Two Priority Levels in the First Queue

In this paper we consider a single-server cyclic polling system consisting of two queues. Between visits to successive queues, the server is delayed by a random switch-over time. Two types of customers arrive at the first queue: high and low priority ...
A two-queue polling model with two priority levels in the first queue
ValueTools '08: Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools

In this paper we consider a single-server cyclic polling system consisting of two queues. Between visits to successive queues, the server is delayed by a random switch-over time. Two types of customers arrive at the first queue: high and low priority ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Performance Evaluation

Performance Evaluation Volume 67, Issue 6

June, 2010

84 pages

ISSN:0166-5316

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2010.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 June 2010

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bekker RVis PDorsman JMei RWinands E(2015)The impact of scheduling policies on the waiting-time distributions in polling systemsQueueing Systems: Theory and Applications10.1007/s11134-014-9416-879:2(145-172)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1007/s11134-014-9416-8
Bekker RDorsman Jvan der Mei RVis PWinands E(2013)Scheduling in polling systems in heavy trafficACM SIGMETRICS Performance Evaluation Review10.1145/2518025.251803241:2(41-43)Online publication date: 27-Aug-2013
https://dl.acm.org/doi/10.1145/2518025.2518032

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents