基于多参考剖面评价的多目标项目调度问题新视角

《European Journal of Operational Research》：A new perspective on multi-objective project scheduling problems: Evaluating with multiple reference profiles

　　

在多项目调度中，拖期时间（Tardiness）与资源平准成本（Resource Levelling Cost, RLC）之间存在权衡关系。本研究探讨了冲突目标之间的非补偿性（non-compensatory）关系。决策者的偏好通过多个参考剖面（reference profiles）来表征。研究人员将一种偏好引导框架嵌入到多目标进化搜索中。实验表明，所提方法在偏好满意度方面优于现有方法。

论文解读文章

一、研究背景与动机

项目调度是项目管理的基础环节，旨在确保活动在满足优先关系和资源约束的前提下高效执行。其中，资源受限项目调度问题（Resource-Constrained Project Scheduling Problem, RCPSP）是学术界和工业界（如建筑、软件开发、制造业）中研究最广泛且最具实践意义的问题之一。经典的RCPSP通常以最小化项目工期（makespan）为目标。然而，现实中的项目管理往往涉及多个相互冲突的目标，例如最小化项目拖期时间（Tardiness）、平衡资源分配（Resource Levelling）或最大化净现值（Net Present Value），由此产生了多目标资源受限项目调度问题（Multi-Objective Resource-Constrained Project Scheduling Problem, MORCPSP）。

在MORCPSP中，决策者经常面临一个目标的改善无法线性或成比例地补偿另一个目标恶化的情况，这反映了非补偿性偏好结构。当同时考虑拖期时间和资源平准成本（Resource Levelling Cost, RLC）这两个目标时尤为明显，因为它们分别代表了不同利益相关者的管理关切。拖期时间衡量项目超过预定截止日期的惩罚，与合同罚款、客户信心丧失以及下游活动延迟密切相关；而RLC则惩罚项目周期内资源使用的不均衡，因为过度波动可能导致频繁的人员调整、设备闲置或过载以及更高的执行风险。实践中，一旦资源波动超出组织的容忍水平，即使拖期性能良好，该调度方案也可能因资源角度不可接受而被否决。

现有MORCPSP方法在处理非补偿性偏好时存在局限：帕累托（Pareto）方法生成的解集理论丰富但过于庞大，难以直接支撑管理决策；ε-约束（epsilon-constraint）方法需要指定难以确定的合适ε水平，且同样返回大量候选方案；加权和方法虽能给出单一最优解，但要求决策者事先给出精确的补偿权重。因此，这些方法均不适用于非补偿性偏好结构下的决策环境。为解决这一局限性，研究人员引入了一种基于阈值的偏好表示方式，通过满意度水平（即参考剖面）来表达决策者对多个目标的偏好，进而提出了多参考剖面评价（Evaluating with Multiple Reference Profiles, EMP）程序，用于评估和排序候选调度方案，并将由此导出的EMP度量嵌入底层多目标启发式算法（Multi-Objective Heuristic Algorithm, MOHA）的适应度评价与选择机制中，形成了MOHA-EMP框架。

本研究的贡献在于：首次处理MORCPSP中拖期时间与RLC之间的非补偿性关系；提出新颖的MOHA-EMP框架，将源自参考剖面的EMP度量作为偏好引导的适应度与选择机制嵌入五种MOHA；通过大规模人工项目实例的实验证明MOHA-EMP能提升偏好满意度；提出基于阈值的参考剖面偏好表达可作为精确赋权和从大型非支配解集中选择的有效替代方案。

二、主要关键技术方法

研究人员采用了以下关键技术方法：

1. 1.
   多参考剖面评价（EMP）程序：设计了一种基于阈值的偏好表示方法，决策者通过设定多个满意度水平（即参考剖面）来表达对拖期时间和RLC两个目标的非补偿性偏好。EMP程序据此评估和排序候选调度方案，并导出EMP度量作为适应度指标。
