Question

During any period, a potential customer arrives at a certain facility with probability 1/2. If there are already two people at the facility (including the one being served), the potential customer leaves the facility immediately and never returns. However, if there are one or fewer people, he enters the facility and becomes an actual customer. The manager of the facility has two types of service rates available. If he uses his “slow” service rate at a cost of $3 during a period, a customer will be served and leave the facility with probability 3/5. If he uses his “fast” service rate at a cost of $9 during a period, a customer will be served and leave the facility with probability 4/5. Note that the probability of more than one customer arriving or more than one customer being served in a period is zero. A profit of $50 is earned when a customer is served. The manager wants to minimize the expected discounted cost of service over an infinite horizon β=0.9).

a) Formulate the problem as a Markov decision process (e.g. specify the state space, decision set, transition probabilities, expected rewards) Hint: In computing the costs for services, do not forget the opportunity cost of losing a potential customer – e.g. 50$ is lost.

b) Formulate the problem as a linear program to determine the optimal stationary policy.

c) Implement the policy iteration algorithm starting with the stationary policy that always uses slow service. Iterate either until you find the optimal policy or implement 3 iterations.

d) Implement the value iteration algorithm for 3 iterations.

e) In the value iteration algorithm, what is the number of iterations necessary to achieve a desired precision of ε=0.1?

Answer 1

A potential customer arrives at a certain facility with probability 1/2 the manager of the facility has two types of service rates variables if he uses his 'slow' service rate at cost of $ 3 during a period a customer will be served a customer will be served and leave the facility with probability 4/5 A profit of $ 50 is earned when a customer is served beta = 0.9 there are 3 possible states 0, 1, 2 0 - no customer in queue 1 - 1 customer in queue 2 - 2 customer in queue so arrival probability in a queue is 0.5 immediate cost incurred for the slow service = 3/5 times 3 = $ 18 for the service = 4/5 times 9 = $ 7.2 [0.5 0.5 0 0.3 0.5 0.2 0.2 0.3 0.5] 3/5 is probability of slow servicing 2/5 is customer not serviced \r\n probability