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.
- Introduction
- Polling Models - An Overview
- Review of H=\lambda G and PASTA
- The M/G/1 Queue
- Classical Departure-Chain Analysis
- Decomposition of the Waiting Time
- Arrival-Epoch Decomposition
- Generalizations
- The M/G/1 Vacation Model and Decomposition
- Departure-Epoch Decomposition
- Arrival-Epoch Decomposition
- Applications
- The Zero-Switchover-Times Model
- The Nonzero-Switchover-Times Model
- Relationship between the Zero- and Nonzero-Switchover-Times Models
- Transform Relations
- Pseudo-Conservation Laws
- Other Results
References
- Boxma, O. J. [1989]. "Workloads and Waiting Times in Single-Server Systems with Multiple Customer Classes." Queueing Systems, 5, pp. 185-214.
- Boxma, O. J., and W. P. Groenendijk [1987]. "Pseudo-Conservation Laws in Cyclic-Service Systems." Journal of Applied Probability, 24, pp. 949-964.
- Cooper, R. B. [1970]. "Queues Served in Cyclic Order: Waiting Times." The Bell System Technical Journal}, 49, pp. 399-413.
- Cooper, R. B., and G. Murray [1969]. "Queues Served in Cyclic Order." The Bell System Technical Journal, 48, pp. 675-689.
- 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.
- Eisenberg, M. [1972]. "Queues with Periodic Service and Changeover Times." Operations Research, 20, pp. 440-451.
- Ferguson, M. J., and Y. J. Aminetzah [1985]. "Exact Results for Nonsymmetric Token Ring Systems." IEEE Transactions on Communications, COM-33, pp. 223-231.
- Fuhrmann, S. W. [1992]. "A Decomposition Result for a Class of Polling Models." Queueing Systems, 11, pp. 109-120.
- 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.
- 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.
- Niu, S.-C. [1995]. "Arrival-Epoch Stochastic Decompositions in M/G/1 Queues with Generalized Vacations." Draft paper.
- 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.
- 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.
- Srinivasan, M. M., S.-C. Niu, and R. B. Cooper [1993]. "Relating Polling Models with Zero and Nonzero Switchover Times." Queueing Systems, to appear.
- Takagi, H. [1986]. Analysis of Polling Systems. The MIT Press, Cambridge, Massachusetts.
- Takagi, H. [1990]. "Queueing Analysis of Polling Models: An Update." In Stochastic Analysis of Computer and Communication Systems, H. Takagi (ed.). North-Holland, Amsterdam.
- 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
- Altman, E., and U. Yechiali [1994]. "Polling in a Closed Network." Probability in the Engineering and Informational Sciences, 8, pp. 327-343.
- Browne, S., and U. Yechiali [1989]. "Dynamic Priority Rules for Cyclic-Type Queues." Advances in Applied Probability, 21, pp. 432-450.
- Levy, H., M. Sidi, and O. J. Boxma [1990]. "Dominance Relations in Polling Systems." Queueing Systems, 6, pp. 155-172.
- Daganzo, C. F. [1990]. "Some Properties of Polling Systems." Queueing Systems, 6, pp. 137-154.
- Eisenberg, M. [1994]. "The Polling System with a Stopping Server." Queueing Systems, 18, pp. 387-431.
- Federgruen, A., and Z. Katalan. [1994]. "Approximating Queue Size and Waiting-Time Distributions in General Polling Systems." Queueing Systems, 18, pp. 353-386.
- Fuhrmann, S. W., and Y. Wang [1988]. "Analysis of Cyclic Service Systems with Limited Service: Bounds and Approximations." Performance Evaluation, 9, pp. 35-54.
- 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.
- Kleinrock, L., and H. Levy [1988]. "The Analysis of Random Polling Systems." Operations Research, 36, pp. 716-732.
- 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.
- Liu, Z., P. Nain, and D. Towsley [1992]. "On Optimal Polling Policies." Queueing Systems, 11, pp. 59-84.
- Sarkar, D., and W. I. Zangwill [1991]. "Variance Effects in Cyclic Production Systems." Management Science, 37, pp. 443-453.
- Sidi, M., H. Levy, and S. W. Fuhrmann [1992]. "A Queueing Network with a Single Cyclically Roving Server." Queueing Systems, 11, pp. 121-144.
- Srinivasan, M. M. [1991]. "Nondeterministic Polling Systems." Management Science, 37, 667-681.
- Takagi, H. [1991]. "Analysis of Finite-Capacity Polling Systems." Advances in Applied Probability, 23, pp. 373-387.
- 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.
- Takine, T., and T. Hasegawa [1992]. "A Cyclic-Service Finite Source Model with Round-Robin Scheduling." Queueing Systems, 11, pp. 91-108.