Normal view MARC view

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
Tags: No tags from this library for this title. Add tag(s)
Log in to add tags.
Item type Current location Collection Call number Status Date due
INSEAD Working Paper Digital Library
PDF Available

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.

Log in to your account to post a comment.
Koha 3.18 - INSEAD Library Catalogue
Library Home | Contact Us | What's Koha?