基于强化学习的多技能项目调度算法

Reinforcement learning-based algorithm for multi-skill project scheduling problem

中文关键词  多技能资源  项目调度  智能算法  强化学习  并行调度

英文关键词  multi-skill resource  project scheduling  intelligence algorithm  reinforcement learning  PSGS

中文摘要

      多技能项目调度存在组合爆炸的现象, 其问题复杂度远超传统的单技能项目调度, 启发式算法和元启发式 算法在求解多技能项目调度问题时也各有缺陷. 为此, 根据项目调度的特点和强化学习的算法逻辑, 本文设计了基 于强化学习的多技能项目调度算法. 首先, 将多技能项目调度过程建模为符合马尔科夫性质的序贯决策过程, 并依 据决策过程设计了双智能体机制. 而后, 通过状态整合和行动分解, 降低了价值函数的学习难度. 最后, 为进一步提 高算法性能, 针对资源的多技能特性, 设计了技能归并法, 显著降低了资源分配算法的时间复杂度. 与启发式算法的 对比实验显示, 本文所设计的强化学习算法求解性能更高, 与元启发式算法的对比实验表明, 该算法稳定性更强, 且 求解速度更快.

英文摘要

      Combinatorial explosion is a common phenomenon in multi-skill project scheduling, which leads to higher complexity in multi-skill project scheduling problem (MSPSP) than in traditional single-skill project scheduling problem. Heuristics and meta-heuristics have disadvantages in solving MSPSP. Therefore, based on the characteristics of project scheduling and the algorithmic logic of reinforcement learning, a multi-skilled project scheduling algorithm based on reinforcement learning is designed in this paper. Firstly, the multi-skill project scheduling process is modeled as a Markov decision process (MDP). Then, a double-agent mechanism is proposed, and state integration method and action decomposition method are designed to reduce the complexity of value function learning. Finally, skills conflation algorithm is developed to reduce the time complexity of allocating resources in MSPSP. Comparative experiments between the proposed RL algorithm and heuristics show that the reinforcement learning (RL) has better performance, and experiments between the proposed RL algorithm and meta-heuristics show that the RL has higher stability and shorter running time.