考虑员工技能等级的软件项目多目标超启发式调度
作者单位:

南京信息工程大学

基金项目:

国家自然科学基金资助项目(61502239);江苏省自然科学基金(BK20150924)


Multi-objective Hyper-heuristic Scheduling of Software Project Considering Employee Skill Level
Author:
Affiliation:

Nanjing University of Information Science and Technology

Fund Project:

Multi-objective Hyper-heuristic Scheduling of Software Project Considering Employee Skill Level

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献
  • | |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    以最优化项目工期和员工满意度为目标,建立多目标软件项目调度问题的数学模型。该模型考虑员工的技能等级划分、任务重要程度等实际因素,并将重要任务与高技能等级员工相匹配。提出一种基于Q学习的超启发式算法求解该模型。基于交叉算子和引入随机抖动的Jaya算子对任务-员工矩阵进行全局搜索;利用问题信息设计了减少项目工期和增加员工满意度的局部挖掘策略;将全局搜索算子、邻域参数的取值和局部挖掘策略组合为八种低层启发式策略;给出一种基于Q学习的高层策略,根据低层策略的历史表现为不同进化状态下的种群自适应选择合适的低层策略。实验结果表明所提算法在绝大多数算例上的HVR和IGD性能优于代表性算法。

    Abstract:

    A mathematical model is formulated for the multi-objective software project scheduling problem, aiming to optimize both the project duration and employee satisfaction. The model takes into account practical factors such as the skill level classification of employees and the importance of tasks, and matches important tasks with employees of high skill levels. A hyper-heuristic algorithm based on Q-learning is proposed to solve the model. A global search of the task-employee matrix is performed based on the matrix crossover operator and Jaya operator with random jitter; The local search strategies are designed to reduce the project duration and increase the employee satisfaction by using the problem information; The global search operators, the neighborhood parameter values, and the local search strategies are combined to form eight low-level heuristics; Providing a high-level strategy based on Q-learning that adaptively selects appropriate low-level heuristics for different evolutionary states of the population, based on the historical performance of the low-level heuristics. The experimental results show that the proposed algorithm outperforms the representative algorithms in terms of HVR and IGD on most of the cases.

    参考文献
    [1] 赵旭,闫春明.探析软件工程技术现状与未来发展趋势[J].电子元器件与信息技术. 2021, 5(11):1-2
    ZHAO Xu, YAN Chunming. Analysis on the Current Situation and Future Development Trend of Software Engineering Technology[J], Electronic Component and Information Technology. 2021, 5(11):1-2
    [3] [2] Chen W N,Zhang J. Ant colony optimization for software project scheduling and staffing with an event-based scheduler [J]. IEEE Transactions on Software Engineering. 2013, 39(1): 1-17
    [4] [3] Alba E, Chicano J F. Software project management with Gas[J]. Information sciences. 2007, 177(11):2380-401
    [5] [4] Kosztyán Z T, Bogdány E, Szalkai I, et al. Impacts of synergies on software project scheduling[J]. Annals of Operations Research. 2022, 312:883-908
    [6] [5] Li Q, Sun Q, Tao S, et al. Multi-skill project scheduling with skill evolution and cooperation effectiveness. Engineering[J], Construction and Architectural Management. 2020, 27(8):2023-2045
    [7] [6] 王培源.基于区间效率的多技能多目标软件项目调度进化优化[D]. 徐州: 中国矿业大学, 2022
    WANG Peiyuan. Interval-efficiency-based Multi-Skill and Multi-Objective Software Project Evolutionary Scheduling[D]. Xuzhou: China University of Mining and Technology, 2022
    [9] [7] Li H, Zhu H, Zheng L, et al. Software project scheduling under activity duration uncertainty[J]. Annals of Operations Research. 2023, 1-36.
    [10] [8] 肖菁, 吴洲. 基于时间轴的软件多项目任务调度遗传算法[J]. 计算机科学. 2012, 39(12):133-138
    XIAO Jing, WU Zhou. Software Multi-project Scheduling Genetic Algorithms Based on a Time-line Model[J]. Computer Science. 2012, 39(12):133-138
    [12] [9] Chen R, Liang C Y, Gu D X, et al. A competence-time-quality scheduling model of multi-skilled sta? for IT project portfolio[J]. Computers & Industrial Engineering. 2020, 139: 1-17
    [13] [10] Crawford B, Soto R, Johnson F, et al. A max–min ant system algorithm to solve the software project scheduling problem[J]. Expert Systems with Applications. 2014, 41(15): 6634-6645
    [14] [11] Shen X, Guo Y, Li A. Cooperative coevolution with an improved resource allocation for large-scale multi-objective software project scheduling[J]. Applied Soft Computing. 2020, 88:106059
    [15] [12] Cowling P, Kendall G, Soubeiga E. A hyperheuristic approach to scheduling a sales summit[C]//Practice and Theory of Automated Timetabling III: Third International Conference, PATAT 2000 Konstanz, August 16–18, 2000, Germany, Springer Berlin Heidelberg, 2001: 176-190
    [16] [13] Shao Z, Shao W, Chen J, et al. A feedback learning-based selection hyper-heuristic for distributed heterogeneous hybrid blocking flow-shop scheduling problem with flexible assembly and setup time[J]. Engineering Applications of Artificial Intelligence. 2024, 131:107818
    [17] [14] 尹丹,胡蓉,钱斌等. 混合超启发式算法求解复杂两级车辆路径问题[J].云南大学学报(自然科学版). 2024, 46(01): 23-37
    YIN Dan, HU Rong, QIAN Bin, et al. Hybrid hyper-heuristics algorithm for solving complex two-echelon vehicle routing problem[J]. Journal of Yunnan University (Natural Sciences Edition). 2024, 46(01): 23-37
    [19] [15] 刘思宇,李铁克,王柏琳等. 混合流水车间插单重调度的超启发式遗传算法[J].计算机应用研究. 2023, 40(09): 2609-2615
    LIU Siyu, LI Tieke, WANG Bailin, et al. Hyper-heuristic genetic algorithm for hybrid flow shop with
    rush orders insertion rescheduling problem[J]. Application Research of Computers. 2023, 40(09): 2609-2615
    [22] [16] Qi R, Li J Q, Wang J, et al. QMOEA: A Q-learning-based multiobjective evolutionary algorithm for solving time-dependent green vehicle routing problems with time windows[J]. Information Sciences. 2022, 608:178-201
    [23] [17] Zhao F, Di S, Wang L. A hyperheuristic with Q-learning for the multiobjective energy-efficient distributed blocking flow shop scheduling problem[J]. IEEE Transactions on Cybernetics. 2022, 53(5): 3337-3350
    [24] [18] Zhang W, Geng H, Li C, et al. Q-learning-based multi-objective particle swarm optimization with local search within factories for energy-efficient distributed flow-shop scheduling problem[J]. Journal of Intelligent Manufacturing. 2023, 1-24
    [25] [19] Ji J J, Guo Y N, Gao X Z, et al. Q-learning-based hyperheuristic evolutionary algorithm for dynamic task allocation of crowdsensing[J]. IEEE Transactions on Cybernetics. 2021, 53(4):2211-2224
    [26] [20] Hou YE, Gu W, Wang C, Yang K, Wang Y. A Selection Hyper-heuristic based on Q-learning for School Bus Routing Problem[J]. IAENG International Journal of Applied Mathematics. 2022, 52(4):1-9
    [27] [21] Chang C K, Jiang H, Di Y, et al. Time-line based model for software project scheduling with genetic algorithms[J]. Information and Software Technology. 2008, 50: 1142-1154
    [28] [22] 周鹏程,王梦.员工技能等级模型剖析[J].人力资源. 2009, (05):47-49
    ZHOU Pengcheng, Wang Meng. Analysis of Employee Skill Level Model[J]. Human Resources. 2009, (05):47-49
    [30] [23] 马耀娟.H公司人员分类分级培养体系研究[D].南昌: 南昌大学, 2021
    MA Yaojuan. Research on the employees classification and grading training system of H company[D]. Nanchang: Nanchang University, 2021
    [32] [24] 宁明超,张俊勃,陈戈.基于面向服务架构的工业软件的任务调度算法[J].计算机应用. 2023, 43(03):885-893
    NING Mingchao,ZHANG Junbo,CHEN Ge. Task scheduling algorithm for service-oriented architecture-based industrial software[J]. Journal of Computer Applications. 2023, 43(03):885-893
    [34] [25] Minku L L, Sudholt D, Yao X. Improved evolutionary algorithm design for the project scheduling problem based on runtime analysis[J]. IEEE Transactions on Software Engineering. 2013, 40(1):83-102
    [35] [26] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE transactions on evolutionary computation. 2002, 6(2):182-197
    [36] [27] Zhang S, Yang T, Liang J, et al. A Novel Adaptive Bandit-Based Selection Hyper-Heuristic for Multiobjective Optimization[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems. 2023, 53(12):7693–7706
    [37] [28] Li R, Gong W, Lu C. A reinforcement learning based RMOEA/D for bi-objective fuzzy flexible job shop scheduling[J]. Expert Systems with Applications. 2022, 203:117380
    [38] [29] Cimbala J M. Taguchi orthogonal arrays[J]. Pennsylvania State University. 2014, 1-3
    [39] [30] Van Veldhuizen D A, Lamont G B. Multiobjective evolutionary algorithm test suites[C] // In Proceedings of the 1999 ACM symposium on Applied computing. New York, ACM, 1999: 351-357
    [40] [31] 张铭显. 316L(N)奥氏体不锈钢晶间腐蚀与晶界特征分布优化的研究[D].北京: 北京科技大学, 2017
    ZHANG Mingxian. Study on the intergranular corrosion and the optimization of grain boundary character distribution of 316L(N) austenitic stainless steel[D]. Beijing: University of Science and Technology Beijing, 2017
    [42] [32] Zhao F, Ma R, Wang L. A self-learning discrete jaya algorithm for multiobjective energy-efficient distributed no-idle flow-shop scheduling problem in heterogeneous factory system[J]. IEEE Transactions on Cybernetics. 2021, 52(12):12675-12686
    [43] [33] Wu X, Consoli P, Minku L, et al. An evolutionary hyper-heuristic for the software project scheduling problem[C] // In Parallel Problem Solving from Nature–PPSN XIV: 14th International Conference. September 17-21, 2016, UK, Springer International Publishing. 2016, 37-47
    [44] [34] Vincent F Y, Maglasang R, Tsao Y C. A reduced variable neighborhood search-based hyperheuristic for the shelf space allocation problem[J]. Computers & Industrial Engineering. 2020, 143:106420
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

申晓宁,陈文言,陈星晖,佘娟.考虑员工技能等级的软件项目多目标超启发式调度[J].南京信息工程大学学报,,():

复制
分享
文章指标
  • 点击次数:52
  • 下载次数: 0
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2024-05-16
  • 最后修改日期:2024-06-04
  • 录用日期:2024-06-05

地址:江苏省南京市宁六路219号    邮编:210044

联系电话:025-58731025    E-mail:nxdxb@nuist.edu.cn

南京信息工程大学学报 ® 2025 版权所有  技术支持:北京勤云科技发展有限公司