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

本研究的目的是引入一套新的工具来建立和分析复杂系统的仿真模型。考虑的问题包括模型验证和确认、停止条件、方差减少技术、敏感性分析和实验设计。计算复杂性理论为分类和研究这些问题提供了一个统一的框架。我们还将开发一种新的启发式算法来解决这些问题。确定了仿真建模和分析的六个基本决策问题，并可以证明它们是非确定性多项式完备的。研究了决策问题在多项式时间内可解的特殊情况。针对这些问题，基于树搜索、动态规划和模拟退火的新启发式算法得到了发展。在本研究中开发的启发式有可能提供定量的、自动化的方法来解决离散事件模拟中的基本决策要素。当与仿真语言相关联时，开发的工具可以帮助从业者构建更精确、质量更好的模型，并以更高的保证和信心执行分析。这项研究的结果有可能推进可以使用离散事件模拟建模和分析的系统领域。

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.