Glaucoma is the leading cause of irreversible blindness worldwide. The clinical standard for glaucoma diagnosis and progression tracking remains visual field (VF) testing via standard automated perimetry. One outstanding challenge of many ophthalmic prediction tasks is the issue of class imbalance, where the majority class outnumbers the minority class(es). Although this issue has been reported in several prior studies on the prediction of VF progression or glaucoma, it has not been addressed in the context of longitudinal VF data. In this work, we proposed, VF-Transformer, a transformer-based framework for VF progression prediction based on longitudinal VF examination results. In particular, we addressed the class imbalance issue by incorporating our proposed inverted class-dependent temperature (ICDT) loss and weight normalization. The proposed framework was developed and evaluated on a public VF dataset and further validated on an external hospital dataset, using accuracy, sensitivity, specificity, and area under the receiver operating characteristic curve (AUC) as evaluation metrics. Extensive experiments and comparisons with existing state-of-the-art methods and class imbalance handling strategies confirmed the effectiveness of the proposed framework in predicting VF progression in the presence of class imbalance.

Personalized medication recommendations aim to suggest a set of medications based on the clinical conditions of a patient. Not only should the patient’s diagnosis, procedure, and medication history be considered, but drug-drug interactions (DDIs) must also be taken into account to prevent adverse drug reactions. Although recent studies on medication recommendation have considered DDIs and patient history, personalized disease progression and prescription have not been explicitly modeled. In this work, we proposed FastRx, a Fastformer-based medication recommendation model to capture longitudinality in patient history, in combination with Graph Convolutional Networks (GCNs) to handle DDIs and co-prescribed medications in Electronic Health Records (EHRs). Our extensive experiments on the MIMIC-III dataset demonstrated superior performance of the proposed FastRx over existing state-of-the-art models for medication recommendation. The source code and data used in the experiments are available at https://github.com/pnmthaoct/FastRx.

Monte Carlo simulation is a commonly used tool for evaluating the performance of complex stochastic systems. In practice, simulation can be expensive, especially when comparing a large number of alternatives, thus motivating the need to intelligently allocate simulation replications. Given a finite set of alternatives whose means are estimated via simulation, we consider the problem of determining the subset of alternatives that have means smaller than a fixed threshold. A dynamic sampling procedure that possesses not only asymptotic optimality, but also desirable finite-sample properties is proposed. Theoretical results show that there is a significant difference between finite-sample optimality and asymptotic optimality. Numerical experiments substantiate the effectiveness of the new method. Summary of Contribution: Simulation is an important tool to estimate the performance of complex stochastic systems. We consider a feasibility determination problem of identifying all those among a finite set of alternatives with mean smaller than a given threshold, in which the means are unknown but can be estimated by sampling replications via stochastic simulation. This problem appears widely in many applications, including call center design and hospital resource allocation. Our work considers how to intelligently allocate simulation replications to different alternatives for efficiently finding the feasible alternatives. Previous work focuses on the asymptotic properties of the sampling allocation procedures, whereas our contribution lies in developing a finite-budget allocation rule that possesses both asymptotic optimality and desirable finite-budget properties.

