consortiums

PROJECT 2

DISTRIBUTION AND ASSIGNMENT

Robert P. Cook
Computer and Information Science
University of Mississippi

Proposed Grant $78,538

Abstract:
The goal of the proposed research is to explore the feasibility of utilizing an open architecture for a discrete-event simulation system, together with optimization strategies such as tabu search [1], to realize an improved solution system for large-scale combinatorial optimization problems of interest to the Navy. The existing close relationship between University of

Mississippi researchers and NPRST will be utilized to provide suitable sample problems in the initial tests. The first phase of the project will involve the implementation of a suitable experimental test-bed. The creation of the test-bed requires the implementation of a prototype discrete-event simulation system; the implementation of a suitable search meta-strategy, and the implementation of several sample problems. The completion of the basis for experimentation in the first phase of the project basically duplicates the current state-of-the-art in the use of discrete-event simulation systems in combination with heuristic search techniques to solve combinatorial optimization problems.

The proposed research includes the design of an experimental “open” architecture for the simulation system that would allow the search algorithm to interact with simulations during their execution. One obvious benefit would be the addition of a “cut” feature that would allow unproductive runs to be terminated early. The goals are to improve the quality of solutions and the speed with which they could be produced. Note that we are not proposing to rewrite existing simulations, only to “open” the architecture of the simulation system so that the search strategy can interact with intermediate simulation states. An alternative optimization strategy might be to recognize useful intermediate states and to “hot start” other runs at that point to explore alternative paths.