Computational issues for accessibility in discrete event simulation

Enver Yucesan, Sheldon H. Jacobson

Research output: Contribution to journalArticlepeer-review


Several simulation model building and analysis issues 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, noninterchangeability 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. This article considers the problem of accessibility, identifies special cases that are polynomially solvable or remain NP-hard, and discusses implications with respect to the other three problems. A local search procedure and variations of simulated annealing are presented to address accessibility. Computational results illustrate these heuristics and demonstrate their strengths and limitations.

Original languageEnglish (US)
Pages (from-to)53-75
Number of pages23
JournalACM Transactions on Modeling and Computer Simulation
Issue number1
StatePublished - Jan 1996
Externally publishedYes

ASJC Scopus subject areas

  • Modeling and Simulation
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Computational issues for accessibility in discrete event simulation'. Together they form a unique fingerprint.

Cite this