In order to generalize the applicability of Conditional Value at Risk, one of the most widely used measurements used in financial risk management, we develop a solution methodology for the conditional expectation (CE)-based simulation optimization problems. To optimize CE-based objective functions in a highly generalized context, we propose a gradient-free, direct search optimization method, called SNM-CE, which inherits the search framework of Stochastic Nelder-Mead (SNM) Simplex Method but further incorporates effective mechanisms designed for handling problems with CE-based objective functions. As we assume the underlying problem is complicated enough that no closed-form expression can represent the objective function, stochastic simulation is applied to estimate CE. We apply Importance Sampling (IS) as a variance reduction technique, which, combined with a newly-developed methodology, called SOCBA-mn, ensures that simulation resources are used with great efficiency. We show that SNM-CE can converge to the true global optimum with probability one (w.p.1) like SNM. An extensive numerical study and a communication system-based empirical study are both conducted to demonstrate the effectiveness, efficiency and viability of this research in both theoretical and practical settings. Note to Practitioners—This paper develops a direct search algorithm, called SNM-CE, used for solving conditional expectation-based simulation optimization problems. By tackling conditional expectation-based problems, SNM-CE fills a gap in the stochastic optimization literature which has traditionally focused on expectation- or quantile-based objective functions. SNM-CE possesses a high degree of flexibility and generalizability which users can benefit from in solving real-world applications. For example, the$\alpha $value in the CE-based simulation optimization formulation can be freely adjusted. In other words, the quantile value above which the CE is estimated and optimized can be set according to the needs of the practitioner and/or characteristics of the problem to be solved. Also, SNM-CE is designed such that instead of setting the$\alpha $value, the user may choose to utilize a particular numerical value of the objective function as the threshold for the CE estimation and optimization. SNM-CE is also simple in terms of implementation and, being a direct search method, does not impose many assumptions about the structure of the underlying objective function and does not necessitate the use of gradient information in the search process. As one application example, SNM-CE can be utilized to select the operational parameters which minimize the average delay in the manufacturing of semiconductors given that the delay exceeds the 90th percentile of simulated delay times.

A novel methodology is introduced for optimally allocating a sampling budget. Sampling budget allocation problems arise frequently in various settings. For example, in the design of complex engineering systems, given both the complexity of these systems and the imperfect information on new technologies, designers often face deep uncertainty as to system performance. Consequently, designers need to sample multiple alternative designs under a limited budget. This article proposes a minimax regret approach to allocate the sampling budget in the presence of deep uncertainty pertaining to system performance. The objective is to maximize the probability of selecting the design with the minimum–maximum regret under a limited sampling budget and imperfect information. To effectively solve the minimax regret problem, an approximation methodology that provides good solutions with quantifiable uncertainty is developed. The essence of the methodology, which has the added benefit of being generally applicable to any multilevel optimization, is that all but the first level of multilevel optimization can be eliminated via a response surface. By sampling many values of a higher level decision’s variables, solving the next lower level optimization given those samples values, and calibrating a response surface to the objective function value eliminate one required optimization. Doing this repeatedly reduces the complexity of the multilevel optimization to a standard optimization. Regardless of the number of levels in the optimization, repeating this process ultimately leaves one with a single optimization whose objective function can be directly computed, given the highest level variables. Numerical experiments with two sampling allocation examples demonstrate both the benefit of the robust sampling budget allocation versus nonrobust formulations and the effectiveness of the proposed solution approach.

In a wireless network with dynamic spectrum sharing, tracking temporal spectrum holes across a wide spectrum band is a challenging task. We consider a scenario in which the spectrum is divided into a large number of bands or channels, each of which has the potential to provide dynamic spectrum access opportunities. The occupancy times of each band by primary users are generally non-exponentially distributed. We develop an approach to determine and parameterize a small selected subset of the bands with good spectrum access opportunities, using limited computational resources under noisy measurements. We model the noisy measurements of the received signal in each band as a bivariate Markov modulated Gaussian process, which can be viewed as a continuous-time bivariate Markov chain observed through Gaussian noise. The underlying bivariate Markov process allows for the characterization of non-exponentially distributed state sojourn times. The proposed scheme combines an online expectation-maximization algorithm for parameter estimation with a computing budget allocation algorithm. Observation time is allocated across the bands to determine the subset of G*out of G frequency bands with the largest mean idle times for dynamic spectrum access and at the same time to obtain accurate parameter estimates for this subset of bands. Our simulation results show that when channel holding times are non-exponential, the proposed scheme achieves a substantial improvement in the probability of correct selection of the best subset of bands compared to an approach based on a (univariate) Markov modulated Gaussian process model.

