Time: | 12 Monday mornings (February 16 - April 5; April 19 - May 10. |
Location: | Room 107A, Buys Ballot Laboratorium, Princetonlaan 4, The Uithof, Utrecht. |
Lecturers : | Prof.dr.ir. S.C. Borst (CWI and Eindhoven University of
Technology),
prof.dr. L.C.M. Kallenberg (LNMB and Leiden University) and prof.dr. G.M. Koole (Free University Amsterdam). |
Course description:
Stochastic dynamic programming
The theory of Markov decision processes (MPDs) - also known under
several
other names as sequential stochastic optimization, stochastic control
or
stochastic dynamic programming, studies sequential optimization of
stochastic
systems whose transition mechanism can be controlled over time. Each
control
policy defines a stochastic process and values of objective functions
associated
with this process. The goal is to select an optimal control policy. In
real life, decisions that are made usually have two types of impact:
they
cost or save time or money, or other resources, as well as they have
impact
on the future, by influencing the dynamics. In many situations,
decisions
with the largest immediate profit may not be good in view of future
rewards.
MPDs model this paradigm and provide results on the structure and
existence
of good policies and on methods for the computation of optimal
policies.
Control of queues
The performance of queueing systems can be controlled by strategies
for the arrivals and the servers, e.g. how are customers at arrival be
assigned to one of a number of servers; how are one or more servers be
assigned to different customer classes of queues? Depending on the
objective
function we can compare several strategies and look for an optimal
strategy.
In some cases the optimal strategy has a nice structure, e.g. send an
arrival
to the server with the shortest queue.
Part 1 (Control of queues I; Borst)
- Stochastic majorization, coupling techniques.
- Routing to parallel queues, load balancing, scheduling in multi-class
queues, priority strategies.
- Achievable performance region, conservation laws, performance bounds,
asymptotically optimal policies.
Prerequisites:
- Basic knowledge of probability, stochastic processes as well as
queueing
theory ( in particular stochastic variables, probability distributions,
expectation, M/G1 queue).
Some useful background material:
- R. Nelson; Probability, stochastic processes and queueing theory,
Springer, 1995 (Chapters 2, 4, 5, 7).
- S.M. Ross, Introduction to Probability Models, Academic Press, 1989
(Chapters 1 - 8).
- S.M. Ross, Stochastic Processes, Wiley, 1996 (Chapters 1 - 5, 9).
- R.W. Wolff, Stochastic Modeling and the Theory of Queues, Prentice
Hall, 1989 (Chapters 1 - 5, 10).
Literature:
Lecture notes will be provided.
Examination:
Take home problems.
Part 2 (Control of queues II; Koole)
In this part of the course we focus on the control of queueing systems.
We apply the theory
to several controlled queueing models. We also pay attention to the
curse
of dimensionality and its implications
Prerequisite:
Part 2 of this course.
.
Literature:
Lecture notes will be privided.
Examination:
Take home problems.
Part 3 (Stochastic dynamic programming; Kallenberg)
- Introduction of the model, policies and optimality criteria; the
finite horizon.
- Discounted rewards (optimality equation; bounds on the value vector;
solution methods).
- Average and more sensitive rewards (laurent expansion; solution
methods).
- Application (gambling; optimal stopping; replacement; mullti-armed
bandits).
Prerequisites:
-Elementary knowledge of linear programming (e.g. K.G. Murthy, Linear
programming, Wiley, 1983).
- Elementary knowledge of probability theory (e.g. S.M. Ross, A first
course in probability, Macmillan, New York, 1976).
- Elementary knowledge of (numerical) analysis (e.g. Banach space;
contracting mappings; Newton's method; Laurent series).
Literature:
Lecture notes are available as pdf file: Survey
SDP
The 110 slides of the lectures are available as pdf file: Sheets
SDP 2004
Examination:
Take home problems.
The exercises (deadline June 15) are available as pdf file: Exercises
SDP 2004
Addresses of the lecturers:
Prof.dr.ir. S.C. Borst
Centre for Mathematics and Computer Science
P.O. Box 94079
1090 GB Amsterdam
Phone: 020- 5924205
E-mail: sem.borst@cwi.nl
Prof.dr. L.C.M. Kallenberg
Mathematical Institute
Leiden University
P.O. Box 9512
2300 RA Leiden
Phone: 071 - 5277130
E-mail: kallenberg@math.leikdenuniv.nl
Prof.dr. G.M. Koole
Free University Amsterdam
Faculty of Mathematics and Computer Science
De Boelelaan 1081a
1081 HV Amsterdam
Phone: 020 - 4447755
E-mail: koole@cs.vu.nl