Please wait a minute...
浙江大学学报(工学版)
自动化技术     
考虑技能水平的多技能资源约束项目调度
任逸飞, 陆志强, 刘欣仪, 张猛
同济大学 机械与能源工程学院,上海 201804
Project scheduling problem with hierarchical levels of skills
REN Yi-fei, LU Zhi-qiang, LIU Xin-yi, ZHANG Meng
School of Mechanical Engineering, Tongji University, Shanghai 201804, China
 全文: PDF(992 KB)   HTML
摘要:

针对带有技能水平的一般多技能资源约束项目调度问题进行扩展,将技能水平进行分级并将技能和资源各分为关键和辅助2类,考虑作业执行时间因分配的关键资源具备的技能水平而变.以最小化项目总工期为目标,建立相应的数学优化模型,提出包含双层决策及局部优化策略的混合算法.其中,上层的遗传算法用于决策表示作业执行顺序的优先级列表,下层的关键资源决策启发式算法用以确定作业实际执行时间并对上层列表进行解码得到问题的可行解.在所得可行解的基础上,采用基于关键链的局域搜索算法,调整资源分配以缩短关键链长度,保证算法的求解质量.数据实验表明,所提算法在求解质量和求解速度方面均具有良好性能.

Abstract: Extended the multi-skill resource constrained project scheduling problem with hierarchical levels of skills, classified the skills into several levels and categorized the resources as key resources and assistant resources. The duration of the activity changes according to the level of the key resource used. The objective of the mathematical optimization model is to minimize the makespan of the project. A hybrid algorithm consists of a two-level decision scheme and a local search optimization scheme was developed. A genetic algorithm was proposed to decide the activity priority list at the upper level and a key resource decision heuristic algorithm was introduced at the lower level, to generate a feasible solution and decide the start time of the activity. Subsequently, a critical chain based local search optimization algorithm was designed to adjust the allocation of the resources, shorten the length of the critical chain and improve the quality of the result. Computational results show that the proposed algorithm can solve the problem effectively.
出版日期: 2017-05-01
CLC:  TP 29  
基金资助:

国家自然科学基金资助项目(61473211,71171130).

通讯作者: 陆志强,男,教授. ORCID:0000-0002-9357-610X.     E-mail: zhiqianglu@tongji.edu.cn
作者简介: 任逸飞(1994—),男,博士生,从事多技能资源投入项目调度等研究. ORCID:0000-0001-9546-506X. E-mail:ryf3212698@163.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
作者相关文章  

引用本文:

