Simulation Optimization

Your Guidance System for Complex Decisions Under Uncertainty

Simulation has proven itself to be an incredibly useful tool for evaluating complex systems. Sometimes, however, you need to do more than just evaluate how a system will react under a given combination of conditions. Instead, what you really need to do is find the combination of conditions that will give you the 'best' possible system performance. To achieve this with a stand-alone simulation model, you will need to change model parameters, run each scenario and repetitively review results in the search for a satisfactory solution.

A simulation optimization algorithm works to automate this search procedure in an intelligent manner, saving you time and, if properly used, giving you superior results. In cases where there are many, many alternatives to evaluate, the automated guidance provided by a good simulation optimization tool can be a very welcome addition to your modeling arsenal.

When Evaluation Alone Isn't Enough

Let's look at how a simulation model typically functions as a decision making aid. A properly developed and validated simulation model will show you - very accurately - what level of performance you can expect from a system for a given set of input parameters. In other words, it will tell you what you can expect if you take some particular action. A simulation model alone, however, cannot recommend which action among many you should take. For that, you need to use a specialized technique called optimization. What's more, you need an optimization tool that has been specially developed for use with simulation models - even better if it has been designed for use with your simulation package of choice.

Thanks to enormous progress in the field of simulation optimization over the past several years, a very high quality and efficient simulation optimization plug-in, called OptQuest^TM for SIMUL8 is now available.

How Does Simulation Optimization Work?

To answer that question, let's back up a bit and consider how a human analyst might approach the problem of changing scenario variables to find a good solution. The process might go something like this:

1. Decide upon evaluation criteria (also called an objective function). What measure or combination of measures will you choose to evaluate the quality of any given solution? Will it be throughput, utilization, cycle time, usage of labor or perhaps some combination of the above? It doesn't do much good to compare scenarios until you've got a basis for evaluation.
2. Determine which input parameters can be changed and by how much. After all, if you know that you don't have physical space for more than one additional machine, you won't want to waste your time considering scenarios that would require three new machines. This is referred to as bounding the parameters.
3. Consider any known relationships between decision variables. You could reduce your effort tremendously by taking these into account. For example, if you know that parameter 2 must be larger than parameter 1, you wouldn't bother evaluating any scenarios in which parameter 1 had a value larger than parameter 2.
4. Using all of the information you've gathered so far, make an educated guess at appropriate values for all scenario variables. Make sure that they fall within the limits you specified in steps 2 and 3.
5. Run the simulation to see how well the system performs with the values selected in step 4. Make sure to run the model several times, each time with a new random number seed. With all those random numbers, you have to make sure that a single run isn't just a fluke.
6. Gather up the results from your multiple simulation runs and evaluate how well the current scenario worked.
7. Are you either happy with the results, out of time for your analysis, or just plain tired of dealing with it? If so then STOP. If you are up for trying more scenarios, return to step three.

A simulation optimization tool works with your simulation model to automate the process in much the same way. Not all of the elements can be automated, however. In setting up the optimization, you must still perform steps (1-3) above. Once you have provided an objective function and specified your scenario variables and associated constraints, a typical simulation optimization algorithm will take the following steps:

1. Use the history of previous solution attempts (if any) to choose the next set of values for all scenario variables taking into account the bounds on the variables and any existing constraints.
2. Pass scenario information to the simulation model for evaluation.
3. Receive results for the most recent scenario from the simulation model.
4. If a stopping criterion has been satisfied, STOP. Otherwise, return to step 1.

Sounds simple enough, and at a high level it is. But don't let this simple description fool you; simulation optimization is an extremely difficult problem. Simulation shines as a technique for modeling complex systems, making random variation of parameters and dynamic interactions a natural part of the territory. With even a few scenario variables, the list of all possible scenarios to evaluate rapidly becomes unwieldly. When you consider that each possible scenario takes substantial time to evaluate, and that each evaluation must consist of multiple runs, it is easy to see that simply enumerating every scenario is not a very feasible option.

Simulation optimization algorithms deal with these difficulties by searching the space of possible solutions in an extremely intelligent manner. The real genius, therefore, lies in how these algorithms handle step 1. The manner in which an optimization tool takes the information from scenarios already tried and uses it to identify the most efficient path through the search space can make the difference between a high quality solution and a poor quality solution. The researchers at OptTek Systems Inc. (the makers of OptQuest) have dedicated their careers to this very topic - a fact that is reflected in the quality of OptQuest's solution methods. Using a unique integration of metaheuristic procedures and classic optimization methods, OptQuest's implementation gives excellent solutions at very efficient speeds.

