بهینه سازی شبیه سازی چند هدفه با استفاده از تحلیل پوششی داده ها و الگوریتم ژنتیکی: برنامه خاص تعیین سطوح منابع مطلوب در خدمات جراحی

Simulation is a powerful tool for modeling complex systems with intricate relationships between various entities and resources. Simulation optimization refers to methods that search the design space (i.e., the set of all feasible system configurations) to find a system configuration (also called a design point) that gives the best performance. Since simulation is often time consuming, sampling as few design points from the design space as possible is desired. However, in the case of multiple objectives, traditional simulation optimization methods are ineffective to uncover the efficient frontier. We propose a framework for multi-objective simulation optimization that combines the power of genetic algorithm (GA), which can effectively search very large design spaces, with data envelopment analysis (DEA) used to evaluate the simulation results and guide the search process. In our framework, we use a design point's relative efficiency score from DEA as its fitness value in the selection operation of GA. We apply our algorithm to determine optimal resource levels in surgical services. Our numerical experiments show that our algorithm effectively furthers the frontier and identifies efficient design points.

Real-world problems are often too complex to model analytically that allows straightforward optimization of performance measures to find the best system configuration (represented as a design point). Here, by design point, we mean a particular set of the input variables (also called factors or parameters) that determines the “configuration” or “design” of the system in question [1]. In other words, a design point is a vector composed of all input variables. Design space refers to the set of all feasible design points satisfying system constraints. Performance measures (also called outputs or responses) are quantitative criteria that are used to evaluate system performance [1]. Real-world problems are often large-scale and therefore have a large design space making it difficult to identify the best design point. One effective method to solve such problems is simulation optimization, which is a powerful decision-making tool that is capable of capturing intricate relationships and interactions among various entities in a real-world complex system and identifying the best design point(s) [1], [2], [3], [4], [5] and [6]. In particular, simulation optimization [1] and [7] refers to methods that search design points within the design space to optimize performance measures. Simulation optimization has been successfully used to solve difficult real-world problems such as inventory control, resource allocation, scheduling, and investment portfolio optimization [1]. Fu et al. [1] and Fu [7] surveyed several classical simulation optimization approaches including stochastic approximation [8] and [9], response surface methodology [1] and [10], random search [2] and [11], and sample path optimization [7], [12] and [13]. The main drawbacks of these methods are that they are usually designed to handle cases with only a single performance measure [1] and that they often require a substantial amount of computation [4]. In order to increase efficiency of simulation optimization techniques, several meta-heuristic approaches including genetic algorithm, simulated annealing, and tabu search have been explored [2] and [14]. Many real-world problems have multiple (and often conflicting) criteria that need to be optimized simultaneously [14]. In addition to usual complexities associated with general multi-objective optimization problems (e.g., conflicting objectives, intense computational requirement due to need for identifying Pareto-optimal solution set) [14], [15], [16], [17], [18] and [19], time-consuming sampling and stochasticity associated with complex system simulations makes multi-objective simulation optimization very difficult. For these reasons, Tekin and Sabuncuoglu [3] in their comprehensive survey of several simulation optimization approaches indicated that only limited work has been done in multi-objective simulation optimization. This clearly shows the need for a multi-objective simulation optimization approach that can efficiently (i.e., as few samples as possible) and effectively (i.e., identification of a large portion of the Pareto-optimal design points, also called the efficient frontier) optimize a complex system. In this paper, we propose a framework for multi-objective simulation optimization that combines genetic algorithm with data envelopment analysis (DEA) used to evaluate the simulation results and guide the search process. There have been attempts in the literature to combine DEA and simulation in a mutually supporting role. For example, Greasley [20] developed a three-stage process to improve the performance of operating units. In the first stage, historical or simulated data are obtained for all units. The efficiencies of these units are then evaluated using DEA and a benchmark design is identified in the second stage. In the third stage, the “weaker” units (in the sense of DEA efficiency) are simulated using benchmark and current designs. Furthermore, there have recently been efforts to evaluate simulation output using Pareto optimality. Lee et al. [21], for instance, considered a multi-objective ranking and selection problem, where there are multiple performance measures associated with a design point. They define a performance index indicating the extent to which a design point is non-dominated and define a simple procedure to allocate simulation replications subject to a limited simulation budget. Dellino et al. [22] propose a mathematical programming model to minimize the mean output from simulation subject to an upper-bound constraint on the output variance. Since it is difficult to determine such a threshold value on the output variance, they estimate the Pareto frontier showing the trade-off between the output and its variance. There have also been numerous attempts to apply genetic algorithm to multi-objective simulation optimization. Several of such works appeared in the supply chain management literature [23], [24], [25] and [26]. One notable study is by Lee et al. [27], who developed a multi-objective simulation optimization framework integrating genetic algorithm with a multi-objective computing budget allocation method to solve an aircraft spare parts allocation problem. In their framework, they define a performance index, which measures the probability that a design point is non-dominated, and use this index to evaluate the fitness of a design point in the GA selection process. In contrast, our framework uses a design point's relative efficiency score from DEA as its fitness value in the selection operation of GA. Through numerical experiments, we show our method can naturally handle multiple performance measures and efficiently identify near Pareto-optimal design points. Below, we give a brief overview of the genetic algorithm and data envelopment analysis and review very limited previous work that attempted combining these two techniques to solve (deterministic) multi-objective optimization problems. Genetic algorithm: Genetic algorithm (GA) developed by John Holland at the University of Michigan is a meta-heuristic that searches the feasible region of an optimization problem by mimicking the process of natural evolution [28]. GA seeks to improve a whole group of solutions by treating them as individuals in a population and generating a new generation from these individuals using processes similar to those in natural evolution such as mutation and crossover. GA has been applied to many problems in various domains such as engineering, finance, and economics. Jones et al. [14] show that GA is the most popular meta-heuristic with 70% of the articles surveyed using GA as the primary methodology due to its popularity and flexibility. GA has also been successfully used to solve multi-objective problems [29], [30], [31], [32] and [33]. The main idea behind multi-objective GA is to use a sorting algorithm to divide solutions in a generation into different domination levels and assign a fitness value to each solution based on its domination level [31]. Data envelopment analysis: Data envelopment analysis (DEA) [34] is used to evaluate the relative efficiency of a set of decision making units (DMUs), which consist of multiple inputs and multiple outputs. DEA uses linear programming to develop an efficiency frontier, which consists of efficient DMUs. Inefficient DMUs are then projected onto the efficient frontier by either increasing their output levels or decreasing their input levels. Since the first DEA model was introduced by Charnes et al. [35] in 1978, it has been adapted, modified, and extended by many researchers [36], [37], [38] and [39]. Integration of GA and DEA: Limited work exists in the literature combining GA with DEA to solve multi-objective optimization problems. Whittaker et al. [15] developed a hybrid GA using activity analysis (or an appropriate DEA model) as local search function and the non-dominated sorting-II (NDSA-II) [31] as a fitness evaluation function in selecting parents. They use activity analysis, which can be replaced with DEA depending on the application, as a local search method to maximize profit. In other words, activity analysis is used to calculate local optimal performance measures (e.g., maximizing profit and minimizing pollution) for a given design point. In contrast, we use simulation to estimate the performance measure for a given design point. While Whittaker et al. use NSGA-II [31] to assign fitness based on calculated performance measures from activity analysis or DEA, we use efficiency scores from DEA as a design point's fitness value in the selection operation of GA. Yun et al. [16] and [17] used generalized DEA as a selection function in GA to find efficient frontiers in deterministic multi-objective optimization problems. Our framework is similar to that developed by Yun et al. [16] and [17] except that we use discrete-event simulation to evaluate multiple performance measures for a given design point. This added flexibility makes our framework to be applicable to a wide range of complex-system optimization problems having intricate relationships and interactions among various entities. In our framework, we use a design point's relative efficiency score from DEA as its fitness value in the selection operation of GA. In other words, the probability that a design point is selected as a parent is directly proportional to its relative efficiency score. This implies that the relative efficiency scores from DEA dictate the influence the parent design points will have on future generations. Another important difference between our framework and that developed by Yun et al. [16] and [17] is that the DEA component in our framework evaluates the efficiency relative to the design points in the current generation and all efficient design points identified in previous generations instead of simply evaluating the efficiency of design points within the current generation. This substantially improves the discriminatory power of DEA and helps distinguishing truly efficient design points from inefficient ones. While Diewert [40] originally developed this idea when defining a sequential method for efficiency analysis, to the best of our knowledge, this is the first work that applies Diewert's method to a multi-objective GA/DEA framework. The rest of the paper is organized as follows. In Section 2, we give a detailed description of our multi-objective simulation optimization framework composed of GA, which is used to generate design points, a simulation model, which is used to estimate performance measures associated with each design point, and DEA, which is used to determine the fitness of design points in the selection process of GA. In Section 3, we perform a thorough analysis of a case study from a complex healthcare setting to demonstrate the ability of our algorithm to efficiently identify near Pareto-optimal design points. The paper ends with conclusions and future research directions in Section 4.

