Problem 2 (Markov Chain model of a collaborative service network)
Consider the network in the figure below – it models a simple health-care process.
Each station has its own waiting room (or queue). Customers arrive to the first
station according to a Poisson process with rate 1/hour (that is—time between
arrivals is exponential with a mean of 1 hour).
If there are customers waiting in the first station an arriving customer will be added
to the end of the line. Once a customer is served in the first station, he/she moves to
the line before the second station where, again, the customer will wait behind other
waiting customers. The same applies to the third station.
The service time in each of the station is exponential with a mean of 20 minutes.
The tricky thing here is that we do not have a dedicate resource per station. Rather,
we have only a doctor and a nurse. They are both required to serve a
patient/customer in the first station. There can be no customers served in station 1 if
either the doctor is working in station 2 or the nurse in station 3.
Station 2 is the nurse’s station – only the nurse is required there and station 3 is the
doctor’s station – only the doctor is required there. Next, we must specify how the
doctor and nurse move between the stations. They use the following simple policy:
• As long as there are customer in station 1’s line – work together in that station
(processing customers at a rate of one every 20 minutes – or 3 per hour).
• Once done with the work there, the resources move to their individual tasks and
work there until there is an arrival to the first station. Of course, there could be
moments where either the doctor or the nurse idle. For example, when
there is no work in station 1 and 3 but there is work in station 2 – the nurse will be
working but the doctor will have nothing to do. Let Xi(t) be the number of customers
in service or waiting in station i at time t (notice that there can be at most one
customer in service in each station). I claim that if the nurse and the doctor follow
the above priority rule, the process X(t) = (X1(t), X2(t), X3(t)) is a Continuous Time
Markov Chain. Characterize the transition rates for this CTMC. Hint. you should
consider a state (x1, x2, x3) and find all states where you can transition and specify
the rate of transition.
Be careful with the case where x1 = 0 v.s. the case where x1 > 0. Just to give you
an example the transition rate from (x1, x2, x3) to (x1 − 1, x2 + 1, x3) if x1 > 0 is
1/20.
Problem 3 (Inventory management problem)
An inventory manager has the following policy. As long as there are 5 units in
inventory, there is no need to order extra items. Demand arrives according to a
Poisson process with rate μ (meaning customers come and ask for the product
every exp(μ) time). As soon as the first customer takes a product (and inventory falls
to 4), the inventory manager calls the supplier. The delivery time is random: the
supplier will show up within an exp(ℓ) amount of time. When the supplier shows up,
the inventory will be replenished to bring it back to 5. Of course, if the inventory is
empty, arriving customers leave empty handed.
a. Build a CTMC with 6 states that models the inventory evolution.
b. Say we start at 4 and the manager just called the supplier. What is the expected
time until we either go back to 5 (the supplier arrives) or we go down to 3 (another
customer takes an
item).
c. Say, now, we start at 5. What is the expected time until we run out of inventory
and start disappointing customers?
d. In the long-run, what is the fraction of time that arriving customers will be leaving
empty handed (no inventory).
Part d. does not rely on parts b. and c.