求解任务可拆分多项目协同调度问题的启发式算法  

Heuristic algorithm for solving multi-project collaborative scheduling problem with activity splitting

作　　者：王磊[1] 聂兰顺[2] 战德臣[2] 王弼陡[1] 罗刚银[1] WANG Lei NIE Lan-shun ZHAN De-chen WANG Bi-dou LUO Gang-yin(Suzhou Institute of Biomedical Engineering and Technology, Chinese Academy of Sciences, Suzhou 215163, China School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)

机构地区：[1]中国科学院苏州生物医学工程技术研究所,江苏苏州215163 [2]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《控制与决策》2017年第6期1013-1018,共6页Control and Decision

基　　金：国家自然科学基金项目(61273038);江苏省政策引导类计划(产学研合作)-–前瞻性联合研究项目(BY2016049-01)

摘　　要：生产项目计划与调度过程中任务可以被拆分为更小粒度的子任务分批次执行,实现缩短项目总工期的优化目标.针对抢占式任务可拆分多项目调度问题,从协同优化角度探讨任务拆分与重组方式,提出一个长工期任务优先拆分、长工期项目优先拆分和高资源利用率项目优先拆分3种任务拆分优先级判断规则,设计一种求解任务可拆分多项目协同调度问题的启发式算法.最后通过数值实例和仿真分析验证了所提出方法在多项目调度总工期的优化效果和求解效率.The activity in project can be split into multiple sub-activities in batches of smaller granularity execution in the real production project planning and scheduling environment to shorten the total projects makespan. For the preemptive multi-project scheduling problem with activity splitting, the patterns of activity splitting and recombination are discussed from the perspective of collaborative optimization, three heuristic rules for the activity splitting judgment are proposed, such as long activity duration（LAD）, long project makespan（LPM） and high resource rate（HRR）, and a heuristic algorithm for solving multi-project collaborative scheduling problem with activity splitting is designed. Simulation results show that the method can shortn the total makespan of the multi-project scheduling problem by activity splitting.

关 键 词：多项目调度 协同优化 任务可拆分 抢占式 启发式规则 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]