书书书
收稿日期:20120510;修回日期:20120702 基金项目:国家教育部人文社会科学规划基金资助项目(10YJA630187);高等学校博士
点基金资助项目(20093120110008);上海市重点学科建设资助项目(S30504);上海市教育委员会科研创新资助项目(12ZS133);上海市研究生创新
基金资助项目(JWCXSL1102)
作者简介:陈君兰(1988),女,上海人,硕士,主要研究方向为项目管理(tracychen0602@163.com);叶春明(1964),男,安徽宣城人,副院长,
教授,博士,主要研究方向为工业工程、企业战略、企业生产计划与控制、生产调度、企业资源计划(ERP)、供应链管理及企业信息化.
柔性资源受限多项目调度的混沌粒子群算法研究
陈君兰,叶春明
(上海理工大学,上海 200093)
摘 要:为解决柔性资源受限多项目的调度问题,有效实行资源分配和工作时间安排,采用混沌粒子群算法结
合混合优先规则,形成优先规则序列。针对多项目问题,避免了传统方法将多个项目合并为一个项目,而是形成
一个链表在项目的各工序间进行选择调度,并在初始化中嵌入混沌理论,在迭代过程中使用并行算法,有效避免
了算法易陷入局部最优解的可能。改编标准库的多模式算例,对比多种算法下的结果,验证了该方法在求解该
问题的可行性和有效性,对于项目管理中柔性资源受限问题具有实际应用价值。
关键词:柔性资源;粒子群;多项目调度;混沌
中图分类号:TP391;TP3016 文献标志码:A 文章编号:10013695(2013)01011704
doi:10.3969/j.issn.10013695.2013.01.028
Chaosparticleswarmoptimizationonflexibleresource
constrainedmultiprojectschedulingresearch
CHENJunlan,YEChunming
(UniversityofShanghaiforScience&Technology,Shanghai200093,China)
Abstract:Inordertosolvetheflexibleresourceconstrainedmultiprojectschedulingproblem andeffectivelysolvethere
sourcedistributionandstarttimeoftasks,thispaperusedCPSO(chaosparticleswarmoptimization)tosolvethisproblem,
combinedwithmultiwork’sprioritiesways.Andformultiprojectschedulingproblem,usingthewaytoformachainofall
tasksinallprojectsandthenchosefromtoptobottomtoseparatelyscheduleinsteadoftakingmultiprojectintoabigproject.
ItusedchaostoinitiatetheregionalgroupandduringtheprocessusedbothPSOandchaostoupdatedthegroup,andleftthe
bestresultandit’sprovedbetterwaytosolvetheproblemfromescapingthegroupbestresult.Finally,psplibdatabaseofthis
problemwasmodifiedunderthisproblem.Comparingwithothertwoalgorithms,itprovesthepossibilityandeffectofthismeth
odinsolvingthisproblem.Therefore,thismethodhasitspracticalapplicationvaluefortheflexibleresourceconstrainedpro
jectschedulingproblem.
Keywords:flexibleresource;particleswarmoptimization;multiprojectscheduling;chaos
!
引言
柔性资源受限的项目调度问题是资源受限项目调度问题
中的一种。柔性资源受限的项目调度问题可描述为:存在具有
不同技能的有限资源,这些资源被称为柔性资源,而完成一项
工序则需要不同的技能,为了在资源不冲突的情况下,合理安
排各个工序,使整个项目的最终完成时间最短。对于柔性资源
受限问题的研究源于柔性资源受限的车间调度问题,后运用在
项目调度研究上,而目前使用较多的方法是建立一个简单的
01资源技能矩阵。例如喻小光等人
[1]
通过建立两级映射模
型表达任务—能力—资源的关系求解了资源均衡情况下的项
目调度问 题;黄 敏 镁 等 人
[2]
通 过 建 立 任 务—技 能 矩 阵 和 资
源—技能矩阵,使用改进的遗传算法,采用拓扑排序和最大流
理论对产品开发项目实例进行了研究。
多项目问题指同时对多个项目进行调度。由于在项目调
度问题中,经常会出现多个项目共用相同资源,并几乎同时进
行的情况发生,使得任务之间的资源冲突加剧,所以在解决多
项目问题时,通常将多个项目合并为一个项目考虑,但是当项
目数较多时,就会使计算繁琐,运算效率低下。因而很多学者
开始研究新的方法以解决多项目问题。例如应瑛等人
[3]
建立
了拍卖模型,通过让工序在每个调度阶段对资源竞价来确定资
源的优先分配和工序的优先调度;徐赐军等人
[4]
根据资源维
拉技术消解资源冲突,并在此基础上根据最小冲突强度和最小
延迟构建动态优先规则。
柔性资源的多项目调度问题已逐渐受到关注,罗荣桂等
人
[5]
对国内外柔性资源及多项目调度问题进行了研究,分析
了拓展资源受限的多项目问题到柔性资源,并对该方向研究和
发展作出了展望。将柔性资源受限与多项目调度相结合正是
本文的研究重点,这类问题更符合目前项目调度问题,尤其是
产品开发项目中的实际情况,具有更好的实际意义。
本文在解决多项目问题时,单独考虑多个项目,通过建立
一个项目选择的数组,从而解决多项目调度的问题。在此基础
第 30卷第 1期
2013年 1月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol30No1
Jan.2013