A List of Responders
Virtual Manufacturing Background Project
E-mail: jacobson@tioli.ise.vt.edu
TITLE: Analyzing Discrete Event Simulation Models of Complex
Manufacturing Systems: a Computational Complexity Approach
PRINCIPAL INVESTIGATOR: Sheldon H. Jacobson
Department of Industrial and Systems Engineering
302 Whittemore Hall, Mail Stop 0118
Virginia Tech
Blacksburg, VA 24061-0118
jacobson@vt.edu
SUPPORT: Air Force Office of Scientific Research (F49620-95-1-0124)
National Science Foundation (DMI-9409266)
ABSTRACT: Discrete-event computer simulation is a powerful modeling tool
for analyzing complex systems that cannot be studied analytically. The
value of simulation depends on how effectively and efficiently one can
build and utilize the simulation model to gain insights into complex,
real-world systems.
The goal of this project is to introduce a new set of tools for building
and analyzing simulation models of complex systems, with a particular
emphasis on manufacturing processes for turbine engine parts, under
development at Wright Laboratory (Materials Process Design Branch).
The basic research question to be considered is: Given a complex
manufacturing system, where the different processes and operations can
be modeled using discrete event simulation model events, is it possible
to determine the sequence of processes and operations, hence events,
that results in finished products with prespecified attributes and
output measures? The attributes and measures of such manufacturing
processes typically involve physical and operational properties of the
finished products, as well as metrics for affordability, predictability,
and repeatability of the outputs.
Research questions of this type are often addressed using adhoc procedures
and problem-specific approaches. This project uses the theory of
computational complexity to provide a framework to study these research
questions, as well as construct new heuristic algorithms to address them.
These heuristics involve simulated annealing, genetic algorithms, and tabu
search. These three heuristics will be cross-fertilized, resulting in
hybrid approaches, as well as enhanced to exploit any special structure
offered by the manufacturing problems.
REFERENCES (as of 3/15/95):
Jacobson, S.H., and Yucesan, E., 1995, "Intractability Results in
Discrete-Event Simulation", To Appear in Recherche Operationelle.
Jacobson, S.H., and Yucesan, E., 1995, "On the Intractability of Verifying
Structural Properties of Discrete Event Simulation Models",
Technical Report, Virginia Tech.
A List of Responders
Virtual Manufacturing Background Project
Virtual Manufacturing Home Page