IE 512 Queueing Theory and Applications
Spring Semester 1999
Wherever there is competition for limited resources queuing is likely to
occur. People queue up at the checkout counter at grocery stores,
parts queue to be processed at a machine center and machines are queued
to gain access to repair. Airplanes queue before landing or
takeoff, email messages are queued at a server, and computer programs are
queued at the job scheduler of a parallel supercomputer, to name a few.
The objective of queuing theory is to understand such queuing phenomenon
in order to predict the performance, control, and sometimes optimize the
system where the queuing occurs. Due to the range of applicability
and potential gain of controlling these systems, proper understanding of
queuing can be a powerful tool.
In this class we build a foundation for the investigation of queuing
phenomenon by studying variety of queues. These range in complexity
from simple single server queues, that can be used to model a single checkout
counter or a single machine, to complex networks of queues, that can be
used to model job shops or flexible flow shops in production environments.
Our emphasis is on intuitive understanding of queuing and on modeling and
solution techniques that are useful in applications.
Index
General Course Information
Contact Information
Time and Place
Classes are held on MWF at 12:10 in Marston
314.
Prerequisites
The official prerequisites for this class is IE
313 Stochastic Analysis.
Texts
The textbook for this class is Fundamentals of Queueing Theory by
Donald Gross and Carl Harris. Lecture notes and additional material will
be handed out in class, and a few books have been placed on reserve
in the Parks library. These
books supplement and extend our treatment of the material, and also provide
much more background on stochastic processes.
Books on reserve:
-
Cassandras, C. G. 1994. Discrete Event Systems: Modeling
and Performance Analysis, Irwin, Homewood, IL.
-
This book takes a discrete event systems (DES) approach
to stochastic processes. Much of this material is outside the scope
of this class, but it provides a very interesting alternative view of the
systems that we are studying. I think the DES approach has a great
appeal to engineers since it has been developed by other engineers as opposed
to mathematicians. It may therefore prove very helpful for you in
developing an intuition about stochastic systems. Chapters 1 - 4
provide the basics of the DES approach, and chapter 5 and chapter 6 cover
Markov chains and queuing theory, respectively.
-
Ross, S.M. 1996. Stochastic Processes, 2nd ed., John
Wiley, New York.
-
This is an excellent traditional introduction to stochastic
processes at the graduate level. The intended audience is primarily
industrial engineering graduate students rather than mathematicians or
other scientists. Look at this book if you think your background
in stochastic processes is lacking and you don't feel comfortable with
the material we have reviewed in class.
-
Wolff, R. 1989. Stochastic Modeling and the Theory of
Queues, Prentice-Hall, New Jersey.
-
Another excellent introduction to stochastic processes
that deals more extensively with queues. It takes a renewal theoretic
approach to stochastic processes (chapter 2), which is a bit more advanced
than our approach. There is an excellent discussion of the Poisson
process in section 2-6, and Markov chains are treated in detail in chapters
3 and 4. Chapter 5 is a self-contained treatment of simple queuing
systems and is a must read. Other queuing models that we will also
discuss are treated in section 6-1 to 6-5 (networks), section 8-1 to 8-3
(M/G/1 queue), section 9-1 (G/G/1 queue), section 11-1 to 11-2 (bounds),
and section 11-10 (approximations).
The library
reserve site for this class has now been created.
Additional handouts in class:
-
Notes on the law
of total probability (conditioning).
-
Basic information on the gamma distribution (photocopy of page 13 in Bickel
and Doksum, Mathematical Statistics: Basic Ideas and Selected
Topics, Prentice Hall: Englewood Cliffs, New Jersey, 1977).
Homework
There will be regular homework assigned for this class and it will account
for 35% of the final grade. All homework is
due one week after it is assigned unless otherwise noted.
A solution
key for homework five and six.
Exam
An in-class midterm exam will be held on March 3rd
and covers Part I Stochastic Processes (see the schedule
below). This exam will be closed book with a formula sheet provided
and it will account for 25% of the final grade.
The final exam is scheduled as an in-class exam on April 30th, and will
be open book and open notes. It will account for 35% of the final
grade. The final will be noncumulative in the sence that
no direct questions will be asked on the material from Part
I; however, the material in Part II depends
heavily
on the earlier material.
Grading
The final grade will be based on a midterm exam,
a final exam, homework assignments,
and class participation. The following weights will be used:
| Midterm Exam |
25% |
| Final Exam |
35% |
| Homework |
35% |
| Participation |
5% |
Back to Index
Schedule
The following topics will be covered. As each chapter of the lecture
notes becomes available it will be linked to a postscipt file with the
text. The references in brackets are to the corresponding material
in the primary text book.
The entire lectures
notes can now be downloaded.
Part I Stochastic Processes
Chapter 1 Introduction
Stochastic processes (p. 6).
Sample paths of stochastic processes (p. 10).
Queuing systems (p. 12).
Summary (p. 13).
Chapter 2 The Poisson Process
Arrival processes (p. 15) .
The Poisson process (p. 16).
The exponential distribution (p. 20).
Further properties of the Poisson process (p. 24).
Chapter 3 Markov Processes
A motivational example (p. 27).
Discrete Markov chains (p. 29).
Long-Run behavior (p. 35).
Continuous time Markov chains (p. 46).
Birth-death processes (p. 55).
Reversibility (p. 57).
Application: Designing a FMS (p. 61).
Summary (p. 65).
Part II Queuing Theory
Chapter 4 Single Server Queues
Introduction to queues (sections 1.1 - 1.6).
Simple Markovian queues (sections 2.2 - 2.4).
Little's Law (section 2.2.5).
Erlang's loss formula (section 2.5).
Chapter 5 Queuing Networks
Tandem queues (section 4.1).
Jackson networks (section 4.2).
Closed networks (section 4.3).
Chapter 6 Advanced Topics
Erlangian models (section 3.3).
Phase-type distributions (section 3.3).
The Pollaczek-Khintchine formula (section 5.1.1).
The Lindley equation for G/G/1 (section 6.2).
The Kingman bounds for G/G/1 (section 7.1.1).
Heavy traffic approximations (section 7.2).
Back to Index
Direct
comments concerning this page to olafsson@iastate.edu.
Copyright @ 1999 Sigurdur Olafsson. All
Rights Reserved
