B9801-33: Stochastic Processing Networks
Columbia Business School -- Spring 1999
Announcements
New meeting time/place:
The class will be meeting once a week, every Wednesday
10:00 - 12:40 at Uris 328.
Correction to HW1 ex.1(b). The question should read:
Suppose that the routing matrix satisfies $P(i,1)=1$
for $i > 1$ and all external arrivals are into station 1.
Teaching staff
- Professor: Costis Maglaras
- Office: Uris 409
- Tel: (212)-854.4240
- Email:
[email protected]
- Office Hours: TBA
Course overview
Course description
Stochastic processing network models may be used to represent
service operations, manufacturing systems, or communication
systems.
These ``stochastic processing networks" are highly complex
and difficult to analyze exactly.
A major insight that has emerged over the past 10-15 years,
uses a hierarchy of approximate models as the basis for
analysis and synthesis of such systems.
In particular, the analytical theory associated with fluid
approximations and Brownian approximations has produced
important insights in understanding how the performance
of a multiclass network depends on different design and
control parameters.
Within this general framework,
the two central themes of this course are: first,
descriptive performance analysis for processing networks,
where one strives to understand the factors that contribute
to congestion and delay; and second, dynamic flow management,
including problems of routing, sequencing and input control.
The course starts with a description of classical queueing
network models, but mainly focuses on their continuous
idealizations based on fluid and Brownian model approximations.
Course objectives
The main objective for this course is to describe the hierarchical
framework to stochastic network control problems based on fluid
and Brownian approaximations, to cover the basic theory behind it,
and finally explore some of its potential applications.
In detail, we will study
the analytical theory of fluid and Brownian models,
stability analysis for multiclass networks based on
fluid models,
applications from diverse fields, and, finally,
we will overview the current research in these areas, both
in theory and applications.
Textbook & Grading
There is no textbook. Most of the material covered in
this course is not contained in a textbook or even a
research monograph.
Complete lecture notes will be handed out during the
course, and will be available in postscript and adobe
pdf via this web page.
Some texts will serve as auxiliary references:
F. P. Kelly, Reversibility and Stochastic Networks.
John Wiley & Sons, 1979.
J. M. Harrison, Brownian motion and stochastic flow systems.
John Wiley & Sons, 1985.
There will be 5 or 6 homework assignements (that will
involve some Matlab programming -- no prior knowledge
of Matlab is required), and a term project.
The grade: homework 50%, project 50%.
Tentative Course outline
Product-form networks (2 lectures).
(1) Course introduction. Preliminaries on Markov
Processes, reversibility, and the Output Theorem.
Introduction to product-form networks.
(2) Jackson networks. Quasi-reversibility and
Kelly networks. Closed queueing networks.
Fluid models and stability analysis
(2.5 lectures).
(3) Multiclass networks: system dynamics; examples of
scheduling rules. Introduction to stability theory.
Fluid models: formal derivation and basic properties.
(4) Dai's stability theorem. Stability analysis based on
fluid model analysis. Lyapunov and trajectory decomposition
techniques. Instability examples. Virtual stations.
Dynamic control based on fluid models
(2.5 lectures).
(5) Decsription of the basic methodology. Examples.
Dynamic control of fluid models. Optimal control for fluid
models. Algorithmic issues.
(6) Translating the fluid control policy back into
the stochastic network. Discrete-review policies: stability
and fluid-scale asymptotic optimality.
(7) Extensions to routing and admission control
problems. Examples: flexible resources and pooling,
communication networks, revenue management.
Brownian models (2 lectures)
(8)
Introduction to Brownian models. One-dimensional reflected
Brownian motion. Heavy-traffic limit for the $G/G/1$ queue.
(9) $G/G/1$ queue continued.
Brownian model approximations for stochastic processing networks
in heavy-traffic and the BIGSTEP approach to dynamic network
control problems.
Applications and Special topics (3 lectures).
The last part of the course will focus on applications of the
techniques developed so far, and in an overview of the current
literature on these -or related- topics;
this part will be tailored according to class interests.
(Each lecture will consist of roughly two 75 minute parts
with a 10 minute break.)
Handouts and notes
Course overview (in ps
or pdf)
Part I: Product form networks (Lectures 1 and 2)
Lecture notes on product form networks:
prod-form.ps or
prod-form.pdf.
First homework due Wedn. February 10.
Solutions to homework 1:
hw1-prod-form+sols.ps or
hw1-prod-form+sols.pdf.
Part II: Fluid models and stability analysis (Lectures 3, 4 and 5)
Lecture notes on fluid models and stability analysis are
courtesy of Prof. J. Dai -- they are available through me (Uris 409).
Second homework due Fri. March 5:
hw2-fm-stability.ps or
hw2-fm-stability.pdf.
Solutions to homework 2:
hw2-fm-stability+sols.ps or
hw2-fm-stability+sols.pdf.
Part III: Fluid models and control (Lectures 6 and 7)
Lecture notes on dynamic control of fluid models:
fluid-control.ps or
fluid-control.pdf.
Lecture notes on translation mechanisms between
fluid models and the original stochastic networks:
fluid-translation.ps or
fluid-translation.pdf.
Third homework due Fri. April 2:
hw3-fm-control.ps or
hw3-fm-control.pdf.
Part IV: Brownian models (Lectures 8 and 10)
We will use the notes by Paul Glasserman (PG) distributed
in class.
PG-Lecture 1: Brownian motion and the one-sided regulator.
PG-Lecture 2: The G/G/1 queue in heavy-traffic.
Brownian models and control: Harrison-Wein QUESTA (89) paper
and overview of Harrison's (88) IMA paper.
To view the Portable Document Format files (PDFs) on this
site,
download a
free Acrobat Reader