A Simple SIMUL8 Example

Consider a simple simulation model of a 3-work center, 2-buffer operation where work is processed in sequence (Work Center 1, Work Center 2, Work Center 3), as shown in Figure 1 below. In this simple example, the goal is to determine the optimal sizes for each of the buffers preceding the work centers so that throughput is maximized while keeping work-in-process to a minimum.

Specifically, this simple example model above takes into account the following random and dynamic elements:

• Variable process times (Table 1)
• Reliability parameters (Table 1)
• Staggered labor schedules for each machine (Table 2)

Figure 1

Table 1

(All times in minutes)	Process Time Log Normal		MTBF Exponential	MTTR Erlang
	Average	Std. Dev.	Average	Average	K
Work Center 1	8	2	200	45	15
Work Center 2	9	2	200	45	15
Work Center 3	10	2.5	200	45	15

Table 2

	Work Center 1		Work Center 2		Work Center 3
	Start	End	Start	End	Start	End
Shift 1	00:00	03:00	00:30	03:30	01:00	04:00
	03:15	06:00	03:45	06:30	04:15	07:00
	06:30	08:00	07:00	08:30	07:30	09:00
Shift 2	08:00	11:00	08:30	11:30	09:00	12:00
	11:15	14:00	11:45	14:30	12:15	15:00
	14:30	16:00	15:00	16:30	15:30	17:00
Shift 3	16:00	19:00	16:30	19:30	17:00	20:00
	19:15	22:00	19:45	22:30	20:15	23:00
	22:30	00:00	23:00	00:30	23:30	01:00

Without adequate work-in-process, work centers 2 and 3 may become starved for material and lose precious production time. However, because work center 3 is the bottleneck operation (having the longest process time), work centers 1 and 2 have the potential to continually build inventory, suggesting that some limit on the size of the associated buffers is necessary to keep work-in-process down to a reasonable level. On the other hand, by setting limits on maximum buffer sizes, work centers 1 and 2 could be prevented from working at times. If a downstream buffer is full to capacity, a work center cannot discharge its current item, which will in turn prevent it from picking up the next item, leading finally to a work stoppage.

The need to balance maximal throughput with minimal work-in-process is a common problem. Using simulation, we can vary capacity limitations to investigate the effects of varying buffer sizes on throughput, cycle time, and utilization. For example, Figure 1 is a screen capture of the simulation model at the conclusion of one scenario. The results of this simulation show a total production of 1509 units in 14 days.

To give you an idea of the range of outcomes that are possible, we'll examine how total throughput varies as the buffer sizes are changed. Table 3 shows all possible combinations of buffer sizes ranging from 5 to 12 units for Buffer 2 and 18 to 27 units for Buffer 3. Each cell of the table provides the total production for a given combination of buffer sizes. To simplify comparison, all runs presented in Table 3 used the same set of random number seeds. The highest observed production levels are highlighted. In this example, a buffer size combination of 10 and 26 (or 9 and 27) gave the lowest inventory levels among the combinations that led to the highest throughput. Increasing buffers sizes beyond these levels will not increase production past 1516 but will simply increase cycle time and inventory costs.

Table 3

Production		Buffer 3
Buffer 2		18	19	20	21	22	23	24	25	26	27
	5	1497	1499	1500	1500	1501	1501	1503	1504	1506	1507
	6	1499	1501	1503	1503	1505	1506	1507	1509	1509	1510
	7	1503	1504	1505	1506	1507	1509	1510	1511	1512	1513
	8	1504	1506	1506	1508	1509	1510	1512	1512	1513	1514
	9	1506	1506	1507	1509	1510	1511	1512	1513	1514	1516
	10	1506	1507	1509	1510	1511	1512	1513	1514	1516	1516
	11	1506	1507	1509	1510	1511	1512	1513	1514	1516	1516
	12	1506	1507	1509	1510	1511	1512	1513	1514	1516	1516

Keep in mind that Table 3 presents the results for only a single set of random number seeds. Even so, 80 simulation runs were required to populate the table. To be careful in the analysis, we would need to evaluate each of the 80 bin size combinations across several seed sets. Running just 5 seed sets per scenario leads us to a total of 400 runs: (8 values for Buffer 2) times (10 values for Buffer 3) times (5 runs for each scenario). And this is just for a very limited range of variable values on a very small problem - with a wider range, the problem grows enormously.

