Simulation optimization: a comprehensive review on theory and applications

IIE Transactions, Nov, 2004 by Eylem Tekin, Ihsan Sabuncuoglu

1. Introduction

With the continuing developments in computer technology, simulation is receiving increasing attention as a decision-making tool. Most real-world systems are so complex that computing values of performance measures and finding optimal decision variables analytically is very hard and sometimes impossible. Therefore, computer simulation is frequently used in evaluating complex systems and optimizing responses.

The problem under consideration is the maximization or minimization of the expected value of the objective function with respect to its constraint set as given below:

(max)[min.[X[epsilon][THETA]]]H(X). (1)

where H(X)=E[L(X,[epsilon])] is the performance measure of the problem. The quantity L(X,[epsilon]) will be called the sample performance, [epsilon] represents the stochastic effects in the system, X is a p-vector of controllable factors and [THETA] is the constraint set on X. If H(X) is a one-dimensional vector, the problem is single objective optimization, whereas if its dimension is more than one, the problem becomes multiobjective. The optimum is denoted by X*. Without loss of generality, we will consider the minimization problem throughout the paper.

A variety of techniques and approaches have been proposed to solve the above optimization problem. In the literature, there are also several survey papers that discuss foundations, theoretical developments and applications of these techniques (Meketon, 1987; Jacobson and Schruben, 1989; Safizadeh, 1990; Azadivar, 1992; Fu. 1994a; Andradottir, 1998; Swisher et al., 2000). The simulation optimization techniques covered in these papers are listed in Table 1. The objective of this paper is to provide a more comprehensive coverage of these techniques and their applications. Besides reviewing the "traditional" methods, we give emphasis to recent developments in this area (i.e., global optimization methods such as evolutionary algorithms, simulated annealing, and tabu search).

We classify the existing studies under two main headings: (i) local optimization; and (ii) global optimization. Local optimization techniques are further classified in terms of discrete and continuous parameter spaces. Figure 1 shows such a classification scheme. In this paper, in addition to reviewing the theoretical aspects of these techniques, we also discuss their applications to various production systems.

The rest of the paper is organized as follows. In Section 2.1, we focus on techniques for the discrete-parameter case such as ranking and selection, multiple comparison procedures, random search, Nelder-Mead simplex/complex search, Hooke-Jeeves pattern search and the single-factor method. For the continuous-parameter space case, we consider response surface methodology, gradient-based methods (finite difference estimates, perturbation analysis, frequency-domain analysis, likelihood ratio estimators) and stochastic approximation methods in Section 2.2. In Section 3, we discuss global search methods such as evolutionary algorithms, simulated annealing, tabu search, Bayesian/sampling algorithms, and the gradient surface method. In Section 4, we review the studies for multiple objective problems. The paper ends with concluding remarks and suggestions for further research in Section 5.

2. Local optimization

Local optimization problems are discussed in terms of discrete and continuous decision spaces. In a discrete space, decision variables take a discrete set of values such as the number of machines in the system, alternative locations of depots, different scheduling rules or policies, etc. On the other hand, in a continuous space, the feasible region consists of real-valued decision variables such as order quantity and reorder quantity in inventory problems, release time of factory orders, etc.

[FIGURE 1 OMITTED]

2.1. Discrete decision space

The discrete case can further be classified into: finite parameter space and infinite parameter space. In the finite case, X [member of] {[[lambda].sub.1],...,[[lambda].sub.k]} where [[lambda].sub.i] is one of the k points in the feasible region and the aim is to find X*=[[lambda].sub.i]. The two most popular methodologies for the class of problems are: (i) ranking and selection; and (ii) multiple comparison procedures. For excellent reviews of these two classes of techniques, one can refer to Bechhofer et al. (1995) and Goldsman and Nelson (1998). Other methods (e.g., random search, Nelder-Mead simplex/complex search, single-factor method. Hooke-Jeeves pattern search) can operate in the infinite parameter space.

There are two main approaches with respect to ranking and selection. The first is the indifference-zone approach (Dudewicz and Dalal, 1975). This method guarantees that the performance measure value of the selected [[lambda].sub.i] differs from the optimal solution value by at most a small amount [delta], with a probability of at least P*. The second approach is called subset selection. It aims to select a subset of at most m [less than or equal to] k [[lambda].sub.i]'s and guarantees that this subset contains at least the best [[lambda].sub.i], with probability of at least P*. The latter approach is more useful when the number of choices is quite large. Sullivan and Wilson (1989) propose two extensions to the subset selection procedure for normal populations with unknown moments. Butler et al. (2001) combine multiattribute utility theory with the indifference-zone approach to make comparisons of systems that have multiple performance measures.