Consider an integer-time queueing system with a finite buffer of size 2. At the beginning of the nth time interval, the queue contains at most two customers. There is a cost of one unit for each customer in queue (i.e., the cost of delaying that customer). If there is one customer in queue, that customer is served. If there are two customers, an extra server is hired at a cost of 3 units and both customers are served. Thus the total immediate cost for two customers in queue is 5, the cost for one customer is 1, and the cost for 0 customers is 0. At the end of the nth time interval, either 0, 1, or 2 new customers arrive (each with probability 1/3).
(a) Assume that the system starts with 0 ≤ i ≤ 2 customers in queue at time -1 (i.e., in stage 1) and terminates at time 0 (stage 0) with a final cost u of 5 units for each customer in queue (at the beginning of interval 0). Find the expected aggregate cost vi(1, u) for0 ≤ i ≤ 2.
(b) Assume now that the system starts with i customers in queue at time -2 with the same final cost at time 0. Find the expected aggregate cost vi(2, u) for 0 ≤ i ≤ 2.
(c) For an arbitrary starting time -n, find the expected aggregate cost vi(n, u) for 0 ≤ i ≤ 2.
(d) Find the cost per stage and find the relative cost (gain) vector.
(e) Now assume that there is a decision maker who can choose whether or not to hire the extra server when there are two customers in queue. If the extra server is not hired, the three-unit fee is saved, but only one of the customers is served. If there are two arrivals in this case, assume that one is turned away at a cost of 5 units. Find the minimum dynamic aggregate expected cost v∗(1), 0 ≤ i ≤ 2, for stage 1 with the same final cost as before.
(f) Find the minimum dynamic aggregate expected cost v∗(n, u) for stage n,0 ≤ i ≤ 2.
(g) Now assume a final cost u of 1 unit per customer rather than 5, and find the new minimum dynamic aggregate expected cost v∗(n, u), 0 ≤ i ≤ 2.
Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.