Polling Models


Course Syllabus

Click here to get a copy of the syllabus in postscript format.

Office Hours

Mondays, 3:00pm--5:00pm
Jonsson 4.912

Background Reading

Stochastic Modeling and the Theory of Queues, by Ronald W. Wolff. Prentice-Hall, Englewood Cliffs, New Jersey, 1989.

Prerequisites

OPRE 6331; or consent of the instructor.

Grading Scheme

Paper Presentation: 100%

Topics

Polling models describe systems in which a single server "polls" a number of queues according to some polling discipline. Such models are very important for the efficient design of manufacturing systems, computer systems, telecommunication systems, and other complicated systems that provide service to random demands. The seminar will be based on research papers on polling models. A significant emphasis will be placed on the analysis of polling models by decomposition methods. The following is a tentative summary of topics, which might evolve randomly during the course of the semester.
  1. Introduction
  2. The M/G/1 Queue
  3. The M/G/1 Vacation Model and Decomposition
  4. The Zero-Switchover-Times Model
  5. The Nonzero-Switchover-Times Model
  6. Relationship between the Zero- and Nonzero-Switchover-Times Models
  7. Other Results

References

  1. Boxma, O. J. [1989]. "Workloads and Waiting Times in Single-Server Systems with Multiple Customer Classes." Queueing Systems, 5, pp. 185-214.
  2. Boxma, O. J., and W. P. Groenendijk [1987]. "Pseudo-Conservation Laws in Cyclic-Service Systems." Journal of Applied Probability, 24, pp. 949-964.
  3. Cooper, R. B. [1970]. "Queues Served in Cyclic Order: Waiting Times." The Bell System Technical Journal}, 49, pp. 399-413.
  4. Cooper, R. B., and G. Murray [1969]. "Queues Served in Cyclic Order." The Bell System Technical Journal, 48, pp. 675-689.
  5. Cooper, R. B., S.-C. Niu, and M. M. Srinivasan [1992]. "A Decomposition Theorem for Polling Models: The Switchover Times are Effectively Additive." Operations Research, to appear.
  6. Eisenberg, M. [1972]. "Queues with Periodic Service and Changeover Times." Operations Research, 20, pp. 440-451.
  7. Ferguson, M. J., and Y. J. Aminetzah [1985]. "Exact Results for Nonsymmetric Token Ring Systems." IEEE Transactions on Communications, COM-33, pp. 223-231.
  8. Fuhrmann, S. W. [1992]. "A Decomposition Result for a Class of Polling Models." Queueing Systems, 11, pp. 109-120.
  9. Fuhrmann, S. W., and R. B. Cooper [1985]. "Stochastic Decompositions in the M/G/1 Queue with Generalized Vacations." Operations Research, 33, pp. 1117-1129.
  10. Konheim, A. G., H. Levy, and M. M. Srinivasan [1993]. "Descendant Set: An Efficient Approach for the Analysis of Polling Systems." IEEE Transactions on Communications, 42, pp. 1245-1253.
  11. Niu, S.-C. [1995]. "Arrival-Epoch Stochastic Decompositions in M/G/1 Queues with Generalized Vacations." Draft paper.
  12. Niu, S.-C., and R. B. Cooper [1993]. "Transform-Free Analysis of M/G/1/K and Related Queues." Mathematics of Operations Research, 18, pp. 486-510.
  13. Sarkar, D., and W. I. Zangwill [1989]. "Expected Waiting Time for Nonsymmetric Cyclic Queueing Systems - Exact Results and Applications." Management Science, 35, pp. 1463-1474.
  14. Srinivasan, M. M., S.-C. Niu, and R. B. Cooper [1993]. "Relating Polling Models with Zero and Nonzero Switchover Times." Queueing Systems, to appear.
  15. Takagi, H. [1986]. Analysis of Polling Systems. The MIT Press, Cambridge, Massachusetts.
  16. Takagi, H. [1990]. "Queueing Analysis of Polling Models: An Update." In Stochastic Analysis of Computer and Communication Systems, H. Takagi (ed.). North-Holland, Amsterdam.
  17. Takagi, H. [1994]. "Queueing Analysis of Polling Models: Progress in 1990-93." Institute of Socio-Economic Planning, University of Tsukuba, Japan, May 11, 1994.

Papers Suggested for Presentation

  1. Altman, E., and U. Yechiali [1994]. "Polling in a Closed Network." Probability in the Engineering and Informational Sciences, 8, pp. 327-343.
  2. Browne, S., and U. Yechiali [1989]. "Dynamic Priority Rules for Cyclic-Type Queues." Advances in Applied Probability, 21, pp. 432-450.
  3. Levy, H., M. Sidi, and O. J. Boxma [1990]. "Dominance Relations in Polling Systems." Queueing Systems, 6, pp. 155-172.
  4. Daganzo, C. F. [1990]. "Some Properties of Polling Systems." Queueing Systems, 6, pp. 137-154.
  5. Eisenberg, M. [1994]. "The Polling System with a Stopping Server." Queueing Systems, 18, pp. 387-431.
  6. Federgruen, A., and Z. Katalan. [1994]. "Approximating Queue Size and Waiting-Time Distributions in General Polling Systems." Queueing Systems, 18, pp. 353-386.
  7. Fuhrmann, S. W., and Y. Wang [1988]. "Analysis of Cyclic Service Systems with Limited Service: Bounds and Approximations." Performance Evaluation, 9, pp. 35-54.
  8. Hofri, M., and K. W. Ross [1987]. "On the Optimal Control of Two Queues with Server Setup Times and Its Analysis." SIAM Journal on Computing, 16, pp. 399-420.
  9. Kleinrock, L., and H. Levy [1988]. "The Analysis of Random Polling Systems." Operations Research, 36, pp. 716-732.
  10. Lee, D.-S., and B. Sengupta [1992]. "An Approximate Analysis of a Cyclic Server Queue with Limited Service and Reservations." Queueing Systems, 11, pp. 153-178.
  11. Liu, Z., P. Nain, and D. Towsley [1992]. "On Optimal Polling Policies." Queueing Systems, 11, pp. 59-84.
  12. Sarkar, D., and W. I. Zangwill [1991]. "Variance Effects in Cyclic Production Systems." Management Science, 37, pp. 443-453.
  13. Sidi, M., H. Levy, and S. W. Fuhrmann [1992]. "A Queueing Network with a Single Cyclically Roving Server." Queueing Systems, 11, pp. 121-144.
  14. Srinivasan, M. M. [1991]. "Nondeterministic Polling Systems." Management Science, 37, 667-681.
  15. Takagi, H. [1991]. "Analysis of Finite-Capacity Polling Systems." Advances in Applied Probability, 23, pp. 373-387.
  16. Takagi, H. [1992]. "Analysis of an M/G/1//N Queue with Multiple Server Vacations, and Its Applications to a Polling Model." Journal of the Operations Research Society of Japan, 35, pp. 300-315.
  17. Takine, T., and T. Hasegawa [1992]. "A Cyclic-Service Finite Source Model with Round-Robin Scheduling." Queueing Systems, 11, pp. 91-108.