《计算机应用研究》|Application Research of Computers

求解广义优先关系下多技能人员项目调度问题的改进布谷鸟搜索算法

Improved cuckoo search algorithm for multi-skilled resource constrained project scheduling problems with generalized precedence relations

免费全文下载 (已被下载 次)  
获取PDF全文
作者 段鹏飞,余杰,聂慧,杨辉华
机构 1.桂林电子科技大学 a.电子工程与自动化学院;b.信息与通信工程学院,广西 桂林 541004;2.北京邮电大学 自动化学院,北京 100876
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2018)05-1315-05
DOI 10.3969/j.issn.1001-3695.2018.05.008
摘要 为解决传统的完成—开始时序不能满足描述真实项目调度顺序要求的问题,引入广义优先关系(GPRs)及改进的AON描述任务的时序约束。提出将布谷鸟搜索算法应用于求解广义优先关系下的多技能人力资源项目调度问题(MS-RCPSP/GPRs)中的构想,建立了基于改进布谷鸟搜索算法(ICS)的求解方法,采用Powell局部改进技术和精英保留策略,并给出了算法流程。基于相关案例生成器生成该问题的数据集,实验结果表明ICS是一种求解MS-RCPSP/GPRs的有效方法,对解决实际问题具有重要意义。
关键词 广义优先关系;多技能人力资源调度问题;布谷鸟搜索算法;Powell局部搜索;回溯操作
基金项目 国家自然科学基金资助项目(21365008,61562013)
广西重点研发计划资助项目(桂科AB16380293)
本文URL http://www.arocmag.com/article/01-2018-05-008.html
英文标题 Improved cuckoo search algorithm for multi-skilled resource constrained project scheduling problems with generalized precedence relations
作者英文名 Duan Pengfei, Yu Jie, Nie Hui, Yang Huihua
机构英文名 1.a.CollegeofElectronicEngineering&Automation,b.SchoolofInformation&CommunicationEngineering,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China;2.SchoolofAutomation,BeijingUniversityofPosts&Telecommunications,Beijing100876,China
英文摘要 Aiming at the problem that the traditional finish-start precedence relation couldn’t satisfy the requirement of describing the real project scheduling precedence relations, this paper introduced the generalized precedence relations (GPRs) and the improved AON to describe task timing constraints. It applied cuckoo search algorithm to solve the multi-skilled resource constrained project scheduling problem with generalized precedence relations (MS-RCPSP/GPRs), designed and introduced an methodology based on the improved cuckoo search(ICS) algorithm to optimize those problems, used Powell technology and improved local elite retention strategy, and gave the algorithm process. The relevant case generator generated the data set of the problem. The experimental results show that ICS is an effective method to solve MS-RCPSP/GPRs, which is of great significance to solve practical problems.
英文关键词 generalized precedence relations; multi-skilled RCPSP; cuckoo search algorithm; Powell local search; backtracking
参考文献 查看稿件参考文献
  [1] Bartusch M, Mhring R H, Radermacher F J. Scheduling project networks with resource constraints and time windows[J] . Annals of Ope-rational Research, 1988, 16(1):201-240.
[2] Dhib C, Kooli A, SoukhaL A, et al. Lower bounds for the multi-skill project scheduling problem[C] //Proc of the 8th International Workshop on Project Management and Scheduling. Berlin:Springer, 2012:471-476.
[3] Montoya C, Bellenguez-Morineau O, Pinson E, et al. Branch-and-price approach for the multi-skill project scheduling problem[J] . Optimization Letters, 2014, 8(5):1721-1734.
[4] Myszkowski P B, Skowronski M E, et al. Hybrid ant colony optimization in solving multi-skill resource-constrained project scheduling problem[J] . Soft Computing, 2015, 19(12):3599-3619.
[5] 郭研, 李南, 李兴森. 基于云多目标微粒群算法的多项目调度方法研究[J] . 计算机工程与应用, 2012, 48(21):15-20.
[6] Liao Guangrui, Liu Zhenyuan, Bi Yang. Project scheduling with time window constraints on multi-skill resources[C] //Proc of the 26th Chinese Control and Decision Conference. [S. l. ] :IEEE Press, 2014:4885-4891.
[7] 王一帆, 刘士新, 陈迪. 求解多技能人力资源约束的项目调度问题的两阶段算法[J] . 东北大学学报:自然科学版, 2014, 35(2):184-189.
[8] Wang Yifan, Chen Di, Liu Shixin, et al. An instance generator for project scheduling problems with multi-skilled personnel constraints[C] //Proc of the 24th Chinese Control and Decision Conference. [S. l. ] :IEEE Press, 2012:3430-3435.
[9] Yang Xinshe, Deb S. Cuckoo search via Lévy flights[C] //Proc of World Congress on Nature & Biologically Inspired Computing. Piscata-way, NJ:IEEE Press, 2009:210-214.
[10] Ballestín F, Barrios A, Valls V. An evolutionary algorithm for the resource-constrained project scheduling problem with minimum and maximum time lags[J] . Journal of Scheduling, 2011, 14(4):391-406.
[11] Li Haitao, Womer K. Scheduling projects with multi-skilled personnel by a hybrid MILP/CP benders decomposition algorithm[J] . Journal of Scheduling, 2009, 12(3):281-298.
收稿日期 2016/12/28
修回日期 2017/3/1
页码 1315-1319
中图分类号 TP301.6
文献标志码 A