求解资源受限项目调度问题的分支定价算法

摘要：

资源受限项目调度问题是最具代表性的一类项目调度问题,是很多实际调度问题的抽象表示,属于NP-hard问题,对于大规模问题难以求得全局最优解.文中提出了问题的整数规划模型,通过将模型分解为约束主问题和子问题设计了求解线性松弛模型的列生成方法,然后通过分支定价寻找问题的整数解.在求解过程中引入松弛变量解决模型伪不可解的问题,设计了剪支策略和分支策略,并根据不同情况提出了两种缩小解空间的方法.在PS PL IB基准数据集上,对于有30个工序的问题,所提算法在10 m内能够求出480个问题中的301个问题的当前最优解;对于有60个工序的问题,在20 m内能够求出480个问题中的269个问题的当前最优解;对于有90个工序的问题,在30 m内能够求出480个问题中的263个问题的当前最优解.同时,算法使用缩小解空间策略后,超时算例的个数明显减少,优化初始解的性能得到明显提升.以上实验结果表明,所提算法具有较好的求解能力.

关键词：资源受限项目调度、整数规划、列生成、分支定价、伪不可解

所属期刊栏目：49

分类号：TP181(自动化基础理论)

在线出版日期：2022-12-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：274-282