We propose a dynamic sampling allocation and selection paradigm for finding the alternative with the optimal quantile in a Bayesian framework. Myopic allocation policies (MAPs), analogous to existing methods in classic ranking and selection for selecting the alternative with the optimal mean, and computationally efficient selection policies are derived for selecting the alternative with the optimal quantile. Under certain conditions, we prove that the proposed MAPs and selection procedures are consistent, which means that the best quantile would be eventually correctly selected as the sample size goes to infinity. Numerical experiments demonstrate that the proposed schemes can significantly improve the performance.

Under a dynamic spectrum access paradigm, a set of L spectrum bands licensed to primary users provide opportunities for an unlicensed secondary user to gain access to spectrum left idle by a primary user. We model the received noisy signal measurements on each band as a continuous-time Markov chain observed through a discrete-time Gaussian channel. Based on this model, we develop a scheme for estimating the parameters of the subset of L* <; L bands that offer the “best” opportunities for dynamic spectrum access in the sense of largest mean idle periods. Our approach consists of a Markov modulated Gaussian process model, an associated expectation-maximization algorithm, and a computing budget allocation scheme for allocating sensing effort across the spectrum bands over a sequence of observation intervals. The sensing effort allocation scheme maximizes the probability that the L* best bands will be determined from their parameter stimates obtained in the next observation interval. Simulation results are presented to demonstrate the performance of the proposed scheme.

In this paper, an input-decimation technique for the recursive discrete Fourier transform (RDFT)/inverse DFT (RIDFT) algorithm is proposed for the high-speed broadband communication systems. It is worth noting that the input-decimation approach is presented to decrease the number of input sequences for the recursive filter so that the computation cycle of RDFT/RIDFT can be shortened to meet the commuting time requirement (3.6 μs) for the high-speed broadband communication systems. Therefore, the input-decimation RDFT/RIDFT algorithm is able to carry out at least 55.5% reduction of the total computation cycles compared with the considered algorithms. Furthermore, holding the advantages of input-decimation technique, the computational complexities of the real-multiplication and -addition are reduced to 41.3% and 22.2%, respectively. The area and the power consumption can be minimized by employing the cost-efficient constant multiplier with the refined signed-digit expression of twiddle factors. Finally, the physical implementation results show that the core area is 0.37×0.37 mm2with 0.18 μm CMOS process. The power consumption is 5.16 mW with the supply voltage of 1.8 V and the operating clock of 40 MHz. The proposed design can achieve 258 million of computational efficiency per unit area (CEUA) and really outperform the previous works.

The N-k problem is very well known in the power industry and it tries to answer the question whether there exists a set of k lines in a power network with N elements whose removal would cause the failure of the system. In practice, it is common to evaluate a system according to an N-1 criterion, i.e., k = 1. While this problem has traditionally been considered in a deterministic setting, stochastic behavior within the system is important especially in the context of extreme events. A number of stochastic Monte Carlo models have been proposed to estimate the probability of cascading failures. In this paper, we deal with simulation budget allocation of the stochastic N-1 problem. More specifically, we assume that a simulation model is able to provide us an estimate of the system failure rate when any line is tripped. It is not difficult to see how simulation of all configurations to some certain accuracy can become computationally expensive with the growth of N. Under such a setting, we transform the N-1 problem into a stochastic selection process with optimal computing budget allocation (OCBA): given N configurations, we would like to sequentially allocate a certain number of simulation replications in order to answer the question whether the system is reliable or not. We show through theoretical analysis and numerical experiments that the probability of correctly identifying the system reliability state can be increased by applying OCBA allocation rules in the simulation budget allocation process.

In dynamic or opportunistic spectrum access, the primary user (PU) alternates between an idle and an active state, and a secondary user (SU) may access the channel during the idle periods. In multiband spectrum sensing, an SU tracks the PU state on a given set of channels to determine spectrum access opportunities. In this context, we address the following problem: Given amp;#924; channels, determine the best subset of amp;#925; amp;#8804; amp;#924; channels with respect to spectrum access opportunities and, at the same time, estimate the parameter of the PU state process for each channel within the selected subset. Specifically, we model the PU state on the given set of channels by amp;#924; independent, two-state continuous-time Markov chains. Over a given interval of time, our goal is to determine, with high probability, the amp;#925; channels with the largest mean idle periods and, at the same time, to accurately estimate the parameter of each channel in the selected subset. We adapt the optimal computing budget allocation (OCBA) methodology from the field of simulation optimization to allocate the total time budget for sensing the $N$ channels in order to perform the channel subset selection and parameter estimation. Simulation results are presented to demonstrate the performance of the proposed algorithm.

