Research Initiation: Building and Analyzing Discrete Event Simulation Models of Complex Systems -- A Computational Complexity Approach

研究启动：复杂系统离散事件仿真模型的构建和分析——计算复杂性方法

• 批准号: 9409266
• 负责人: Sheldon Jacobson
• 金额: $ 9万
• 依托单位: Virginia Polytechnic Institute and State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-09-15 至 1998-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9409266&HistoricalAwards=false
• 关键词: Research; Initiation; Building; Analyzing; Discrete

9409266 Jacobson The objective of this research is to introduce a new set of tools for building and analyzing simulation models of complex systems. Issues considered include model verification and validation, stopping conditions, variance reduction techniques, sensitivity analysis, and experimental design. The theory of computational complexity is used to provide a unified framework to classify and study the issues. A new heuristic algorithm will also be developed to address these issues. Six decision problems fundamental to simulation modeling and analysis are identified and may be proven to be non-deterministic polynomial complete. Special cases of the decision problems that are solvable in polynomial time are studied. New heuristics for these problems are developed based on tree search, dynamic programming, and simulated annealing. The heuristics developed in this research have the potential to provide quantitative, automated approaches to address fundamental decision elements in discrete event simulation. The developed tools when attached to simulation languages can help practitioners build more precise, better quality models, and perform analysis with a higher degree of assurance and confidence. The outcome of this research has the potential to advance the domain of systems that can be modeled and analyzed using discrete event simulation.

9409266雅各布森这项研究的目的是介绍一套新的工具，用于建立和分析复杂系统的仿真模型。所考虑的问题包括模型验证和确认、停止条件、方差减少技术、灵敏度分析和实验设计。计算复杂性理论被用来提供一个统一的框架来分类和研究这些问题。还将开发一种新的启发式算法来解决这些问题。识别了六个模拟、建模和分析的基本决策问题，并且可以证明它们是非确定多项式完备的。研究了在多项式时间内可解的决策问题的特例。提出了一种基于树搜索、动态规划和模拟退火法的启发式算法。这项研究中开发的启发式方法有可能提供定量的、自动化的方法来处理离散事件模拟中的基本决策元素。开发的工具附加到模拟语言后，可以帮助实践者建立更精确、更高质量的模型，并以更高的把握和信心执行分析。这项研究的结果有可能推进可以用离散事件仿真建模和分析的系统领域。