Optimizing with OptQuest for SIMUL8

Let's look at how this might be formulated using OptQuest to both save time and potentially identify superior results. No matter how good the simulation optimization tool, the quality of the results obtained will be tied to how well you've formulated the problem.

Decision Variables

Our first job in setting up an OptQuest simulation run is to identify the variables that can be changed in search of a good solution. In this example, we want to consider changing the values of queue capacity limitations for buffers 2 and 3. In our SIMUL8 model, those values are contained in variables called 'Max Size 2. Content' and 'Max Size 3.Content'. This is also where we set lower and upper bounds for the decision variables (Figure 2). In the Suggested Value column, we can enter an optional starting value. In our example, we'll leave that value at 1.

Figure 2

Constraints

OptQuest allows you to further limit the search space of feasible solutions by specifying constraints on the decision variables. Constraints are generally used to represent the manner in which decision variables must relate to each other. Please keep in mind that these constraints must be in the form of linear equations or inequalities. In applying constraints, you reduce the number of feasible solutions, thereby reducing the search space.

You can think of constraints as an opportunity for you to apply any prior knowledge you may have to help speed along the work of the optimizer. In our example, we don't have any hard requirements on the relationship between the two buffer sizes. However, we can apply some general common sense to see that since Work Center 3 is the bottleneck, we may expect that its' buffer will need to be at least as large as the buffers before non-bottleneck operations. Figure 3 shows how this constraint would be entered in OptQuest's constraint editor.

Figure 3

Objective Function

Whether you are seeking a good solution by hand, or setting up OptQuest, you must provide some way to determine what qualifies as a 'good' solution. This is known as an objective function, and is given in the form of minimizing or maximizing some (possibly weighted) function of decision variables and/or model results. In designing your objective function, you can think of it as a scoring function for the quality of any given solution. You want to penalize poor results and reward good ones.

OptQuest must either minimize or maximize a single value. If your objective function consists of a single component, such as throughput, you can completely specify the objective function from OptQuest. Simply select the value from a menu and choose "minimize" or 'maximize' from a drop down menu. If you want your objective function to consider multiple factors, you can easily achieve this by creating an objective function Information Store variable in your SIMUL8 model. This function can be as complex as you like, and can incorporate as many model elements as are appropriate. Make sure that you include logic to update the objective function variable at the end of each run. Once you've done this, you can choose to minimize or maximize the objective function Information Store variable in OptQuest, just as you would for any other single value.

In our example, we have two objectives. Our primary objective is to maximize our overall throughput. However, at a given throughput level, we want to minimize our buffer sizes so that we can keep work- in- process down. We want to encourage OptQuest to find solutions with the highest throughput, while at the same time discouraging solutions that involve unnecessarily high buffers. Our objective function must therefore assign a positive value to throughput and negative values to the maximum sizes for buffers 2 and 3.

Because we've said that throughput is our primary concern, we want to weight that objective more heavily. For purposes of demonstration, we'll multiply the throughput by 100 before subtracting off the buffer 2 and 3 maximum capacities. This is equivalent to saying that we'd be willing to keep up to an additional 100 items in WIP in order to get one more finished good. The appropriate multiplier value in a real application would depend upon many factors, including the inventory holding costs for WIP. These types of objective functions will often involve cost and revenue-based multipliers. Having defined our objective function in SIMUL8 (Figure 4), we need to tell OptQuest that we'd like it to maximize that value (Figure 5).

Figure 4

Figure 5

Stopping Criterion

Every program must know when to stop. In OptQuest, we have several options (Figure 6). You can specify that the optimizer should complete a given number of runs, that it run for a specified number of minutes, or until a specified day and time.

Figure 6

Having set up the decision variables, constraints, objective function and stopping criterion (plus any optional settings), you'll be ready to run the optimizer. You can let it do its thing in the background while you move on to something else. Before you go too far away, though, you may want to have a look at OptQuest's Performance Graph (Figure 7). We have found that OptQuest typically finds a good solution very quickly, with remaining runs being used to make smaller improvements. It is interesting to see the trade-off between run time and quality of solution.

Figure 7

