حل مسایل بهینه سازی شبیه سازی در سیستم های کامپیوتری شبکه

The optimal assignment of berth slots and cranes to shipping services is the central logistics problem at modern marine container terminals and should be formulated to specifically account for its stochastic nature. We use a computational grid to solve a major seaport logistic problem by a simulation optimization approach centred around a queuing network model of the logistic process of interest. We emphasize the power of grid computing for the simulation optimization studies and we design and implement an algorithm for distributing the computational load to parallel processors. Performance of the algorithm is demonstrated numerically using real-sized problem instances.

The problem of optimizing a cost/performance function over a finite or countably infinite set of alternative system configurations, whenever the (objective) function cannot be evaluated exactly, but has to be estimated via stochastic simulation, is the subject of the research area called “simulation optimization”, exhaustively presented by Andradóttir [1]. Several, challenging, real applications that ask for practical solution to large, interrelated, decision problems may be found in the planning and control of logistic systems [6]. More recent presentations of simulation optimization techniques may be found in a stimulating survey paper by Fu [5] and, restricting our focus to discrete decision variables, on the special March 2003 issue of ACM TOMACS. In the relevant Guest Editorial Note, Fu and Nelson say: “Simulation optimization means searching for the settings of controllable decision variables that yield the maximum or minimum expected performance of a stochastic system that is represented by a simulation model. Perhaps the most natural approach is to try to import ideas from deterministic optimization into the stochastic setting by taking into account the uncertainty from estimation”. Following this guideline, Ghiani et al. [7] provide for a critical review that covers parallel computing strategies and commercial software oriented to complex decision problems in logistics. The topic of simulation optimization has also appeared in the latest editions of the most popular simulation textbooks [2] and [11]. In the latter one, the authors focus around the analysis of a discrete event simulation model “to find a combination of the input factors that optimizes a key output performance measure” under the assumption that “the alternative system configurations are not just given, but we have to decide what alternative system configurations to simulate as well as how to evaluate and compare their results”. They briefly call this problem “optimum seeking”, but here we would like to refer to it as “optimum seeking via stochastic simulation”. In particular, due to the need of estimating the value of the objective function by simulation experiments, the related combinatorial optimization problem cannot be solved by any available IP solvers (e.g. CPLEX). Rather, a meta-heuristic based algorithm can be designed to provide a guidance procedure aimed to explore in some intelligent and computationally effective way the feasible region. Starting from Pichitlamken and Nelson [14], the optimum seeking framework adopted in our work consists of: • a grid computing system, • a global guidance system to drive our seeking within the feasible region (where one point corresponds to one configuration), • a method to analyze the output of the stochastic simulation (of any given configuration), • a “selection of the best” procedure (for comparisons), • a local improvement strategy (finer analysis of some parameters of a configuration). The main novelty of this paper is the use of grid computing for solving (iterative) simulation optimization problems. The global guidance system of the search method is asked to reach and select a near-optimum solution in a relatively short time; it may have a significant improvement with computing resources that work in parallel as much as possible, by exploring larger subsets of feasible configurations of the model. The policy designed to arrange the exploration is a crucial part of the whole algorithm to be designed for the optimum seeking problem at hand. Moreover, at an inner level, a specific subset of computing resources may have their own capability of: • parallel execution of stochastic simulation; • parallel replication of stochastic simulation to get an adequate level of statistical confidence on the performance indices of the assigned configurations, during the (outer) optimization process. Whenever it is possible to work with a “small list” of feasible, alternative, configurations, then ranking and selection (R&S) and multiple comparison are appropriate procedures for selecting the best (see [20] for a recent survey). Vice versa, if the objective function is defined over a large finite or countable infinite set of alternatives, some global search strategies (e.g., simulated annealing, tabu search and genetic algorithms) can be adopted. In a previous paper [8] a R&S procedure has been incorporated into a simulated annealing framework and the resulting algorithm has been applied for solving a particular production logistics problem. In this work, taking as reference a general seaport logistic problem, we re-design such combined procedure for a grid computing system and carry out an extensive, numerical analysis of its performance. The paper is organised as follows. In Section 2, we present the simulation optimization model. We propose a grid-enabled algorithm in Section 3 and we discuss statistical issues of simulation in Section 4. In Section 5, we illustrate the specific grid framework used and discuss computational results. Finally, we give conclusions in Section 6.

We have designed and implemented on a grid platform a simulation optimization algorithm that requires a limited amount of communication and a minimal synchronization among computing resources. It could be used for a cost-effective solution of logistics decision problems at seaport container terminals. Numerical evidence shows that as the number of workers increases, the quality of the final solution improves. A crucial role is played by the optimal compromise between searching the entire feasible region (exploration) and locally searching promising sub-regions (exploitation). An interesting new random search approach to be pursued under a grid framework should be the balanced explorative and exploitative search[15], due to its “adaptive features” and the possibility of managing the available workers to maintain the right balance between exploration and exploitation during the various stages of the optimization via simulation process. Experimentation of these new valuable ideas is the subject of our ongoing research, where, by adopting the nested partition approach – originally introduced by Shi and Ólafsson [18] and successively refined by Pichitlamken and Nelson [14] – we try to identify a sequence of most-promising sub-regions where to concentrate the computational effort by sub-sets of workers.