|
|
 |
Dynamic
Programming
Examples |
 |
-
Queue with Variable Number of Channels Solution |
|
The solution of
the queuing problem is found with the DP Solver add-in
(dp_solver.xla). Click the Transfer
to DP Solver at
the top of the model page. The model has 55 states, so any
of the DP Solver are forms available. We chose
the Transition
List option. The add-in automatically constructs the solver
model. The top of the solver model page is shown below. To
find the optimum solution, click the Solve button.
|
| |
|
The number of states is too great for the
Policy approach. Also, the quantity of interest
is the total of the operating costs for a two hour period.
Each period of analysis is 0.01 hours so we choose Value iterations for 200 periods. The summary
display will show the last iteration, deleting all states
with zero probability. |
|
| |
After a few seconds the solution
for all states is shown in the state list of the solver page.
The figure shows the first 20 states. The Action Index and Name columns
show the optimum action for each state. The State Value column
shows the total costs of the system as a function of the initial
state. Since the numbers in this column are all negative, the
system yields an operating profit, regardless of the starting
state. The State
Probabilities approximate
the steady-state probabilities for the states. |
|
| |
Since the discount rate is zero,
the state values will not converge with additional runs. Both
the state value and state probabilities are approximate since
initial conditions affect the results, even after 200 iterations. |
Recovering the Solution |
|
Since probabilities govern transitions,
the optimum sequence of states cannot be easily recovered.
The display on the Book State worksheet
shows the policy for the states with only nonzero state
probabilities. There are 37 such states.
They are listed so that the lowest populations are near
the top. We see that all states below (6, 2) delete channels
or leave the channels the same. Some of the states with higher
populations delete channels. |
|
| |
To gain further insight on the
solution, I used the scatter chart option to show the population
vs. channels columns. The arrows (added by the author) show transitions
between states. The black arrows indicate transitions that involve
arrivals and departures. Red arrows indicate transitions that
occur after the addition of a channel. Green arrows indicate
transitions that occur after a deletion.
In terms of the original problem, when the system starts in
state (0, 2), two registers are used until the 6 customers
are in the checkout system. Two are in service and four are
in the queue. Then a third register is opened. Depending on
the subsequent event, the system moves to (5, 3), (6, 3) or
(7, 3). Note that the register change decision comes before
the arrival, stay, departure events. The graph clearly shows
the register policy and would be a useful management tool. |
|
| |
Because of the cost of changing
the number of registers, the delete option comes at much lower
populations than the add option. Say at state (6, 3) the number
of registers was changed from 2 to 3. If it happens that the
number of waiting customers declines, the number of registers
would not be reduced until state (0,3), when all customers are
served. |
Conclusion |
| |
This example represents a problem that is often
encountered when operating queuing systems. This is the problem
of choosing the number of servers as a function of the number
in the system. Even though the discount rate is zero, the total
cost over a fixed number of iterations is a rational measure
of effectiveness. The MDP model is solved to obtain an optimum
policy. The workbook for this example also contains DTMC models
for a fixed number of servers. |
| |
|
|