任逸飞, 陆志强, 刘欣仪, 张猛. 考虑技能水平的多技能资源约束项目调度[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2017.05.021.

REN Yi-fei, LU Zhi-qiang, LIU Xin-yi, ZHANG Meng. Project scheduling problem with hierarchical levels of skills. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2017.05.021.

参考文献(References):
[1] BELLENGUEZ O, NETON E. Lower bounds for the multi-skill project scheduling problem with hierarchical levels of skills [M]. Berlin: Springer Berlin Heidelberg, 2005: 229-243.
[2] BARZ C, KOLISCH R. Hierarchical multi-skill resource assignment in the telecommunications industry [J]. Production and Operations Management, 2014, 23(3): 489-503.
[3] HURKENS C A J. Incorporating the strength of MIP modeling in schedule construction [J]. RAIRO-Operations Research, 2009, 43(4): 409-420.
[4] ESTELLON B, GARDI F, NOUIOUA K. High-performance local search for task scheduling with human resource allocation [C]∥International Workshop on Enigneering Stochastic Local Search Algorithms. Berlin: Springer Berlin Heidelberg,2009: 1-15.
[5] CORDEAU J F, LAPORTE G, PASIN F, et al. Scheduling technicians and tasks in a telecommunications company [J]. Journal of Scheduling, 2010, 13(4): 393-409.
[6] FIRAT M, HURKENS C A J. An improved MIP-based approach for a multi-skill workforce scheduling problem [J]. Journal of Scheduling, 2012, 15(3): 363-380.
[7] 喻小光,战德臣,聂兰顺,等.柔性资源约束的资源水平项目调度问题[J].计算机集成制造系统,2010,16(9): 1967-1976.
YU Xiao-guang, ZHAN De-chen, NIE Lan-shun, et al. Flexible resource constrained resource leveling project scheduling problem [J]. Computer Integrated Manufacturing Systems, 2010, 16(9): 1967-1976.
[8] 陈君兰,叶春明.柔性资源受限多项目调度的混沌粒子群算法研究[J].计算机应用研究,2013,30(1): 117120.
CHEN Jun-lan, YE Chun-ming. Chaos particle swarm optimization on flexible-resource constrained multi-project scheduling research [J]. Application Research of Computers, 2013, 30(1): 117-120.
[9] VALLS V, PEREZ A, QUINTANILLA S. Skilled workforce scheduling in service centres [J]. European Journal of Operational Research, 2009, 193(3): 791-804.
[10] HEIMERL C, KOLISCH R. Scheduling and staffing multiple projects with a multi-skilled workforce [J]. OR Spectrum, 2010, 32(2): 343-368.
[11] CHEN J, ZHU J, ZHANG D. Multi-project scheduling problem with human resources based on dynamic programming and staff time coefficient[C]∥Management Science & Engineering (ICMSE), 2014 International Conference on. Helsinki:IEEE, 2014: 1012-1018.
[12] NABER A, KOLISCH R. MIP Models for resourceconstrained project scheduling with flexible resource profiles [J]. European Journal of Operational Research, 2014, 239(2): 335-348.
[13] FERNANDEZ V V, FRAMINAN J M. Integrated project scheduling and staff assignment with controllable processing times [J]. The Scientific World Journal, 2014, 2014(1): 1-16.
[14] 周辅疆,陈宏文,王斌,等.改进柔性资源约束项目调度模型与粒子群算法[J].火力与指挥控制,2016, 41(1): 62-66.
ZHOU Fu-jiang, CHEN Hong-wen, WANG Bin, et al. Modified model of flexible resource-constrained multi-mode project scheduling problem and particle swarm optimization [J]. Fire Control & Command Control, 2016, 41(1): 62-66.
[15] JARBOUI B, DAMAK N, SIARRY P, et al. A combinatorial particle swarm optimization for solving multi-mode resource-constrained project scheduling problems[J]. Applied Mathematics & Computation, 2008, 195(1): 299-308.
[16] PETEGHEM V V, VANHOUCKE M. A genetic algorithm for the preemptive and non-preemptive multi-mode resource-constrained project scheduling problem [J]. European Journal of Operational Research, 2010, 201(2): 409-418.
[17] PETEGHEM V V, VANHOUCKE M. An experimental investigation of metaheuristics for the multi-mode resource-constrained project scheduling problem on new dataset instances [J]. European Journal of Operational Research, 2014, 235(1): 62-72.
[18] 王万良,吴启迪.生产调度智能算法及其应用[M].北京:科学出版社,2007: 15-21.
[1] 王雅静,王群,李博闻,刘志文,朴媛媛,遇涛. 基于脑电信号预发作数据段选取的癫痫发作预测[J]. 浙江大学学报(工学版), 2020, 54(11): 2258-2265.
[2] 席志鹏,楼卓,李晓霞,孙艳,杨强,颜文俊. 集中式光伏电站巡检无人机视觉定位与导航[J]. 浙江大学学报(工学版), 2019, 53(5): 880-888.
[3] 荆丹翔,韩军,徐志伟,陈鹰. 基于成像声呐的水下多目标跟踪研究[J]. 浙江大学学报(工学版), 2019, 53(4): 753-760.
[4] 周炳海, 赵猛. 柔性Job Shops集成调度启发式算法[J]. 浙江大学学报(工学版), 2016, 50(6): 1073-1079.
[5] 周炳海, 陈锦祥, 赵猛. 基于晶圆优先级的连续型Interbay搬运系统性能分析[J]. 浙江大学学报(工学版), 2015, 49(2): 296-302.
[6] 赵立杰, 柴天佑, 袁德成, 刁晓坤. 增强操作工况识别可靠性的概率PLS-ELM方法[J]. J4, 2013, 47(10): 1747-1752.
[7] 孙跃, 赵志斌, 苏玉刚, 唐春森. 非接触电能传输系统参数非线性规划[J]. J4, 2013, 47(2): 353-360.
[8] 孟庆龙, 王元. 基于CFD的空间场温度系统建模与控制[J]. J4, 2012, 46(8): 1478-1484.
[9] 赵立杰, 汤健, 柴天佑. 基于选择性极限学习机集成的磨机负荷软测量[J]. J4, 2011, 45(12): 2088-2092.
[10] 夏明, 董亚波, 鲁东明. 无线传感网逐跳自适应FEC传输可靠性
保证方法
[J]. J4, 2011, 45(2): 273-279.
[11] 孙宁, 张化光, 王智良. 不确定分数阶混沌系统的滑模投影同步[J]. J4, 2010, 44(7): 1288-1291.
[12] 王建中, 金波, 鲁仁全. 基于渗漏模型的城市排水系统建模与分析[J]. J4, 2010, 44(7): 1382-1386.
[13] 汤健, 赵立杰, 岳恒, 柴天佑. 基于多源数据特征融合的球磨机负荷软测量[J]. J4, 2010, 44(7): 1406-1413.