论文部分内容阅读
在典型的资源分配系统中,生产流程互相等待彼此占有的资源会导致系统死锁,进而造成生产的停滞和系统开销上升,使系统性能严重恶化。Petri网是资源分配系统的主要建模工具之一。其中,S4PR网是一类具有良好的建模能力的Petri网子类,基于S4PR网的死锁控制理论是近年来研究的热点。通过控制虹吸使S4PR网保持活性的死锁预防方法是S4PR网的主要死锁控制策略之一。由于这类方法基于较为严格的虹吸受控条件来设计控制器,导致最终的受控系统行为允许度不高,在实际上表现为资源利用率低下。因此S4PR网的虹吸受控理论还有待完善。基于这一点,本文研究了S4PR网的虹吸受控条件及其应用,完成的工作主要分成以下两部分：(1)首先研究了S4PR网的虹吸受控问题。在现有虹吸受控条件的基础上,提出了两类改进的具有更高允许度的虹吸受控条件—maxⅢ和maxⅣ-受控条件,并证明了当一个S4PR网的所有虹吸都满足maxⅢ或maxⅣ-受控时,它能够保持活性。与之前的受控条件相比,这两类控制条件有效拓宽了虹吸受控的限制。(2)在maxⅢ和maxⅣ-受控条件的基础上,进一步扩展了研究内容,提出了两种新型的基于MIP的S4PR网虹吸寻找算法。对输入的S4PR网搜索状态空间,针对特定的状态通过求解MIP问题,来获取该状态下非maxⅢ-标识或maxⅣ-标识的一个虹吸。应用实例结果证明,这两类算法的计算效率相比现有算法有较大地提升,并且能剔除一部分并不需要添加控制器的虹吸,从而减少控制冗余,提高受控系统允许度。本文提出了两类比现有条件更加宽泛的S4PR网虹吸受控条件,并且证明了当一个S4PR网的所有虹吸都满足这两类条件时能够保持活性。在此基础上,研究了这两类受控条件在虹吸寻找算法中的应用,提出了两种优化的虹吸寻找算法,并运用实例说明了其可行性与有效性。