Many problems in automation and manufacturing are most suitable to be modeled as simulation optimization problems. Solving these problems typically involves two efforts: one is to explore the solution space, and the other is to exploit the performance values of the sampled solutions. When the amount of computing budget is limited, we need to know how to balance these two efforts in order to obtain the best result. In this study, we derive two measures to quantify the marginal contribution of exploring the search space and exploiting the performance values. A sequential budget allocation framework is designed by keeping the two measures approximately the same at each iteration. Numerical experiments on both continuous and discrete simulation optimization problems demonstrate that our new approach can significantly enhance the computing efficiency.

Particle Swarm Optimization (PSO) is a popular metaheuristic for deterministic optimization. Originated in the interpretations of the movement of individuals in a bird flock or fish school, PSO introduces the concept of personal best and global best to simulate the pattern of searching for food by flocking and successfully translate the natural phenomena to the optimization of complex functions. Many real-life applications of PSO cope with stochastic problems. To solve a stochastic problem using PSO, a straightforward approach is to equally allocate computational effort among all particles and obtain the same number of samples of fitness values. This is not an efficient use of computational budget and leaves considerable room for improvement. This paper proposes a seamless integration of the concept of optimal computing budget allocation (OCBA) into PSO to improve the computational efficiency of PSO for stochastic optimization problems. We derive an asymptotically optimal allocation rule to intelligently determine the number of samples for all particles such that the PSO algorithm can efficiently select the personal best and global best when there is stochastic estimation noise in fitness values. We also propose an easy-to-implement sequential procedure. Numerical tests show that our new approach can obtain much better results using the same amount of computational effort.

We formulate the statistical selection problem in a general dynamic framework comprising fully sequential sampling allocation and optimal design selection. Because the traditional probability of correct selection measure is not sufficient to capture both aspects in this more general framework, we introduce the integrated probability of correct selection to better characterize the objective. As a result, the usual selection policy of choosing the design with the largest sample mean as the estimate of the best is no longer necessarily optimal. Rather, the optimal selection policy is to choose the design that maximizes the posterior integrated probability of correct selection, which is a function of the posterior mean and the correlation structure induced by the posterior variance. Because determining the optimal selection policy is generally intractable, we also devise an approximation scheme to efficiently approximate the optimal selection policy. For the allocation policy, we study an asymptotic policy called general Bayesian budget allocation, which is comprised of a sampling statistic and a sequential rule. The optimal computing budget allocation algorithm can be interpreted as a special case of the asymptotical sampling statistics. Numerical examples are provided to illustrate the potential performance improvements, especially in small sample behavior.

The analytic hierarchy process (AHP) has been widely applied to multicriteria decision making problems. The AHP aids decision makers to determine the priorities of multiple criteria, and make reasonable decisions. In the AHP, evaluating candidate alternatives requires multiple experts' evaluations to avoid personal subjectivity. Although having more experts can improve selection quality, inviting more experts also results in higher recruitment cost and longer evaluation time. In this paper, we introduce the idea of optimal computing budget allocation (OCBA) and propose a method, named the AHP_OCBA method, to improve the efficiency of expert allocation. The proposed method optimizes the allocation of experts to maximize the probability of correctly selecting the best alternative in the AHP. This method also can minimize the required number of experts to meet the probability of correct selection. An illustrative example is provided to indicate the implementation of the AHP_OCBA method. We show the improvement of the proposed method compared to proportional and equal allocation rules in the numerical result.

