Intractability results in discrete-event simulation

Abstract

Simulation is often viewed as a modeling methodology of last resort. This is due to the lack of automated algorithms and procedures that exist to aid in the construction and analysis of simulation models. Jacobson and Yucesan (1994) present four structural issue search problems associated with simulation model building, and prove them to be NP-hard, hence intractable under the worst-case analysis of computational complexity theory. In this article, three new structural issue search problems are presented and proven to be NP-hard. The consequences and implications of these results are discussed.