Resource title

Intractable structural issues in discrete event simulation: special cases and heuristic approaches

Resource image

image for OpenScout resource :: Intractable structural issues in discrete event simulation: special cases and heuristic approaches

Resource description

Several simulation model building and analysis have been studied using a computational complexity approach. More specifically, four problems related to simulation model building and analysis (accessibility of states, ordering of events, interchangeability of model implementations, and execution stalling) have been shown to be NP-hard search problems. These results imply that it is unlikely that a polynomial-time algorithm can be devised to verify structural properties of discrete event simulation models, unless P = NP. Heuristic procedures should therefore be useful to practitioners. This paper identifies limited special cases of one of these problems which are polynomially solvable and NP-hard, and discusses the implications with respect to the other three problems. A number of heuristic procedures are then proposed. In particular, four algorithms are presented to address ACCESSIBILITY

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

application/pdf

Resource resource URL

http://flora.insead.edu/fichiersti_wp/Inseadwp1994/94-38.pdf

Resource license

Copyright INSEAD. All rights reserved