Adaptive population sizing aims at improving the overall progress of an evolution strategy. At each generation, it determines the parental population size that promises the largest fitness gain, based on the information collected during the evolutionary process. In this paper, we develop an adaptive variant of a (μ/μ, λ) evolution strategy. Based on considerations on the sphere, we derive two approaches for adaptive population sizing. We then test these approaches empirically on the sphere model using a normalized mutation strength and cumulative mutation strength adaption. Finally, we compare the methodology on more general functions with a fixed population, covariance matrix adaption evolution strategy (CMA-ES). The results confirm that our adaptive population sizing methods yield better results than even the best fixed population size.

Ranking and selection procedures have been successfully applied to enhance the efficiency of simulation in recent years. To further improve the efficiency, one approach is to incorporate the simulation output from across the domain into some response surfaces. In this paper, the domain of interest is divided into adjacent partitions and a quadratic regression function is assumed for the mean of the underlying function in each partition. Using the large deviation theory, an asymptotically optimal allocation rule is proposed with the objective of maximizing the probability of correctly selecting the best design point. The proposed simulation budget allocation rule is implemented in a heuristic sequential allocation algorithm and compared with some existing allocation rules. Numerical results illustrate the effectiveness of the proposed simulation budget allocation rule.

Simulation-based policy improvement (SBPI) has been widely used to improve given base policies through simulation. The basic idea of SBPI is to estimate all the Q-factors for a given state using simulation, and then select the action that achieves the minimal cost. It is therefore of great importance to efficiently use the given budget in order to select the best action with high probability. Different from existing budget allocation algorithms that estimate Q-factors by independent simulation, we share the sample paths to improve the probability of correctly selecting the best action. Our method can be combined with equal allocation, Successive Rejects, and optimal computing budget allocation to enhance their probabilities of correct selection as well as to achieve better policies in SBPI. Such improvement depends on the overlap in reachable states under different actions. Numerical results show that with such overlap, combining our method with equal allocation, Successive Rejects and optimal computing budget allocation produces higher probability of selection as well as better policies in SBPI.

In this paper, we present an authentication and recovery scheme to protect images. The image blocks are DCT transformed and then encoded with different patterns. An optimal selection is adopted to find the best pattern for each block which results in better image quality. Both the recovery and check data are embedded for data protection. The experimental results demonstrate that our method is able to identify and localize regions having been tampered with. Furthermore, good image quality for both watermarked and recovered images are well preserved.

Partition-based random search (PRS) provides a class of effective algorithms for global optimization. In each iteration of a PRS algorithm, the solution space is partitioned into subsets which are randomly sampled and evaluated. One subset is then determined to be the promising subset for further partitioning. In this paper, we propose the problem of allocating samples to each subset so that the samples are utilized most efficiently. Two types of sample allocation problems are discussed, with objectives of maximizing the probability of correctly selecting the promising subset$(P\{CSPS\})$given a sample budget and minimizing the required sample size to achieve a satisfied level of$P\{CSPS\}$, respectively. An extreme value-based prospectiveness criterion is introduced and an asymptotically optimal solution to the two types of sample allocation problems is developed. The resulting optimal sample allocation strategy (OSAS) is an effective procedure for the existing PRS algorithms by intelligently utilizing the limited computing resources. Numerical tests confirm that OSAS is capable of increasing the$P\{CSPS\}$in each iteration and subsequently improving the performance of PRS algorithms.

A three-phase memetic algorithm (MA) is proposed to find a suboptimal solution for real-time combinatorial stochastic simulation optimization (CSSO) problems with large discrete solution space. In phase 1, a genetic algorithm assisted by an offline global surrogate model is applied to find N good diversified solutions. In phase 2, a probabilistic local search method integrated with an online surrogate model is used to search for the approximate corresponding local optimum of each of the N solutions resulted from phase 1. In phase 3, the optimal computing budget allocation technique is employed to simulate and identify the best solution among the N local optima from phase 2. The proposed MA is applied to an assemble-to-order problem, which is a real-world CSSO problem. Extensive simulations were performed to demonstrate its superior performance, and results showed that the obtained solution is within 1% of the true optimum with a probability of 99%. We also provide a rigorous analysis to evaluate the performance of the proposed MA.

