Ordinal optimisation and simulation
- PDF / 308,015 Bytes
- 11 Pages / 595 x 842 pts (A4) Page_size
- 6 Downloads / 216 Views
#2000 Operational Research Society Ltd. All rights reserved. 0160-5682/00 $15.00 www.stockton-press.co.uk/jors
Ordinal optimisation and simulation Y-C Ho1, CG Cassandras2, C-H Chen*3 and L Dai4 1
Harvard University, Cambridge; 2Boston University, Boston; 3University of Pennsylvania, Philadelphia and 4Washington University, St. Louis, USA
Simulation plays a vital role in designing and analysing stochastic systems, particularly, in comparing alternative system designs with a view to optimise system performance. Using simulation to analyse complex systems, however, can be both prohibitively expensive and time consuming. Ef®ciency is a key concern for the application of simulation to optimisation problems. Ordinal optimisation has emerged as an effective approach to signi®cantly improve ef®ciency of simulation and optimisation. Ordinal optimisation for simulation problems achieves an exponential convergence rate. There are already several success stories of ordinal optimisation. This paper introduces the idea of ordinal optimisation, and reports some recent advances in this research. It also gives details of an extension of ordinal optimisation to a class of resource application problems. Keywords: discrete-event simulation; ordinal optimisation; discrete-event dynamic systems; resource allocation problem
Introduction It can be argued that optimisation in the general sense of making things better is the principal driving force behind any prescriptive scienti®c and engineering endeavor, be it operations research, control theory, or engineering design. It is also true that the real world is full of complex decision and optimisation problems that we cannot yet solve. While the literature on optimisation and decision making is huge, much of the concrete analytical results and success stories are associated with what may be called real-variable-based methods. The idea of successive approximation to an optimum (say, minimum) by sequential improvements based on local information, is often captured by the metaphor `skiing downhill in a fog'. The concepts of gradient (slope), curvature (valley), and trajectories of steepest descent (fall line) all require the notion of derivatives=gradients and are based on the existence of a more or less smooth response surface. There exist various ®rst and second order algorithms of feasible directions for the iterative determination of the optimum of an arbitrary multi-dimensional response or performance surface. A considerable number of major success stories exist in this genre including the Nobel prizewinning work on linear programming. It is not necessary to repeat or even reference these here. On the other hand, we submit that the reason many realworld optimisation problems remain unsolved is partly due to the changing nature of the problem domain in recent years, which makes calculus or real-variable-based method less applicable. For example, a large number of human*Correspondence: Prof C-H Chen, Dept. of Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104-6315, U
Data Loading...
