摘要
This paper proposes a new extension of the multi-skill resource-constrained project scheduling problem: MSRCPSP with skill switches. In real-world environment, the switch between skills for a resource often incurs considerable extra operation time and cost to meet the requirement of task. A mixed-integer programming model, aiming to minimize project completion time and total cost, is developed. Then, to solve this new problem effectively, we investigate the related existing solution representations and schedule builders from previous literature. Based on the investigation, we propose a new flexible solution representation scheme with reduced search space and a novel greedy-like schedule builder scheme that reorders tasks to reduce skill switches. Besides, we select two efficient mutation operators, i.e., a swap operator and a resource-leveling operator. The swap operator adjusts the task assignment sequence while the resource-leveling operator reassigns the tasks to other resources based on the resource loads of the current schedule. This operator improves solutions by balancing resource loads. We embed all the proposed new components into a multi-objective evolution strategy (MOES) framework. We analyze different configurations of MOES in terms of representation, schedule builder, and mutation operators, and identify the best configuration. We compare the result of MOES with the state-of-the-art algorithms on a wide range of test instances, and the results show that our proposed representation scheme and schedule builder can improve the convergence of the Pareto Front, while the resource-leveling operator can greatly improve the spread and diversity of the front.
学科与关键词
- Multi-skill resource constrained project scheduling using a multi-objective discrete Jaya algorithmLi, Yang-Yuan; Lin, Jian*; Wang, Zhou-JingApplied Intelligence, 2022, 52(5): 5718-5738.被引 19
- Hybrid Differential Evolution and Greedy Algorithm (DEGR) for solving Multi-Skill Resource-Constrained Project Scheduling ProblemMyszkowski, Pawel B.*; Olech, Lukasz P.; Laszczyk, Maciej; Skowronski, Marek E.APPLIED SOFT COMPUTING, 2018, 62: 1-14.被引 71
- 考虑技能水平的多技能资源约束项目调度任逸飞; 陆志强; 刘欣仪; 张猛浙江大学学报(工学版), 2017, 51(5).