In this paper, we develop a framework for multi-objective simulation optimization that combines the genetic algorithm with data envelopment analysis used to evaluate the simulation results and guide the search process of genetic algorithm. To evaluate the effectiveness of our algorithm in terms of finding Pareto-optimal design points and furthering the efficient frontier, we define two metrics, namely average efficiency score and percentage of efficient design points in each generation, with respect to an approximation of the “true” frontier obtained by sampling a large number of design points from the design space. The DEA component in our framework evaluates the efficiency relative to the current design points and all efficient design points identified in previous generations instead of simply evaluating the efficiency of design points in the current generation relative to each other. This substantially improves the discriminatory power of DEA and helps distinguishing truly efficient design points from inefficient ones. This approach, to the best of our knowledge, has not been used before in the works that combine GA and DEA. Our framework has been applied to a case study to identify efficient design points that correspond to Pareto-optimal usage of resources in surgical services. Surgical services are a complex system where several resources interact with each other and are used in multiple stages and high uncertainty in surgical procedure durations makes scheduling a challenge. For these reasons, it is not easy to establish analytical relationships between the input variables and performance measures. The numerical experiments demonstrate the applicability of the framework and the effectiveness of the algorithm to search large design spaces of complex systems such as surgical services. As shown in the case study, the algorithm approximates the overall efficient frontier by iteratively identifying design points that are increasingly efficient. Such a method can be adapted and used in other application domains. One inherent assumption in many of the DEA models is that the inputs and outputs should conform to interval scale implying that equal intervals of the scale have the same value. When this is coupled with the freedom to select weights for inputs and output, the underlying implication is that of a linear value function [77]. However, not all problems lend themselves to such a linearity assumption. Future research will focus on ways to relax the linearity assumptions in the formulations and adapt the framework proposed here. Another important future research direction is to apply our framework to problems where inputs are not comparable in the usual economic sense such as optimizing surgery schedules, which would be represented as inputs in the DEA component of our framework. Lovell and Pastor studied several radial DEA models without (or with constant) inputs or outputs [78]. These types of models can be used to extend our framework to simulation optimization problems where decision variables cannot be readily fit into a DEA model as inputs. In its current form, important qualitative variables such as quality of care cannot be readily incorporated into our GA/DEA framework. Since the omission of such significant variables in DEA has serious implications, future work will focus on incorporating these variables such as quality of care in strategic optimization of resource levels in surgical services. Lastly, a promising research direction is to incorporate a multi-objective computing budget allocation method into our framework to more efficiently allocate simulation replications subject to a limited simulation budget [21] and [27].