Abstract: Uncertain project duration method couldn't describe state changes in sequence accurately and explicitly, there was only approximate solution. In order to deal with this problem, a modeling method by extending Petri net was proposed. Scheduling problems in resource-constrained projects with definite duration and changeable duration were modeled. This method classified tokens into logic token and resource token, and token's transformation represented the task execution as well as resource allocation respectively. Through classifying place, transitions and timed place, the places were divided into activity place, resource place, waiting place, and final place, and transitions were divided into coordination transition, resource scheduling transition and resource releasing transition. Through coordination transition, the timing relationship among tasks were reflected in waiting place and activity place; through resource place, resource scheduling transition and resource releasing transition, the competition, occupation and release of tasks for resources were reflected. By adding places and transition types and modifying transition firing rules, the actual system of uncertain duration was described. Through examples in PSPLIB library, the model solution success rate, model solution fitness and comparative test for extended Petri net were analyzed. The effectiveness of proposed model was verified by an actual engineering application.

Key words: resource constrained, multi-project scheduling, Petri nets, simulation

摘要： 针对不确定性工期问题的研究方法无法正确和清晰地描述工序状态变化、只能近似求解的现象，提出一种扩展Petri网建模方法，对工期确定和可变工期受限资源多项目调度问题进行建模。该方法将托肯分为逻辑托肯与资源托肯，托肯的转移分别表示任务的执行和资源的分配。通过对库所和变迁的分类以及对库所的赋时，将库所分为活动库所、资源库所、等待库所和终极库所，将变迁分为协调变迁、资源调度变迁和资源释放变迁。等待库所和活动库所通过协调变迁连接反映任务之间的时序关系，通过资源库所、资源调度变迁与资源释放变迁，反映任务之间对资源的竞争、占用和释放。对于可变工期问题，通过增加库所和变迁种类以及修改变迁触发规则来描述实际系统。采用PSPLIB library中的实例对提出的建模方法进行模型求解成功率分析、模型求解适应度能力分析和对比性实验分析表明，所提方法比其他方法具有更好的求解能力和表现，并通过一个实际工程应用求解验证了建模方法的有效性。

关键词: 受限资源, 多项目调度, Petri网, 仿真