Queue Solution

 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.

Operations Research Models and Methods
Internet
by Paul A. Jensen