基于整数规划强对偶求解一类局域性资源受限项目调度问题

摘要：

资源受限项目调度问题(简称RCPSP)是最具代表性的项目调度问题之一,调度过程可理解为,将受资源约束的平行工序调整为顺序工序.本文针对实际中广泛存在的资源局域、而非全局受限的情况,研究局域性RCPSP,并重点考虑一类问题:项目某环节的一系列平行工序,可用资源量只有一半,各资源可重复利用且具有相应多功能,但最多能承担2个工序,需将这些工序两两排列成对,实现项目工期最短.本文首先探索问题"局域性"特征,量化局域调度对项目工期的影响;基于此,构建只涵盖"局域调度工序"的0-1规划模型;再者,发展整数规划强对偶理论,结合Dangzig-Wolfe分解等方法,提出多项式时间的精确算法;最后通过算例测试,验证算法优势,例如,计算大规模算例的最优解,运用该算法比常规精确方法可快数万倍以上.

关键词：资源受限项目调度、整数规划强对偶、多项式时间精确算法、Dangzig-Wolfe分解

所属期刊栏目：30

分类号：O221(运筹学)

资助基金：国家自然科学基金;国家自然科学基金

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

页数：共11页

页码：159-169