工期确定及可变工期下的受限资源多项目调度建模  

Resource constrained multi-project scheduling modeling under certainty and uncertainty duration

作　　者：胡文斌[1] 乐宇[1] 许龙[1] 王凯凯[1] 夏畅[1] 杜博[1] 宋伟[1] 

机构地区：[1]武汉大学计算机学院,湖北武汉430072

出　　处：《计算机集成制造系统》2012年第11期2398-2408,共11页Computer Integrated Manufacturing Systems

基　　金：国家自然科学基金资助项目(70901060);湖北省自然科学基金资助项目(2011CDB461);软件工程国家重点实验室开放基金资助项目(SKLSE2010-08-15);武汉市青年晨光计划资助项目(201150431101);武汉市科技攻关计划资助项目(201160923297)~~

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

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

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]