2. 2.
   偏好引导的多目标进化搜索框架（MOHA-EMP）：将EMP度量嵌入到五种不同的多目标启发式算法的适应度评价与选择机制中，使搜索过程逐步淘汰不被决策者接受的方案，并向更满意的解空间引导。这五种底层算法包括：非支配排序遗传算法（Non-dominated Sorting Genetic Algorithm II, NSGA-II）、ε-约束遗传算法（Epsilon-Constraint Genetic Algorithm, ECGA）、非支配锦标赛遗传算法（Non-dominated Tournament Genetic Algorithm 2, NTGA2）、其扩展版本——平衡非支配锦标赛遗传算法（Balanced Non-dominated Tournament Genetic Algorithm, bNTGA），以及基于分解的多目标进化算法（Multi-objective Evolutionary Algorithm based on Decomposition, MOEA/D）。
3. 3.
   实验验证：在大规模人工生成的项目实例集上进行广泛计算实验，对比五种基础算法及其对应的MOHA-EMP变体，以评估偏好满意度的提升效果。

三、研究结果

3.1 文献综述发现

通过对MORCPSP文献的系统梳理，研究人员识别出两大空白：第一，多目标间的非补偿性关系鲜有研究，特别是拖期时间与RLC的非补偿性本质未被探讨；第二，现有MORCPSP方法很少融入决策者偏好，且尚无研究考察在进化过程中结合渐进式整合与后验选择偏好的互补机制。

3.2 问题描述

研究人员将MORCPSP建模为一个双目标优化问题，目标函数分别为最小化拖期时间和最小化RLC。在此基础上，定义了相应的决策问题：给定一组候选非支配调度方案和决策者的偏好信息（通过序数优先级排序和一组参考剖面表达），目标是采用与非补偿性偏好一致的方式评估和排序这些方案。

3.3 方法论开发

研究人员提出了完整的MOHA-EMP框架，其核心创新在于：利用决策者提供的多个参考剖面（例如，对拖期时间的可接受上限和对RLC的可接受上限）定义EMP度量，该度量能够量化一个调度方案相对于所有参考剖面的综合满意度。将该度量作为适应度函数的一部分嵌入进化算法的选择算子，使得搜索过程优先保留那些在所有参考剖面上表现更优的方案，从而引导种群向符合决策者非补偿性偏好的区域收敛。

3.4 实验结果

通过在多种规模和复杂度的人工项目实例上的实验，研究人员发现：

• •
  相比于原始的NSGA-II、ECGA、NTGA2、bNTGA和MOEA/D，对应的MOHA-EMP变体在满足决策者偏好方面均有显著提升。
• •
  MOHA-EMP框架能够有效地将搜索聚焦于决策者真正关心的解区域，减少了对不相关帕累托前沿区域的探索，提高了搜索效率。
• •
  基于参考剖面的偏好表达方式比传统的加权和方法更符合非补偿性决策的实际情境，且比从庞大帕累托解集中手动选择更为直观和便捷。

四、讨论与结论

讨论部分：本研究提出的MOHA-EMP框架成功地将非补偿性偏好融入MORCPSP求解过程，填补了现有文献在处理拖期时间与RLC非补偿关系方面的空白。实验结果表明，该框架能够有效引导搜索，产生更符合决策者期望的调度方案。这种基于参考剖面的方法为决策者提供了一种自然且易于理解的偏好表达方式，避免了精确赋权的困难。研究也指出，该方法目前主要针对双目标情形，未来可扩展到更多目标。此外，如何动态更新参考剖面以适应决策者偏好的演变也是值得探索的方向。

结论部分：本研究首次系统地处理了MORCPSP中拖期时间与资源平准成本之间的非补偿性关系。通过提出MOHA-EMP框架，研究人员将基于多参考剖面的EMP度量嵌入五种主流多目标进化算法，实现了偏好引导的搜索。在大量人工项目实例上的实验证实，MOHA-EMP框架能够显著提升最终调度方案对决策者偏好的满意度。该研究为项目调度领域提供了一种处理非补偿性多目标决策的有效工具，并为阈值型偏好表达在复杂优化问题中的应用提供了新的思路。