Many automation or manufacturing systems are large, complex, and stochastic. Since closed-form analytical solutions generally do not exist for such systems, simulation is the only faithful way for performance evaluation. From the practical engineering perspective, the designs (or solution candidates) with low complexity (called simple designs) have many advantages compared with complex designs, such as requiring less computing and memory resources, and easier to interpret and to implement. Therefore, they are usually more desirable than complex designs in the real world if they have good enough performance. Recently, Jia (IEEE Trans. Autom. Sci. Eng., vol. 8, no. 4, pp. 720-732, Oct. 2010) discussed the importance of design simplicity and introduced an adaptive simulation-based sampling algorithm to sequentially screen the designs until one simplest good enough design is found. In this paper, we consider a more generalized problem and introduce two algorithms OCBA-mSG and OCBA-bSG to identify a subset of m simplest and good enough designs among a total of K (K >; m) designs. By controlling the simulation allocation intelligently, our approach intends to find those simplest good enough designs using a minimum simulation time. The numerical results show that both OCBA-mSG and OCBA-bSG outperform some other approaches on the test problems.

We consider a class of the subset selection problem in ranking and selection. The objective is to identify the top m out of k designs based on simulated output. Traditional procedures are conservative and inefficient. Using the optimal computing budget allocation framework, we formulate the problem as that of maximizing the probability of correctly selecting all of the top-m designs subject to a constraint on the total number of samples available. For an approximation of this correct selection probability, we derive an asymptotically optimal allocation and propose an easy-to-implement heuristic sequential allocation procedure. Numerical experiments indicate that the resulting allocations are superior to other methods in the literature that we tested, and the relative efficiency increases for larger problems. In addition, preliminary numerical results indicate that the proposed new procedure has the potential to enhance computational efficiency for simulation optimization.

The research works on the mobile ad hoc networks (MANET) have attracted wide attentions over the past few years. In order to evaluate and verify the underlying protocols or applications, researchers run simulations to generate results. By controlling different simulation parameters, we can run our programs in diverse simulation scenarios. Mobility model of mobile nodes in MANET plays an important role in simulations but its importance is often ignored. Random waypoint (RWP) is one of the most deployed mobility models in papers. RWP has the properties that are understandable and quick to implement. Until recently, several defects in RWP is unknown. One is decaying average speed and another is border effect. Besides the problems in RWP, there is still a missing property in many mobility models. Diverse average speed (DAS) is a more realistic requirement for mobility models. Most mobility models only can generate one average speed scenario with the same speed range. It is reasonable to provide different average speed within the same speed range. We propose general ripple mobility model (GRMM) of speed-time pairing to provide a similar mobility model to RWP without the defects of RWP. GRMM also provides DAS to generate different mobility scenarios. The simulation results show that GRMM of speed-time pairing can generate the mobility pattern of uniform spatial distribution and diverse average speed.

We consider the problem of efficiently allocating simulation replications in order to maximize the probability of selecting the best design under the scenario in which system performances are sampled in the presence of correlation. In the case of two designs, we are able to derive the optimal allocation exactly, and find that in the presence of positive correlation, unless the variance of one design is significantly larger than that of the other, the number of simulation replications should be identical. In extending to a general number of competing designs, an approximation for the asymptotically optimal allocation is obtained. The approximation coincides with the independent case derived previously in the limit as the correlation vanishes and also agrees with the two-design exact solution. Furthermore, the allocations prescribed by the results seem to match intuition, in terms of the relationship to correlations and relative variances between designs, again suggesting that equal allocation is optimal for sufficiently high positive correlation. An allocation algorithm based on the approximation is proposed and tested on several numerical examples.

