Page 307 - A First Course In Stochastic Models

EXERCISES 301

7.4 Consider Exercise 2.20 again. Assume that the assignment types j = 1, . . . , n are
numbered or renumbered according to E(ξ)/E(τ j ) ≥ E(ξ j+1 )/E(τ j+1 ) for all j. Use
the optimality equation (7.2.2) to verify that the long-run average reward per time unit is
maximal by accepting only assignments of the types j = 1, . . . , r, where r is the smallest
integer such that
 
r r

λ j E(ξ j )  1 + λ j E(τ j )  > E(ξ r+1 )/E(τ r+1 )
j=1 j=1
with E(ξ n+1 )/E(τ n+1 ) = 0 by convention.
7.5 Adjust the value-iteration algorithm for the control problem from Example 7.3.1 when
finite-source input is assumed rather than Poisson input. Solve for the numerical data c = 10,
M 1 = M 2 = 10, δ 1 = 3, δ 2 = 1, µ 1 = 4, µ 2 = 1, where M i is the number of customers
from source i and δ i is the exponential rate at which a customer from source i generates
new service requests when the customer has no other request in service. Try other numerical
examples and investigate the structure of an optimal control rule.
7.6 Consider a flexible manufacturing facility producing parts, one at a time, for two assem-
bly lines. The time needed to produce one part for assembly line k is exponentially distributed
with mean 1/µ k , k = 1, 2. Each part produced for line k is put into the buffer for line k.
This buffer has space for only N k parts, including the part (if any) in assembly. Each line
takes parts one at a time from its buffer as long as the buffer is not empty. At line k,
the assembly time for one part is exponentially distributed with mean 1/λ k , k = 1, 2. The
production times at the flexible manufacturing facility and the assembly times at the lines
are independent of each other. A real-time control for the flexible manufacturing facility is
exercised. After each production at this facility, it must be decided what type of part is to be
produced next. The system cannot produce for a line whose buffer is full. Also, the system
cannot remain idle if not all the buffers are full. The control is based on the full knowledge
of the buffer status at both lines. The system incurs a lost-opportunity cost at a rate of
γ k per time unit when line k is idle. The goal is to control the production at the flexible
manufacturing facility in such a way that the long-run average cost per time unit is minimal.
Develop a value-iteration algorithm for this control problem. Solve for the numerical data
µ 1 = 5, µ 2 = 10, λ 1 = 4, λ 2 = 8, N 1 = N 2 = 5, γ 1 = γ 2 = 1. This problem is based on
Seidman and Schweitzer (1984).
7.7 Consider a tandem network with two assembly facilities in series. The output of the first
station is the input for the second station. Raw material is processed at station 1, and half-
finished goods at station 2. Each of the stations 1 and 2 has a finite buffer for temporarily
storing raw material and half-finished goods. The buffer size is M at station 1 and N
at station 2 (excluding any unit in processing). Units of raw material arrive at station 1
according to a Poisson process with rate λ. A unit of raw material finding the buffer full
at station 1 upon arrival is rejected and is brought elsewhere. Station 1 is a single-server
station and station 2 is a multiple-server station with c servers. Each server can handle only
one unit at a time and the processing times are exponentially distributed with mean 1/µ 1
at station 1 and mean 1/µ 2 at station 2. If the assembly of a unit is finished at station 1,
it is forwarded to station 2 provided the buffer is not full at station 2; otherwise, the unit
remains at station 1 and blocks this station until room becomes available at station 2. Station
1 cannot start a new assembly as long as it is blocked. The control problem is as follows.
Upon arrival of a new unit at station 1, a decision has to be made to accept this unit or
to reject it. The cost of rejecting a unit at station 1 is R > 0. Also, there is a blocking
cost at rate b > 0 per time unit that station 1 is blocked. The goal is to find a control rule
minimizing the long-run average cost per time unit. Develop a value-iteration algorithm.
Solve for the numerical data λ = 20, µ 1 = 15, µ 2 = 3, c = 5, M = 10, N = 3, R = 3.5