It is interesting to watch OptQuest's progress as it moves toward an optimal solution. At each iteration, the values for all decision variables and corresponding objective function are displayed in a solutions window. At the end of the run, a Sensitivity Analysis window allows for further exploration of the potential solutions considered along the way (Figure 8).

Figure 8

In the course of solving this particular problem, OptQuest completed a total of 264 simulation runs. As with our simple hand-calculated example, several possible solutions (numbers 1-5 in Figure 8) were identified at the same throughput level. Any of these solutions will maximize throughput while keeping total work-in-process low. Better yet, these solutions were identified, evaluated and presented to us while we worked on other problems.

We intend this example to demonstrate the power of simulation optimization on even a small problem with only a few random elements. Larger scale problems are sure to benefit even more. In this case, OptQuest helped to automate the process. In a larger case, it would not only save time, but would be likely to identify good solutions that you may not have been able to identify on your own.

Simulation Optimization FAQ

Our goal in writing this article was to introduce simulation optimization and give an overview of how it would be set up on a small problem. There are many interesting technical details that we did not have space to address here. In case you'd like to dig in and find out more, we've included the answers to a few commonly asked questions.

Where can I get more information?

For generalized information, the web is always a good place to start. You will also find technical papers on simulation optimization in various journals and conference proceedings, particularly those dedicated to operations research. You might try starting with the following resources:

• OptTek Systems, Inc. keeps a series of technical white papers on its web site. You will find papers for specific application areas, as well as discussions of how OptQuest's implementation differs from other optimization tools, such as Excel Solver.
• The Annual Winter Simulation Conference is a source of many technical papers on simulation. Try searching the Winter Sim site for archived papers from past conferences.
• The ACM Transactions on Modeling and Computer Simulation published a special issue dedicated to Simulation Optimization way back in January, 2003. In the meantime, you might be interested in perusing simulation articles from past issues.
• When all else fails, try searching "Simulation Optimization" on any good search engine.

Is simulation optimization a new technique?

Well, yes and no. While it has been around for quite some time, simulation optimization is finally coming into its own. Why now? Mathematically speaking, simulation optimization is a very difficult problem. As a result, simulation optimization has been expensive and time consuming in the past. With recent advances in specialized optimization techniques geared to the specific needs of simulation, however, extremely high quality and efficient search methods are now available. What may come as even better news to SIMUL8 users is that an award winning implementation of simulation optimization, called OptQuest, is now available as a SIMUL8 plug-in.

Why isn't simulation alone enough?

First, we should say that sometimes simulation alone is enough. It all depends on the goals of your specific project. If you have only a few scenarios to consider, or if you will be using simulation in a purely evaluative mode, there is no need to go to simulation optimization. However, on those occasions when you have many scenarios to consider, simulation optimization can help you efficiently find a good solution.

Why not just use a standard optimization package, such as Excel Solver?

Simulation problems are by their nature, very messy. If they weren't, you probably wouldn't have gone to the trouble to create a simulation model in the first place. Problems that are suited for simulation tend to have nonlinearities and complex interrelationships between variables that can't be adequately modeled in standard optimization packages. Add to that the complexity that arises from having randomly varying parameters and you need a specialized set of algorithms. For more information on how OptQuest specifically compares to Excel solver, see the white paper on OptTek's website.
Do you have any specific tips for using OptQuest for SIMUL8?

Successful use of any optimization package always comes back to properly setting up constraints and objective functions.

Carefully consider the ranges of your variables. The space of potential solutions is huge, even for smallish problems. Therefore, it is worthwhile to exclude as many possibilities as you can. If cutting staff in one department is infeasible, perhaps for political reasons, don't let your simulation model waste time considering it.

And speaking of resource levels...It is common to use a resource level as an OptQuest decision variable. If you try this with one of your models, be sure to set the value of replicate appropriately on any work centers that may be using that resource type. You'll need to set the replicate number high enough to accommodate the full range of resource levels that may be considered by the optimization. If you don't, SIMUL8 can't make use of the additional resources and will therefore report back to OptQuest that the scenario has a greater cost with no performance improvement. As a result, any scenario with a resource level higher than the replicate value would automatically be eliminated as a good solution, perhaps falsely so.

What are some common application areas?

Now that high quality efficient simulation optimization algorithms are available, we expect to see the number of applications growing rapidly. Just  a few of the many areas suitable for simulation optimization include:

• Supply chain optimization
• Workflow management in production environments
• Ground water treatment planning
• Call center operations