针对线性规划(LP)对NP问题的解决的有限性，NP问题复杂度增加的时候就引出了启发式算法对问题的求解。对RCPSP问题是典型的NP问题，针对这个问题结合了很多流行的算法，简要的介绍。

1.基于优先权规则的启发式算法

基于不同的优先权规则从可安排活动集合中选择活动，常用的优先权规则主要有：最大分级位置权重规则、最迟完成时间规则、最多紧后活动规则、最迟开始时间规则、最小松弛规则。另外还有扩展出多通道算法，如：多重优先权规则启发式算法、前向-后向进度安排启发式算法、抽样性启发式算法、适应性启发式算法等等。

2.超启发式算法

该类算法将项目进度表述为一组编码，利用超启发式策略对编码进行搜索优选后，再转化为进度安排。进度安排常用的表述方式有活动列表、随机键、转移向量、进度设计、直接表述。

求解RCPSP常用的启发式策略有模拟退火、禁忌搜索、遗传算法等。

①模拟退火：从某个初始解开始，一个邻点通过对当前解的扩展来生成。如果邻点好于当前解则被接受；否则，它以一定的概率被接受，接受概率依赖于该解变坏的程度以及当前的温度参数。随着算法的进行，温度被逐步降低以减小接受坏的邻点的概率。达到规定的温度后算法终止，最后固定下来的解即为满意解。

②禁忌搜索：对于所有邻点解进行评价并选择其中最好的一个进行进一步的搜索。为了避免搜索返回刚刚离开的局部最优点而形成循环，通过建立一个禁忌列表来限制向某些邻点的移动。这种禁忌状态在某种特定的条件下也可以被重新激活。

③遗传算法(GA)：并行地考虑解的一个集合或群体, 在已生成的初始群体的基础上, 新的解通过交叉和/或变异操作来获得。在新解生成后，适应度通常用所求解问题的目标函数来表示最高的解“生存”下来构成下一代，而其余的解通过所谓的选择机制被淘汰，从而使解的质量不断得到改善。优点在于采用启发式群体随机搜索的方法，在搜索的过程中不易陷入局部最优。但是其缺陷是局部搜索能力较差并容易早熟收敛。

   其他类型的启发式算法如蚁群算法(ACO)、可变邻点搜索技术等。超启发式算法被普遍认为是在性能、可扩展性和易于实现性等方面权衡后的最佳方法。目前学者们研究资源受限项目调度问题最常用的方法。

转载本文请联系原作者获取授权，同时请注明本文来自方晓汾科学网博客。
链接地址：https://m.sciencenet.cn/blog-87352-331679.html

上一篇：项目管理研究文献阅读
下一篇：约束理论(TOC)