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.