Queuing Results User Functions Non-Markovian Queues Non-Markovian User Functions Open Networks Job Shop Example Non-Markovian Networks Closed Networks Queue Simulation Optimize
An open queuing network can be optimized with the help of the Optimize add-in. The results of this page assume that the Optimize add-in is installed as well as the Queuing add-in. We use as an example the Job Shop network that was described earlier. The model constructed by the Queuing add-in is shown below. Our goal is to select the number of servers at each station to satisfy constraints on results for the system. The numbers of servers are the numbers in the range B5:G5.
 To create an optimization model, we choose Optimize Form from the Queue menu. We also show the Optimize menu on the figure at the left because that add-in must also be installed. We will deal directly with the Optimize add-in through the Search command. The dialog below is presented and we enter the name of the open queuing system and a maximum for the number of servers. A linear server cost indicates that each server in a station has the same cost. A nonlinear server cost creates a table so that different unit costs can be entered for each station. The Optimize add-in performs searches for discrete combinatorial problems. It is applicable in many circumstances. The queuing network provides an example of a search over the integers to optimize a nonlinear objective function subject to nonlinear constraints.
The Queuing add-in identifies cells for constraints immediately to the right of the system results. Column J holds the limit placed on the system result. Column K holds formulas indicating whether the result is less than or equal to the limit. Column L holds formulas computing the difference between the result and the limit. For a feasible solution all the cells in the range K7:K12 must be TRUE. The numbers shown below are for the initial values of the variables. The constraints are not satisfied for this solution.

The Optimize add-in is automatically called to construct a combinatorial optimization form starting in column M. The cells colored green in row 8 hold the values of the decision variables, the numbers of servers in each of the six stations. Row 9 holds formulas that compute lower limits to the numbers of servers. There must be at least the number of servers at a station so that total service rate is greater than the total arrival rate. The upper limits (6) were specified in the dialog. These numbers may be changed after the form is constructed. Row 14 holds the unit costs of the servers at the stations. Since the example uses 1, we are minimizing the total number of servers used. Row 12 computes the server cost for each station. The sum of the yellow colored cells in row 12 is computed in cell P4. This is the objective function for the model. Cell R3 holds a logical expression that indicates whether all the constraints are satisfied (they are not for the initial solution). Cell R4 computes the amount of constraint violation. All formulas in the yellow or pink cells are created by the add-ins and no user interaction is required.

 One additional important step is accomplished by the add-in. The numbers in the range N8:S8 are linked to the queuing model by placing formulas in the cells B5:G5. For example we see in cell B5 the formula: =N8 The other cells are similarly linked. When the Optimize add-in manipulates the numbers in N8:S8, the server numbers in B5:G5 are changed. The functions in the queuing model compute the system results in column J indicating whether the solution is feasible. The variables are manipulated by the Optimize add-in and the worksheet computes the objective function and constraints. To initiate optimization we choose Search from the menu. The dialog that defines the search strategy is shown below. There are many ways to search for the optimum. For illustration we choose Exhaustive Enumeration. This option will generate all values of the decision variables within the lower and upper bounds and evaluate the corresponding solutions. The add-in chooses the best feasible solution. This option guarantees optimality, but at the cost of many computations.

The add-in computes the number of evaluations required and presents the number in a dialog with the choice to continue or not.

After some time, the algorithm finally finishes with the optimum solution shown below. The solution has 18 stations, which is the minimum number of stations that satisfies the constraints.

The system results for the optimum solution fall within the limits imposed. Individual station results are to the left of this display starting in column A. The demonstration file for this section has the complete worksheet.

To the right of the combinatorial form is a summary of the time and number of runs required for the optimization. There is always one extra run because the optimum solution is repeated. The table below shows the 20 best solutions found. There is only one solution with 18 servers that satisfies the constraints, where there are several with 19 and 20.

Although exhaustive enumeration finds the best solution it takes a long time to find it. The approach is not practical for larger numbers of variables or greater variable ranges.

There are a number of heuristic alternatives that do not guarantee the optimum, but often give good results. The Greedy algorithm is a general procedure that changes the variables one at a time. Starting from an initial solution, the variable that improves the solution the most is increased of decreased by 1, and the process repeats. The process terminates when no change of a single variable improves the solution. We choose Greedy with the Search dialog.

For the example, the Greedy algorithm returned the optimum solution in 2 seconds on the author's computer.

Another option is random search that may be followed by an improvement process. The example below shows that 5 solutions are to be generated randomly. Each random solution is to be subjected to a 2-change procedure. The 2-change procedure selects pairs of variables and attempts to increase and/or decrease the variable values in an attempt to improve the solution. All pairs are considered and the process continues until no improvement is possible.

The results are below. Again the process finds the optimum. The runs are divided into Enumeration runs and Improvement runs. The enumeration runs are the five random solutions and the repeated optimum run. The improvement runs are due the 2-change method.

The Optimize add-in provides the capability for finding the best values of the parameters of the queuing system. Using the Optimize command of the Queue menu builds the model described here. Optimization with different objectives and constraints can be performed by using the Add Form command on the Optimize menu.

Operations Research Models and Methods
Internet
by Paul A. Jensen