الگوریتم بهینه سازی ترتیبی مبتنی بر نظریه برای طبقه ای از مسائل بهینه سازی شبیه سازی و کاربرد آن

In this paper, we have proposed an ordinal optimization theory-based two-stage algorithm to solve for a good enough solution of the stochastic simulation optimization problem with huge input-variable space Θ. In the first stage, we construct a crude but effective model for the considered problem based on an artificial neural network. This crude model will then be used as a fitness function evaluation tool in a genetic algorithm to select N excellent settings from Θ. In the second stage, starting from the selected N excellent settings we proceed with the existing goal softening searching procedures to search for a good enough solution of the considered problem. We applied the proposed algorithm to the reduction of overkills and retests in a wafer probe testing process, which is formulated as a stochastic simulation optimization problem that consists of a huge input-variable space formed by the vector of threshold values in the testing process. The vector of good enough threshold values obtained by the proposed algorithm is promising in the aspects of solution quality and computational efficiency. We have also justified the performance of the proposed algorithm in a wafer probe testing process based on the ordinal optimization theory.

Simulation optimization problems could be viewed as optimization problems of a system whose outputs can only be evaluated by simulations (Fu, Glover, & April, 2005). Thus, the objective of simulation optimization is to find the optimal settings of the input variables to the simulated system that makes the output variables at their best or optimal conditions. Various methods had been developed for this purpose such as the gradient search-based methods (Nocedal and Wright, 2006 and Kim, 2006), the stochastic approximation methods (Theiler and Alper, 2006 and Spall, 2003), the sample path methods (Hunt, 2005), the response surface methods (Myers, Montgomery, Vining, Borror, & Kowalski, 2004), and heuristic search methods. These methods had been thoroughly discussed in April, Glover, Kelly, and Laguna (2003). Among them, the heuristic search methods including the genetic algorithm (GA) (Haupt & Haupt, 2004), the simulated annealing (SA) method (Suman & Kumar, 2006), and the tabu search (TS) method (Hedar & Fukushima, 2006) are frequently used in simulation optimization (Blum and Roli, 2003 and Tekin and Sabuncuoglu, 2004). According to an empirical comparison of these algorithms (Lacksonen, 2001), GA showed the capacity to robustly solve large problems and performed well over the others in solving a wide variety of simulation problems. Despite the success of several applications of the above heuristic methods (Ahmed, 2007 and Fattahi et al., 2007), many technical hurdles and barriers to broader application remain as indicated in (Dréo, Pétrowski, Siarry, & Taillard, 2006). Chief among these is speed, because using the simulation to evaluate the output variables for a given setting of the input variables is already computationally expensive not even mention the search of the best setting provided that the input-variable space is huge. Furthermore, simulation often faces situations where variability is an integral part of the problem. Thus, stochastic noise further complicates the simulation optimization problem. The purpose of this paper is to resolve this challenging stochastic simulation optimization problem effectively.The basic idea of the OO theory-based goal softening strategy is to reduce the searching space gradually, and its existing searching procedures can be summarized in the following (Lau & Ho, 1997): (i) uniformly select N, say 1000, settings from Θ. (ii) Evaluate and order the N settings using a crude model of the considered problem, then pick the top s, say 50, settings to form the selected subset (SS), which is the estimated good enough subset (GS). A good enough subset is defined as the subset consisting of the top n% solutions in the input-variable space. (iii) Evaluate and order all the s settings in SS using the exact model, then pick the top k (⩾1) settings. In OO theory (Lau & Ho, 1997), the model noise is used to describe the degree of roughness of the crude model. The OO theory had shown that for N = 1000 in (i) and a crude model with significant noise in (ii), the top setting (i.e., k = 1) selected from (iii) with s ≅ 50 must belong to the GS with probability 0.95, where GS represents a collection of the top 5% actually good enough settings among N. This means the actual top setting in SS selected from (iii) is among the actual top 5% of the N settings with probability 0.95. However, the good enough solution of problem (1) that we are searching for should be a good enough setting in Θ instead of the N settings unless Θ is as small as N ( Chen et al., 1999 and Ho et al., 2007). As indicated in a recent paper by Lin and Ho (2002), under a moderate modeling noise, the top 3.5% of the uniformly selected N settings will be among the top 5% settings of a huge Θ with a very high probability (⩾0.99), and the best case can be among the top 3.5% settings of Θ provided that there is no modeling error. However, for Θ with size of 1030, a top 3.5% setting is a setting among the top 3.5 × 1028 ones. This certainly not seems to be a good enough solution in the sense of practical optimization, however, it is acceptable only when Θ consists of lots of good settings so that even if the performance order of the selected setting is not practically good enough, the corresponding objective value is. As a matter of fact, most of the practical stochastic simulation optimization problems do not have lots of good settings; otherwise, finding a good enough solution will not be difficult. Therefore, to apply the existing goal softening searching procedures, we need to develop a new scheme to select N excellent settings from Θ to replace (i) so as to ensure the final selected setting is a good enough solution of (1) from the practical viewpoint. Heuristic methods for obtaining N excellent settings may depend on how well one’s knowledge about the considered system. For instance in the optimal power flow problems with discrete control variables, Lin et al. proposed an algorithm based on the OO theory and engineering intuition to select N excellent discrete control vectors (Lin, Ho, & Lin, 2004). However, the engineering intuition may work only for specific systems. Thus, in this paper, we will propose an OO theory-based systematic approach to select N excellent settings from Θ and combine with the existing goal softening searching procedures to find a good enough solution of (1). The presentation of this OO theory-based two-stage algorithm to solve (1) for a good enough solution is a novel approach in the area of simulation optimization and is one of the contributions of this paper. Reducing overkills and retests is an important issue in semiconductor wafer probe testing process. Taking the chip demand into account, we have formulated this problem as a stochastic simulation optimization problem, which possesses a huge input-variable space and is most suitable for demonstrating the validity of the proposed OO theory-based two-stage algorithm. This novel formulation as well as the novel solution methodology for this important and practical stochastic optimization problem is another contribution of this paper. We organize our paper in the following manner. In Section 2, we will describe the OO theory-based two-stage approach and present the proposed two-stage algorithm. In Section 3, we will introduce the stochastic optimization problem of reducing overkills and retests in semiconductor wafer probe testing process and present the application of the proposed algorithm. In Section 4, we will show the test results of applying the proposed algorithm on a real case and demonstrate the solution quality and the computational efficiency by comparing with a vast number of randomly generated solutions and competing methods, respectively. We have also justified the performance of the proposed algorithm in a wafer probe testing process based on the ordinal optimization theory. Finally, we will make a conclusion in Section 5.

To cope with the computationally intractable stochastic simulation optimization problems, we have proposed an ordinal optimization theory-based two-stage algorithm to solve for a good enough solution using reasonable computational time. To demonstrate the applicability of the proposed algorithm, we have used it to solve for a vector of good enough threshold values to reduce overkills and retests in a wafer probe testing process of a wafer foundry. We have tested the performance of the solution we obtained using the real data and found that the resulting average number of overkills and retests per wafer lie almost on the boundary resulted from the optimal vector of threshold values of the considered stochastic optimization problem. This indicates that the proposed algorithm will not only control the tolerable level of retests by taking the various chip demand into account but also provide a near optimal vector of threshold values. We have demonstrated the computational efficiency of the proposed algorithm by comparing with the genetic algorithm and the simulated annealing method and found that when the latter two methods consume more than 30 times of the CPU times consumed by the proposed algorithm, the best so far objective values they obtained are still not better than that obtained by the proposed algorithm. We have also justified the performance of the proposed algorithm in a wafer probe testing process based on the ordinal optimization theory.