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