Intractable structural issues in discrete event simulation: special cases and heuristic approaches
Author: Yücesan, Enver ; Jacobson, S. H.INSEAD Area: Technology and Operations Management Series: Working Paper ; 94/38/TM Publisher: Fontainebleau : INSEAD, 1994.Language: EnglishDescription: 33 p.Type of document: INSEAD Working Paper Online Access: Click here Abstract: 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| Item type | Current location | Collection | Call number | Status | Date due | Barcode | Item holds |
|---|---|---|---|---|---|---|---|
|
Digital Library | Available | BC001028 |
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
Digitized
There are no comments for this item.