Semiconductor wafer fab operations are characterized by complex and reentrant production processes over many heterogeneous machine groups with stringent performance requirements. Efficient composition of good scheduling policies from combinatorial options of wafer release and machine dispatching rules has posed a significant challenge to competitive fab operations. In this paper, we design a fast simulation-based methodology by an innovative integration of ordinal optimization (OO) and design of experiments (DOEs) to efficiently select a good scheduling policy for fab operations. Instead of finding the exact performance among scheduling policies, our approach compares their relative orders of performance to a specified level of confidence. Our new approach consists of three stages: performance estimation model construction using DOE, policy option screening process, and final simulation evaluation with intelligent computing budget allocation. The exponential convergence of OO is integrated into all the three stages to significantly improve computational efficiency. Simulation results of applications to scheduling wafer fabrications not only screen out good scheduling policies but also provide insights about how factors such as wafer release and the dispatching of each machine group may affect production cycle times and smoothness under a reentrant process flow. Most of the OO-based DOE simulations require 2-3 orders of magnitude less computation time than those of a traditional approach. Such a high speedup enables decision makers to explore much larger problems.Note to Practitioners- This paper designs a fast simulation-based methodology to compose a good scheduling policy from various dispatching rules of fab operations. The methodology innovatively applies DOE to estimate performance of dispatching rule combinations (policies) over various machines groups in a fab, screens out good enough policy options by using OO over the performance estimation, and allocates computation time intelligently to simulate potentially good options. Our study shows that OO-based DOE simulations require 2-3 orders of magnitude less computation time than those of a traditional approach. The high speedup enables fab managers to identify good scheduling policies from the many combinations of wafer release and dispatching rules.

Ordinal optimization offers an efficient approach for simulation optimization by focusing on ranking and selecting a finite set of good alternatives. Because simulation replications only give estimates of the performance of each alternative, there is a potential for incorrect selection. Two measures of selection quality are the alignment probability or the probability of correct selection (P{CS}), and the expected opportunity cost E[OC], of a potentially incorrect selection. Traditional ordinal optimization approaches focus on the former case. This paper extends Chen's optimal computing budget allocation (OCBA) approach, which allocated replications to improve P{CS}, to provide the first OCBA-like procedure that optimizes E[OC] in some sense. The procedure performs efficiently in numerical experiments.

A generic embedded device (GED) that can be installed to various kinds of information equipment, such as manufacturing equipment, portal servers, automatic guided vehicles, etc., is successfully developed In this work. GED is equipped with an embedded real-time operating system and several software modules to retrieve, collect, and manage equipment data. In particular, the communication management module of GED can transmit and receive data to/from remote clients via both wired and wireless networks. Moreover, GED has an object-oriented application interface that flexibly enables GED to add-in or update any customized application. Three typical communication mechanisms, namely the standard processes of exception notification, periodic inspection, and data inquiry are built in GED. As such, GED is able to handle a variety of customized applications, such as monitoring, detection, diagnostics, and prognostics of various kinds of information equipment. We believe that GED possesses the potentiality of information acquisition and transmission so that it can assist all kinds of information equipment to reach the goal of equipment-to-system (E2S) communication and facilitate the maintenance tasks.

In a fab with heterogeneous machine groups, the number of scheduling policies grows in a combinatorial way because each machine group has its specific dispatching rules. In this paper, we design a fast simulation methodology by an innovative combination of the notions of ordinal optimization (OO) and design of experiments (DOE) to efficiently select a good scheduling policy for fab operation, Instead of finding the exact performance among scheduling policies, our approach compares their relative orders of performance to a specified level of confidence. The DOE method is exploited to largely reduce the number of scheduling policies to be evaluated by the OO-based simulation. Simulation results of applications to scheduling wafer fabrications show that most of the OO-based DOE simulations require 2 to 3 orders of magnitude less computation time than those of traditional approach, and the speedup is up to 7,000 times in certain cases.

