Block Queueing Theory and Simulation
Spring 2010

Instructors:	Ivo Adan
	office:	HG 9.07
	telephone:	247 2932
	e-mail:	i.j.b.f.adan@tue.nl
	Jacques Resing
	office:	HG 9.08
	telephone:	247 2984
	e-mail:	j.a.c.resing@tue.nl
Office Hours:	After class
	or when we are in
Examination:	Take home assignments Basic Part (Due: August 31)
	#1 Comparison of segments of DNA
	#2 Theoretical driving exams
	#3 Patent office

Aim

The aim of this course is to give an introduction to the use of stochastic models for the design of production and communication systems.

The emphasis in the course is on queueing models. Exact and approximation methods will be presented for the analysis of queueing models. These methods include, for example, Markov chain analysis, transform methods and the use of fundamental relations such as Little's law and the PASTA property. Attention is paid to discrete-event simulation of queueing models, and also to advantages and disadvantages of analytical methods versus simulation.

The main goal of this course is to develop some skills in

• stochastic modeling of production and communication systems,
• exact and approximative analysis of queueing models, and
• implementing a simulation model by using JAVA or a simulation package such as Chi or Arena and performing an input analysis of the data and an output analysis of the simulation results.

Set-up

The set-up of the course is as follows. It consists of two parts. The first part treats basic concepts from probability theory, Markov chains, renewal theory and it provides an introduction to queueing models and simulation. The examination consists of take-home assignments. This part is suitable for each orientation. In the second part more advanced queueing models and simulation techniques are presented. This part is suitable for the B and C/I orientation. The examination consists of take-home assignments presented during the course. The assignments involve modeling, analyzing and simulating practical problems.

Course outline

1. Basic concepts from probability theory
2. Renewal theory
3. Markov chains and Markov processes
4. Queueing models and some fundamental relations; M/M/1 system
5. M/G/1 and G/M/1 systems
6. Introduction to simulation;
   random number generators, generating random variables and input and output analysis
   C-source text of simulations:
   • Coin tossing (realization)
   • Fraction of time one of the players is leading
   • Five Heads in a row
   • Birthday problem
   • Nearly birthday problem
   • Lottery problem
   • Lottery problem (with generating loops)
   • Breaking matches
   • Two-machine production line with exponential up and down times
   Java-source text of simulations:
   • Coin tossing
   • Fraction of time one of the players is leading
   • Five Heads in a row
   • Birthday problem
   • Nearly birthday problem
   • Lottery problem
   • Lottery problem (with generating loops)
   • Breaking matches
   • Two-machine production line with exponential up and down times
   Text:
   • Five Heads in a row (exact solution)
7. Event scheduling approach versus process interaction approach;
   simulation of the M/M/1 system with Java, Chi and Arena
   C-source text of simulations:
   • discrete simulation of single-stage production system
   • discrete-event simulation of single-stage production system
   Java-source text of simulations:
   • discrete-event simulation of single-stage production system
   Chi-source text of simulations:
   • discrete-event simulation of single-stage production system
   • discrete-event simulation of single-stage production system with three parallel machine
   • discrete-event simulation of two-stage production system

1. Variations of the M/M/1, M/G/1 and G/M/1 systems;
   priorities, setups, batching, multi-server systems, approximations
   • The M/M/1 system with subcontracting
   • The M/G/1 system with set-up times
     
   • The M/M/1 system with priorities
     
   • The M/G/1 priority system
   • Queueing systems with general interarrival times
     
   • Multi-machine systems
2. Production lines
3. Open job shops
4. Closed production networks
5. Fluid flow models;
   analysis and simulation
6. Simulation;
   • Refresher of input and output analysis
   • random number generators
   • generating random variables
   • variance reduction techniques
   • warm-up interval
7. Simulation of networks of queues with Arena
   Example:
   • Production of parts
   • Arena source text of simulation of production of parts
   • C-source text of Mean Value Algorithm

References

• S.M. Ross (2000) Introduction to Probability Models (7th ed.). Academic press, Londen.
• J. A. Buzacott and J.G. Shanthikumar (1993). Stochastic Models of Manufacturing Systems. Prentice Hall, 1993.
• A.M. Law and W.D. Kelton (2000). Simulation modeling and analysis. 3rd ed. New York: Mc-Graw-Hill.
• G.S. Fishman (2001). Discrete-event simulation: modeling, programming, and analysis. Berlin: Springer.
• J. Banks and J.S. Carson (2001). Discrete-event system simulation. 3rd ed. Upper Saddle River: Prentice Hall.
• P. Bratley, B.L. Fox and L.E. Schrage (1983). A guide to simulation. Springer.
• W.D. Kelton, R.P. Sadowski, D.A. Sadowski (2002). Simulation with Arena. 2nd ed., London: McGraw-Hill, 2002
• Documentation of specification language Chi.
• Lecture notes on queueing theory