Chapter 4: DTMC
Exercise 1 : Stochastic process
Give a stochastic process to describe the evolution of the following variables as well as the nature of their time space and state space :
a) The daily number of phone calls over a year
b) The number of phone calls arrived in interval [0, t]
c) Daily average time for handling a call over the week
d) Remaining waiting time of a customer given the time he has waited
Exercise 2 : Random walk
Let X1, X2, … be identical and independent random variables (i.i.d.). Consider the stochastic process{Yn}n=0,1,2,… with Y0 = 0, and Yn = X1 + X2 + ... + Xn.{Yn}n=0,1,2,… is called a random walk.
a) Are the random variables Yn independent ?
Let Xnbe aBernoulli random variable with parameter p, i.e P[Xn = 1] = p and P[Xn = -1] = 1-p.
b) Propose a graphic representation of the random walk {Yn}
c) Determine a relation between P[Yn = i], i N and P[Yn+1 = j], j N
Exercise 3 : Stochastic matrix
a) Let P be a stochastic matrix, show that Pnis also stochastic
b) Show that all stochastic matrix has an eigenvalue equal to 1.
c) Frobenius Theorem: let P be a stochastic matrix, show that all its eigenvalues are smaller or equal to 1.
Exercise 4 : Graphic representation of DTMCs
Classify the states of the following DTMCs (absorbing, transient, recurrent). Are the DTMCs irreducible?
Exercise 5 : Canonical form
Consider a DTMC with the following graphic representation
a) Classify the states
b) Identify the sub-chains
c) Give the transition matrix of its canonical form
Problem 1 : It's your destinity !
Some sociologists range individuals of a society into 3 social classes: Bourgeois (B), Middle class (C) and Proletariat (P). We are interested in this simplistic model on the social class reached by the end of lifetime by each individual. Assume that this social class depends only on that of the father.
If the father belongs to B, his son belongs to B and C with proba 0.5 and 0.5.
If the father belongs to C, his son belongs to B, C and P with proba 0.2, 0.7 and 0.1.
If the father belongs to C, his son belongs to B, C and P with proba 0.1, 0.3 and 0.6.
a) Model this sociology behavior by a Markov chain.
b) Give its state-transition graph, its matrix
c) Determine the nature of each state. Is the chain irreducible? Periodic?
d) What is the long term average proportion of each class?
e) What is the stationary probability of being in a social class different from that of his grand father?
Problem 2 : Le contrat de confiance
The manager of a supermarket observed that the daily demand of washing machines is a Bernoulli random variable. More precisely, each day, a washing machine is sold with probability p and no machine is sold with probability 1-p.
When the last machine is sold, an order of m machines is issued and delivered the next day morning. The storage cost is s per machine per day. The order cost is independent of order quantity and is b per order.
a) Determine the average daily cost with DTMC.
b) Which value of m minimizes this cost?
Problem 3 : French Roulette versus american roulette
You feel well, you buy i tokens and move to the nearest roulette table. Your strategy is simple: you put a token on each game and only choose simple chances (even/odd, red/black, …). The probability of wining is p for each try and the payout is 1 to 1. You decide to stop if you arrive at a tokens (or if you loose all and you are bankrupted).
Let Xn be your number of tokens after n games.
a) Show that {Xn}n=0,1,…is a Markov chain. Give its graphic representation and its transition matrix. Determine the nature of each state. Is the chain irreducible?
b) Determine the probability fi0 of bankruptcy by starting with i tokens (you can try to find a recursive relation of fi0)
c) Determine the expectation of gain E[G]
d) Calculate the average time ei of the game starting with i tokens
e) Numerical application: determine ei and fi0 for French roulette (p = 18/37) and american roulette (p = 18/38) with i=50 and a=100
Problem 4 : Reliability
A company uses a machine with the following state of wear : new, slightly degraded, degraded, and unusable. Each day of use in each of the four states brings a gain of respectively 1000 $, 1000$, 800$ and 0$. The degrading process is modeled as a DTMC with day as time unit with the following transition probabilities:
new / slightly degraded / degraded / unusablenew / 0,6 / 0,2 / 0,1 / 0,1
slight degraded / 0 / 0,7 / 0,2 / 0,1
degraded / 0 / 0 / 0,8 / 0,2
unusable / 0 / 0 / 0 / 1
a) Determine the average lifetime of a new machine
b) Assume that the replacement of the machine by a new one cost K = 2000$ and takes one day for installation. Which of the following two policies maximize the long term gain:
(P1) Replace the machine when it becomes unusable
(P2) Replace the machine when it is degraded or unusable
Problem 1: Preventive maintenance and discrete time Markov chains
Consider a discrete time model of a machine subject to failures. At the beginning of each period t, the machine has an age n, i.e. the number of periods since its last repair or preventive maintenance. The failure rate of the machine depends on its age. If it fails in period t, a corrective maintenance (CM) of cost Cr = 1000€ is needed and the machine will be of age 0 at the beginning of period t+1. If it does not fail, its age will be increased by 1 at the beginning of period t+1. The failure rate of the machine is the following one:
age / 0 / 1 / 2 / 3failure rate / 0 / 0.1 / 0.2 / 1
For this system, you are asked to:
a)Propose a Markov chain model of the age of the machine by explaining the meaning of states and transitions;
b)Determine the steady state distribution with justifications of its existence and details of different steps of your computation;
c)Determine the average life-time of the machine and its average maintenance cost per period.
In view of the above results, the company considers the introduction of preventive maintenance (PM). At the beginning of each period t, it is possible to perform a PM of cost Cp = 200€ which brings immediately the machine to a new state, i.e. of age 0 at the beginning of period t but after the PM.
You are asked to compare three maintenance policies: P3 – preventive maintenance at age 3, P2- preventive maintenance at age 2, P1- preventive maintenance at age 1. Repeat a)-c) in order to determine the total maintenance cost (PM and CM) per period.
Chapter 5: CTMC
Exercise 1 : Exponential distribution
a) A memoryless random variable is a random variable T such that:
P{T t+ x | T t} = P{T x}, t, x
Show that the only memoryless continuous probability distribution is exponential distribution
b) Prove that the sojourn time in a state i of a CTMC is exponentially distributed.
c) Let X1, X2, … , Xn, be n independent random variables with exponential distribution of parameter λ1, λ2, … , λn and Y= min{X1,X2, …, Xn}. Show that:
- Y is exponentially distributed with parameter λ1 + λ2 + …+ λn
- P[Xi = Y]= λi/(λ1+λ2+ … +λn) and P[Xi = Y | Y = y]= λi/(λ1+λ2+ … +λn)
d) Let X1, X2, … , Xnbe n independent random variables with the same exponential distribution of parameter λ. Show that Zn = X1 + X2 + ... + Xn has the following probability distribution :
Remark : Znis said to follow a n-stage Erlang distribution with parameter .
Exercise 2 : Poisson process
Let N(t) be a Poisson process with parameter λ .
a) Show the following probability distribution:
b) Show that the superposition of n Poisson process with respectively rates λi(i=1,…,n) is a Poisson process with parameter Σ λi .
c) Show that the split of N(t) with probabilities pi gives n Poisson processes of parameter λ pi .
Problem 1 : Reliability
A factory has two identical machines, each with an exponential reliability of rate λ (which implies that the time between two consecutive failures is exponentially distributed with parameter λ). Machines work permanently when they are not failed. When a machine fails, the repair requires two repairmen R1 and R2 consecutively (always in the order R1 then R2). The factory has only one repairman R1 and one repairman R2. As a result, if a machine fails while R2 is repairing another machine, then the second machine has to wait of the end of the on-going repair (same wait for R2). The repair time of R1 and R2 are exponentially distributed with rates μ1 and μ2 .
a) Show that the system can be modeled by a CTMC of 6 states. Give the associated graph.
b) Write the probability flow balance equation (also called equilibrium equation) for μ1 = μ2 = μ;
c) Compute the steady state probabilities.
d) Assume that, on average, a machine fails every 4 hours of operation and that each repairman takes 1 hour to do his repair. What is the availability of the factory, i.e. the proportion of time during which at least one machine is UP.
Problem 2 : Production
Consider a 2-machine production system
The system is fed by an unlimited stock of raw parts. Each part has to visit all three machines in the same order for its production. The machining time of each machine is a random variable with on average 10 minutes on machine 1 and 12 minutes on machine 2. There is no buffer space between the machines. When a part arrives on a machine, it starts the operation. At the end of the operation, two scenarios are possible. If the next machine is available, then the part immediately moves forward and continues its production. If the next machine is not available, the part remains on the machine and the machine is blocked. The blocking situation ends when the next machine becomes available again. We assume that the last machine is never blocked.
a) Under which conditions the behavior of the system can be modeled as a CTMC and explain the meaning of each state.
b) Verify the existence of stationary distribution and determine stationary probabilities.
c) What is the proportion of time P during which at least one machine is blocked?
d) What is the average number X of parts produced per unit of time?
e) What is the average number of parts present in the system?
f) What is the average number M of machines working on a part?
g) What is the average time R needed to produce a part (also called the production leadtime)?
Problem 2 (Availability of machines and Continuous-time Markov Chains).
A shop-floor has three identical machines, each with an exponential failure rate λ (which implies that the UP time of each machine is exponentially distributed with rate λ). The three machines work at full speed when they are not failed. When a machine fails, its repair is performed by a repairman R. There is only one repairman. As a result, a machine that fails while the repairman R is busy with another machine has to wait. The repair time is an exponentially distributed random variable with rate .
a)Show that the system can be modeled by a continuous time Markov chains. Give its graphic representation. Explain the meaning of its states and transitions.
b)Justify the existence of steady state distribution;
c)Write the flow balance equations;
d)Calculate the steady state probabilities;
e)Assume that a machine fails on average every 4 hours, it takes on average 1 hour to repair and each UP machine produces at rate 2 parts/hour. What is the productivity of the system?
f)What is the productivity of the system if a second repairman is available?
Problem 3 : Packet switching
Consider a packet switching networking communication system composed of 3 nodes and 2 links:
The arrival process to node 1 is supposed to be Poisson with rate . All packets are transmitted through links 1-2 and 2-3. When node 3 receives a packet, it handles instantaneously the packet. All nodes have a limited capacity of one packet. It implies:
- when a packet arrives at node 1 while node 1 is busy with another packet, the new packet is lost;
- if there is a packet on node 1 and another packet on node 2, then node 1 cannot start its emission till node 2 becomes empty. It is assumed that node 1 is informed in real time of the availability of node 2.
The emission time of node i is assumed to be exponentially distributed with rate μi, i = 1, 2. The propagation on each link is small enough to be neglected. While a packet is emitted, it occupies a place on the node.
a) Model the behavior of this network as a CTMC by indicating the meaning of each state;
b) Determine the stationary probabilities after the justification of their existence.
c) What is the probability of loss of a packet upon its arrival?
d) Give the average time a packet takes to traverse the network.
Chapter 5Bis Stochastic Petri nets
1. Building the SPN model and deriving the markov chain of the Problem 1 in Chapter 5.
2. (Performance evaluation of Kanban-controlled system)
Consider a production system controlled by kanbans and illustrated by the figure below. It is composesd of two machines M1 and M2. N kanbans are used to control the production. When there is at least one free kanban and there is a part waiting in the input buffer of the system, a kanban is attached to the part and the part moves to the input buffer S1 of machine M1. After being served by M1, the part moves to the input buffer S2 of M2. After the service of M2, the part waits in the finished good inventory S3 for a customer order. It is delivered when a customer order arrives. When this happens, the kanban attached to the part is detached and sent to the free kanban buffer S4 and will be used to authorize the production of other parts. Note that there are at most N parts in the system and the production is pulled by customer demand.
Fig. : A kanban-controlled system
In this problem, we assume that there is always a part in the input stock of the system. The processing times at M1 and M2 are randomly variables of exponential distribution with mean 1/1 and1/2. Customer demands arrive according to a Poisson process at rate 0, i.e. the inter-arrival time is a random variable of exponential distribution of mean 1/0. A customer demand is lost if the finished good inventory S3 is empty at its arrival. Let0 = 1, 1 = 1.5, 2 = 1.5, . S3 contains initially 2 parts and S1, S2, S4 and S5 are initially empty.
1.Model the system using stochastic Petri net. Be sure to explain the physical meaning of places and transitions. How do you represent the lost demand?
2.Determine the structural properties of the model and explain their implications;
3.Determine the marking graph;
4.Determine the Markov chain;
5.Prove the existence of the stationary distribution;
6.Determine the stationary distribution of the Markov chain;
7.Determine the throughput rate, the percentage of lost demand, mean sojourn time of parts in S3.
3. (Failure-prone production system)
The Petri net given below models a production line composed of one unreliable machine M1 and a reliable machine M2. M1 is represented by places p1, p2, p3, and p4 corresponding to the following state: idle (p1), working on a part (p2), blocked (p3), and failed (p4). M2 is represented by place p8. An AGV (Automated Guided Vehicle), represented by the token in p7, is used to transport parts from M1 to M2. Transition t6 represents the tranfer of parts between the two machines, place p5 parts in transfer, place p6 parts in the input buffer of M2. We assume that (i) the transportation time is small enough to be neglected and (ii) when the AGV arrives at M2, it is released only when M2 finished the part on it.
Processing times of M1 and M2 (firing times of t2 and t7) are random variables of exponential distribution of mean 1/2 and 1/7. Time between failure (firing time of t 4) and repair time (firing time of t5) are random variable of exponential distributionof mean 1/4 and 1/5.
For the sake of simplicity, the following degree of priority is assigned: priority 0 (t2, t4, t5, t7), priority 1 (t1), priority 2 (t3, t6). Further, 2 = 4 = 5 = 7 = 1
a) Determine the incidence matrix.
b) Prove that the PN is conservative and consistent.
c) Determine the marking graph by taking intio account the priority.
d) Derive the Markov chain.
e) Show that it is ergodic.
f) Determine its stationary distribution.
g) Determine the productivity (firing frequency of t7), the utilization ratio of M2, the mean sojourn time of the AGVat M2 (i.e. the mean sojourn time of tokens in p6).
Chapter 6: Queueing systems
Problem 1 : Telephone switch
Consider a telephone switch system able to handle simultaneously C calls. A new call arriving while C calls are in progress is lost. Assume that the arrival process of calls is a Poisson process with rate λ and the service is exponential with rate μ.
a) Model the system by a queueing system and give its Kendall notation
b) Give the CTMC model of the system
c) Determine the stationary probabilities and give the stability condition
d) Give the expression of throughput rate of successful calls, of the average number of on-going calls and the average response time.
Problem 2 : A finite population system
Consider a system with m potential customers. Each customer, when he is not in the system, arrives according to a Poisson process of rate . The service time of a customer is exponentially distributed with rate . The system has unlimited number of servers.
a) Model the system by a queueing system and give its Kendall notation
b) Give the CTMC model of the system
c) Determine the stationary probabilities and give the stability condition
d) Give the average number of customers in the system.
Problem 3 : Computer network
The computer network of a pharmaceutical company composed of 10 terminals. These 10 terminals (assumed to be always busy) are connected to a processor (CPU). Each terminal can send a request at a time to the CPU and wait for the answer of the processor before sending another request. After the answer of the CPU to a user, the latter should wait on average 40 seconds before sending a new request. It is called think time. The processor treats the requests one after another in FIFO order and it takes on average 4 seconds to treat a request.
The think time and the treatment time are exponentially distributed.
a) Model the computer network
b) Formulate the network as a queueing system and give its Kendall notation
c) Enumerate and classify all possible states of the associated Markov chain, give its graphic representation and its infinitesimal generator
d) Assume that the stationary distribution is known. Compute the average number of requests in the processor, the average response time and the utilization rate of the processor.
Problem 4 : Switch with priority
Consider a telephone switch able to handle simultaneously C calls. Three classes of calls arrive at the switch. It is assumed that calls of type r arrive according to a Poisson process of rate λr, r = 1, 2 or 3. When a call arrives and there are less than C calls in the switch, the call is treated immediately. The call time is assumed to be independent of the call type and is exponentially distributed with rate m. When a call cannot be served immediately, depending on its type, it is put in a FIFO queue of limited capacity or rejected.