We exploit the speed of an ordinal optimization (OO)-based simulation tool designed by Hsieh et al. (1999) to investigate dynamic selection of scheduling rules for semiconductor wafer fabrication (FAB). Although a scheduling rule is a combination of loading wafer release and dispatching rules, this paper specifically focuses on dispatching when significant amount of wafers-in-process are held due to engineering causes and when major machine failures occur. Four prominent dispatching rules combined with the wafer release policy of workload regulation constitute a basic set of rule options. The dispatching rule may be weekly selected based on FAB states over a four-week horizon. A total of 756 rule options are then evaluated and ranked by the OO-based simulation tool under the performance index of mean cycle time and throughput rate. Results demonstrate the value of dynamic rule selection for uncertainty handling, the insightful selection of good rules and the needs for further research.

Computational efficiency is one of the major challenges of applying simulation to short-term operation scheduling of semiconductor wafer fabrication factories (fabs), which are characterized by re-entrant process flows, stringent production control requirements and fast changing technology and business environments. The paper explores the application of the ordinal optimization (OO)-based simulation technique to efficiently selecting good rules for scheduling wafer fabrications. An efficient simulation tool, which makes use of OO and optimal computing budget allocation techniques, is developed. Experiments with the OO-based simulation tool are conducted for static selection of good rules under different factors such as initial state, performance index and time horizon. Results indicate that one to two orders of computation time reduction over traditional simulations can be achieved and that what rules are good varies with factors of initial state, performance index and time horizon. These results motivate our further investigation about applications to dynamic selection of dispatching rules upon the occurrence of two significant uncertain events: holding of significant amount of wafers-in-process due to engineering causes and major machine failures. Results demonstrate the value of dynamic rule selection for uncertainty handling, the insightful selection of good rules and the needs for future research.

The performance of heuristic algorithms for combinatorial optimization is often sensitive to problem instances. In extreme cases, a specialized heuristic algorithm may perform exceptionally well on a particular set of instances while fail to produce acceptable solutions on others. Such a problem-sensitive nature is most evident in algorithms for combinatorial optimization problems such as job shop scheduling, vehicle routing, and cluster analysis. The paper proposes a formal method for comparing and selecting heuristic algorithms (or equivalently, different settings of a same algorithm) given a desired confidence level and a particular set of problem instances. We formulate this algorithm comparison problem as a stochastic optimization problem. Two approaches for stochastic optimization, ordinal optimization and optimal computing budget allocation are applied to solve this algorithm selection problem. Computational testing on a set of statistical clustering algorithms in the IMSL library is conducted. The results demonstrate that our method can determine the relative performance of heuristic algorithms with high confidence probability while using a small fraction of computer times that conventional methods require.

Presents a general approach for coordinating the legs of a multi-legged statically stable walking machine on an uneven terrain. The approach yields an optimized motion plan for several "body-lengths" that allows us to select footholds and sequence the legs of the walking machine. We assume that a terrain map is available but that this map may be characterized by uncertainty. We also assume the optimality of the motion plan can be measured by a suitable metric. The method of ordinal optimization is used to find a motion plan that is guaranteed to be in a desired percentile with a given confidence level. Depending on the available computational resources we can improve our confidence level and/or get closer to the optimal plan. Finally, our approach allows us to trade off speed with safety, and speed with optimality.

This paper presents an approach to developing high quality tests for switch-level circuits using both current. and logic test generation algorithms. Clear definitions for analyzing the effectiveness of the joint !,est generation approach are derived. Results on a set of switch-level circuits show very high coverage of stuickat, st,uck-on, and stuck-open faults when both current and logic tests are used.

A powerful automatic test generation system which uses a novel nine-valued relaxation algorithm is presented. This algorithm, which brings together the relaxation technique from circuit simulation and a nine-valued algebra from sequential circuit test generation, is applied to the strongly connected DC coupling components so that for every possible choice of node values a stable state could be achieved through relaxation. Circuits which use bidirectional transistors and depend on the transistor strengths for correct operation are properly handled by this algorithm. A method called DC path sensitization is used to detect the stuck-at, stuck-on, stuck-open and bridging faults for CMOS transistors. The algorithm has been implemented in C++ and preliminary results are very promising. The algorithm can easily be extended to different circuit models and other technologies, or be incorporated into a higher level test generation system.>