多技能资源受限项目调度问题的图模型构建与最近邻搜索算法研究

本文提出了一种基于析取图模型和项目工期浮动值引导(ν-GNNS)的最近邻搜索算法，用于解决多技能资源受限项目调度问题(MS-RCPSP)。该算法通过构建ν-table属性矩阵记录邻域解改进值，结合资源导向编码和关键路径法(CPM)前向解码机制，在iMOPSE基准测试中平均缩短项目完成时间1.14小时，21个实例达到理论下界。

　　

亮点

本文首次将"最小距离"理论应用于MS-RCPSP领域，提出ν-GNNS算法在稳定可预测的邻域解空间进行渐进式搜索。通过ν-table精确映射可行解最近邻域内项目完成时间的改进值，该矩阵能有效指导算法的前后向交替搜索。

结论

本研究构建的析取图模型通过ν-table快速计算机制，实现了对可行解最近邻域内项目完成时间C_max的精准映射。基于最近邻搜索原理设计的ν-GNNS算法架构，利用ν-table呈现的问题特征指导有效搜索路径，在资源导向编码与CPM前向解码机制的协同下，显著提升了多技能项目调度效率。

未来研究方向

后续研究将聚焦于动态技能矩阵的实时更新机制，以及基于深度强化学习的ν-table预测模型构建，进一步拓展算法在医疗资源配置(Healthcare Resource Allocation)和制药生产排程(Pharmaceutical Production Scheduling)等生命科学领域的应用场景。