文档介绍：该【求解资源受限项目调度问题的分支定价算法 张宇哲 】是由【林之孝】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【求解资源受限项目调度问题的分支定价算法 张宇哲 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:.
计算机科学
ComputerScience
ISSN1002-137X,CN50-1075/TP
《计算机科学》网络首发论文
题目:求解资源受限项目调度问题的分支定价算法
作者:张宇哲,董兴业,周正
收稿日期:2021-11-29
网络首发日期:2022-08-11
引用格式:张宇哲,董兴业,[J/OL].计
://.
网络首发:在编辑部工作流程中,稿件从录用到出版要经历录用定稿、排版定稿、整期汇编定稿等阶
段。录用定稿指内容已经确定,且通过同行评议、主编终审同意刊用的稿件。排版定稿指录用定稿按照期
刊特定版式(包括网络呈现版式)排版后的稿件,可暂不确定出版年、卷、期和页码。整期汇编定稿指出
版年、卷、期、页码均已确定的印刷或数字出版的整期汇编稿件。录用定稿网络首发稿件内容必须符合《出
版管理条例》和《期刊出版管理规定》的有关规定;学术研究成果具有创新性、科学性和先进性,符合编
辑部对刊文的录用要求,不存在学术不端行为及其他侵权行为;稿件内容应基本符合国家有关书刊编辑、
出版的技术标准,正确使用和统一规范语言文字、符号、数字、外文字母、法定计量单位及地图标注等。
为确保录用定稿网络首发的严肃性,录用定稿一经发布,不得修改论文题目、作者、机构名称和学术内容,
只可基于编辑规范进行少量文字的修改。
出版确认:纸质期刊编辑部通过与《中国学术期刊(光盘版)》电子杂志社有限公司签约,在《中国
学术期刊(网络版)》出版传播平台上创办与纸质期刊内容一致的网络版,以单篇或整期出版形式,在印刷
出版之前刊发论文的录用定稿、排版定稿、整期汇编定稿。因为《中国学术期刊(网络版)》是国家新闻出
版广电总局批准的网络连续型出版物(ISSN2096-4188,CN11-6037/Z),所以签约期刊的网络版上网络首
发论文视为正式出版。
:.
췸싧쫗랢쪱볤ꎺ2022-08-1113:16:21
췸싧쫗랢뗘횷ꎺ.
求解资源受限项目调度问题的分支定价算法
张宇哲1董兴业1周正2
1北京交通大学计算机与信息技术学院交通数据分析与挖掘北京市重点实验室北京100044
2中国船舶工业系统工程研究院北京100094
(******@)
摘要资源受限项目调度问题是最具代表性的一类项目调度问题,是很多实际调度问题的抽象表示,属于
NP-hard问题,对于大规模问题难以求得全局最优解。文中提出了问题的整数规划模型,通过将模型分解为
约束主问题和子问题设计了求解线性松弛模型的列生成方法,然后通过分支定价寻找问题的整数解。在求
解过程中引入松弛变量解决模型伪不可解的问题,设计了剪支策略和分支策略,并根据不同情况提出了两
种缩小解空间的方法。在PSPLIB基准数据集上,对于有30个工序的问题,在10min内能够求出480个问
题中的301个问题的当前最优解;对于有60个工序的问题,在20min内能够求出480个问题中的269个
问题的当前最优解;对于有90个工序的问题,在30min内能够求出480个问题中的263个问题的当前最
优解。同时,算法使用缩小解空间策略后,超时算例的个数明显减少,优化初始解的性能得到明显提升。
以上实验结果表明,本文算法具有较好的求解能力。
关键词:资源受限项目调度;整数规划;列生成;分支定价;伪不可解
中图法分类号TP181DOI:
Branch&PriceAlgorithmforResource-constrainedProject
SchedulingProblem
ZHANGYuzhe1,DONGXingye1*,ZHOUZheng2
1BeijingKeyLabofTrafficDataAanlysisandMining,SchoolofComputerandIT,BeijingJiaotongUniversity,
Beijing100044,China
2SystemsEngineeringResearchInstitute,Beijing100094,China
AbstractResource-constrainedprojectschedulingproblem(RCPSP)isthemostrepresentativeschedulingproblem,whichisanabstract
-hardproblemandisdifficulttoobtaintheglobaloptimalsolution
forlarge-,
problemandsomesubproblems,acolumngenerationmethodisdesignedforthesolvingofthelinearrelaxationmodel,andthentheinteger
solutionoftheproblemisfoundthroughbranch&,relaxationvariablesareintroducedtosolvethepseudo
,pruningstrategy,branchstrategy,andtwomethodsforreducingthesolutionspaceaccordingto
,fortheproblemswith30processes,thecurrentoptimalsolutionscanbeobtained
,thecurrentoptimalsolutionscanbeobtainedin20minutes
,thecurrentoptimalsolutionscanbeobtainedin30minutesfor263outof
,byusingthestrategiesofreducingthesolutionspace,thenumberoftimeoutinstancesdecreases
significantly,
algorithmiseffective.
KeywordsRCPSP,Integerprogramming,Columngeneration,Branch&Price,Pseudoinfeasibility
1引言调度目标通常是最小化总完工时间。
资源受限项目调度问题(Resource-Constrain-目前国内外求解RCPSP的思路主要有启发式
edProjectSchedulingProblem,RCPSP)是最具代表算法、元启发式算法和精确算法3种。
性的一类项目调度问题,已被证明是NP-hard问题启发式算法指为问题设计一系列的优先规则
[1]。RCPSP是很多实际调度问题的抽象表示[2],其并根据规则进行调度,可分为串行调度与并行调度
到稿日期:2021-11-29返修日期:2022-04-30
通信作者:董兴业(******@)
:.
两种机制。常用的优先规则有最多紧后工序(Max并比较了5种算法的求解性能。元启发式算法进行
TotalSuccessors,MST)、最迟开始时间(LatestStart群体寻优,因此在寻找较优解的过程中更具导向性,
Time,LST)和最迟完成时间(LatestFinishTime,LFT)求解效果更好。但由于过程较复杂,求解时间远多
等[3]。Kolisch等[4]介绍了串行进度生成机制与并行于启发式算法。
进度生成机制,并比较了在串行进度生成机制下几启发式算法与元启发式算法都无法确保得到
种最经典的优先规则的求解效果。Browing等[5]以最优解,为了保证求得全局最优解,必须采用精确
资源的冲突和分布程度、项目的复杂程度、项目的算法。精确算法指为问题建立数学模型,直接求解
延迟程度为目标,在12320个测试用例上测试了20该数学模型,其中分支定界(Branch&Bound)、动
种优先规则的效果;Türkakn等[6]在RCPSP经典数态规划、整数规划是求解RCPSP的经典方法。
据集PSPLIB上测试了17种优先规则在串行与并Patterson[15]提出了基于紧前关系的分支定界法,
行两种机制下的求解效果,为了更好地探究不同优Rostami等[16]提出通过构造上界改进剪支策略。精
先规则的求解能力,根据工序总数、资源总数、资确算法虽然能够求得全局最优解,但仅适用于小规
源供应情况等组合生成了不同规模的数据集并测模问题,由于计算复杂度过高,无法求解大规模问
试。启发式算法能够在较短的时间内得到一个解,题。
但解的质量通常较差。列生成方法是求解大规模RCPSP问题的有效
元启发式算法是在启发式算法的基础上结合方法。目前该方法针对RCPSP的研究较少,且在现
仿生学的知识进行群体寻优,常见的有蚁群算法[7-有工作中,为了方便对RCPSP建模,通常会放松部
8]、遗传算法[9]、模拟退火算法[10-11]、禁忌搜索算法分约束,导致实际上无法保证取得全局最优解。其
[12]等,通常对工序序列进行编码。Tofighian等[7]发中,Mingozzi等[17]放松了不可抢占约束与部分偏序
现蚁群算法在求解RCPSP中性能普遍较优。Savitri约束,给出了RCPSP的线性规划形式。Brucker等
等[8]总结了蚁群算法求解RCPSP的流程,并分析了[18]在此基础上对线性规划模型做了改动,使其能够
算法参数对求解效果的影响。Jia等[9]使用串行进度使用列生成求解,并结合约束传播构造总完工时间
生成机制将序列转化为调度方案,通过遗传算法不T的下界,虽然其通过确定每个工序的时间窗进一
断优化工序序列。Boctor[10]首先提出使用模拟退火步加强了偏序约束,但该下界仍有可能不满足不可
算法求解RCPSP,从不同的初始解出发搜索不同方抢占约束与偏序约束。Damay等[19]在放松不可抢占
向,根据接受概率判断当前解是否被接受。Pan等约束与偏序约束的条件下重构了线性规划模型,使
[11]使用优先规则MINSLK生成初始解,结合模拟用列生成求解模型,期望找出能够并发执行的工序
退火算法和邻域搜索求解RCPSP。Omer[12]使用并的最优组合,之后再对得到的解进行修正,使其满
行进度生成机制将序列转化为调度方案,通过交换足所有约束。Wang等[20]使用列生成求解需要在处
序列中两个工序的位置获得新解,建立禁忌表来禁理机上执行工序的RCPSP,在子问题中求解出单个
止某些工序的交换。不同的元启发式算法也可以结处理机的方案,在主问题中组合这些方案以获得最
合使用,Pellerin等[13]在PSPLIB上测试了不同结合优总方案,其采用了启发式方法将决策变量由连续
方法的性能并归纳了表现较优的结合策略。Golab转为整数。RCPSP的总体研究现状如图1所示。
等[14]归纳了元启发式算法在RCPSP领域的研究,
:.
RCPSP求解算法
元启发式算法启发式算法精确算法
Meta-HeuristicAlgorithmHeuristicAlgorithmExactAlgorithm
时间耗费最少时间耗费较多时间耗费最多,无法求解大规模问题
求解质量最差求解质量较好能够取得全局最优解
使用列生成求解
无法取得全局最优解大规模问题
现有工作中对约束进行了放松,
这些建模方式仍无法取得全局最优解
图1RCPSP的研究现状
本文提出了一种基于分支定价的精确算法,为≤,∀∈,∀∈𝑃(5)
RCPSP建立列生成主问题与子问题模型,并解决了()≤,∀∈[0,)(6)
求解过程中出现的伪不可解问题。在求解过程中不其中,式(3)表示目标函数为最小化总完工时间;式
断缩小解空间并使用剪支、分支等策略,最终能够(4)表示需要为工序分配足够的执行时间,且执行不
在满足资源约束、偏序约束和不可中断约束的条件能被中断;式(5)表示工序的偏序约束;式(6)表示工
下求得全局最优解。序的资源约束。
2RCPSP定义图2所示为一个简单的调度算例,每个节点表
可更新资源集合={|=1,…,},定义示一个工序,节点间的箭头表示偏序约束。
表示第种资源的总量。1/(2,1)2/(1,3)2/(2,1)3/(1,1)pi/(ri1,ri2)
{}1234i
工序集合=|=1,…,,定义表示工序
2/(2,3)2/(1,1)R1=4
R2=4
的开始时间,表示工序的结束时间,表示执行56
工序所需要的时间,表示工序对第种资源的图2资源受限项目调度问题示例
需求量。𝑃为工序的前序工序集,
前序工序集中的所有工序完成之后才能开始。本问最优调度方案下资源1和2的消耗情况分别
题中的工序皆为不可中断工序,即工序一经执行,如图资源3与图14所示。可以看出,在满足资源约束与占用量
资源1总量
在其完成之前不允许被中断。偏序约束的条件下,4总完工时间为8。
记时间标号∈[0,)。设时刻正在执行的工35
序集为𝐴(),则工序对第种资源的需求量()的
2
取值如式(1)所示,时刻所有工序对第种资源的需6
113
求总量()如式(2)所示,则RCPSP的数学模型如4
2
式(3)至-式(6)所示:时间
,∈𝐴()12345678
()={(1)
0,∉𝐴()图31类型资源消耗情况
()=∑𝑁()(2)
=
minmax{,∀∈}(3)
..+=,∀∈(4)
:.
资源2占用量
资源2总量
4
表1主问题符号
3
5Table1Symbolsofthemasterproblem
2参数名称含义
26
1决策变量,工序的第个方案是否被选中,
131表示被选中,0表示未被选中4
𝑡工序的第个方案在时刻是否在执行,1表时间
12345678
示在执行,0表示未执行
图42类型资源消耗情况工序的第个方案的开始时间
3列生成求解时间轴最大值,初始化为初始解的总完工
直接对大规模问题建立完整的整数规划模型时间
𝑃偏序对集合,(,)表示是的前序工序
时,模型中的决策变量会非常多,导致难以求解。
建立主问题模型如下:
实际上只有小部分决策变量会出现在最优解中,大
min∑(𝑁+1)(𝑁+1)(7)
部分决策变量是“无用”的,不会出现在最优解中,
..∑=1,∀∈(8)
也不必出现在模型中。因此可以先建立一个可行的、
∑∑𝑡≤,∀∈[0,],∀∈(9)
不完整的模型,称为“限制主问题”,然后通过求解
子问题寻找“有用”的决策变量并加入主问题中,直∑1∑11−∑2∑22≤0,∀(1,2)∈𝑃
至主问题达到最优。相比完整模型,通过列生成方(10)
∈{0,1}(11)
法得到的最终模型的复杂度会大幅降低,因此求解
时间也会大大缩短。式(7)表示目标函数为最小化总完工时间,即
;式(8)表示对于任一工序
问题目标函数为最小化总完工时间。为了更好只能选择一个执行方案,该约束有+1行(含两
地表示该目标,在原RCPSP定义的基础上加上首个虚工序);式(9)表示在任一时刻正在执行的所
尾虚工序。虚工序执行所需时间为0且不消耗任何有工序对每种资源的需求总量不能超过资源总量,
资源,仅作为开始和结束的标志。整个调度方案的该约束有×行;式(10)表示偏序约束,处于偏
开始时间为开始虚工序的开始时间,结束时间为结序对中前序位置的工序的完成时间应不大于处于
束虚工序的完成时间。为图2所示算例添加首尾虚后序位置的工序的开始时间,该约束有|𝑃|行;式
工序后的问题示例如图5所示。(11)表示决策变量为0-1变量,若选中工序的
第个决策方案则值为1,否则为0,模型为整数规
1/(2,1)2/(1,3)2/(2,1)3/(1,1)pi/(ri1,ri2)
12划。34i
0/(0,0)2/(2,3)2/(1,1)0/(0,0)R1=4
列生成算法需要获得每行约束的对偶变量,为R2=4
0567
了求得这些对偶变量,将松弛为连续变量,模型
图5为图1所示算例增加虚工序后的问题示例
变为线性规划,称为“松弛限制主问题”,即式(11)变
为式(12)。
在上述符号的基础上,主问题模型中所使用的
0≤≤1(12)
符号如表1所列。
对于工序的一个执行方案,其约束系数在式
(8)所示行中第行为1,其余为0;在式(9)所示行中,
由于工序不可中断,因此从到为连续的,其
:.
开始
构造初始解
使用初始解构造松弛限制主问题
求解主问题,得到对偶变量,
构建并求解每个工序的子问题
所有子问题最优
处于前序位置时为cij,
第i行为1,处于后序位置时为-sij,
其余为0从sij行到cij行为rik,其余为0,重复K次其余为0
值均小于等于0?
[0...0,1,0...0,0...0,ri1...ri1,0...0,0...0,ri2...ri2,0...0,...,cij,...,-sij,...]
图6的约束系数在约束矩阵中所对应的一列
余为0,重复次;在式(10)所示行中处于前序位置求解每个工序的子问题,若所有工序子问题的
时为,处于后序位置时为−。决策变量的约最优值均小于等于0,那么当前主问题已是最优松
弛主问题,停止算法;否则根据子问题最优值最大否
束系数在约束矩阵中所对应的一列如图6所示。
的解构造一个新的工序的执行方案并添加到主问
在上述符号的基础上,子问题模型使用到的符
题中(添加一个决策变量与对应的一列约束系数)。
号如表2所列。根据最优化理论,对于工序的一个
该方案有望使主问题的目标函数值下降最多从而
开始时间,其子问题目标函数如式(13)所示:改进主问题。是算法流程如图7所示。
max+∑𝐾∑𝑦𝑖+𝑝𝑖+∑|𝑃|(13)
=1𝑡=𝑦𝑖𝑡𝑝=0𝑝𝑝选出最优值最大的子问题解,作为对应工
其中,若在第个偏序对中为前序,则𝑝为+;
若在第个偏序对中为后序,则𝑝为−;否则为
序的一个新的执行方案,添加到主问题中
0。求解时遍历[0,),找到能最大化子问题目标函
数的开始时间∈[0,T)。所求得的方案自动满足工
序不可中断约束,而偏序约束和资源约束则在主问
题中满足。若目标函数最大值小于等于0,那么工
序无论从什么时间开始都不能改进当前主问题,否
则得到工序的一个新的开始时间,即工序的一
个新的执行方案。输出松弛最优解
表2子问题符号
Table2Symbolsofthesub-problem图7列生成求解RCPSP流程图
决策变量,表示第个工序执行的开始时
algorithm
间
式(8)的对偶变量,=1,…,
𝑡式(9)的对偶变量,对应于时刻关于资源初始解采用随机生成方式与启发式算法中的
的约束
串行进度生成机制生成,启发式规则为最早开始时
𝑝式(10)的对偶变量,对应于偏序约束∈
间(EST)与最多紧后工序(MTS)[3]。
𝑃
𝑝𝑝在目标函数中的系数,即式(10)中的约调度环境中的工序分为已调度工序集𝐹、所有
束系数
前序工序已经处于𝐹的工序集以及未调度工序
,使用
集。工序∈的最早可开始时间为
初始解构建松弛限制主问题。每次求解当前主问题,
max{max∈𝑃𝑖,满足资源约束的最早开始时间}。
得到每行约束的对偶变量,构建每个工序的子问题。
:.
开始
,得到松弛限制主问题
将主问题作为根节点加入分支二叉树BT
BT已被完全遍历?
否
按照遍历策略从BT中取出一个节点
每次从中选出一个工序,计算其最早开始时所示,其中上界初始化为初始解的总完工时间。在root:由初始解构建的主问题
root是
间,并令其从此时刻开始。,分支定价算法上界:初始解目标函数值
从BT中删除该节点x1=1x1=0已经访问过该节点?
与3个集合。重复选工序的过程,直至选出所有工流程如图9所示。
是
序。对于EST,每次从CS中选择具有最早可开始x=1x=0
22
时间的工序;对于MTS,每次从CS中选择紧后工主问题不可行,剪支否
序数最多的工序;对于随机生成方式,每次从CS中
x3=1x3=0x4=1x4=0
随机选择一个工序。使用列生成优化主问题,求最优解
......
生成初始解时,随机方式运行5次,EST和
MTS各运行1次,取总完工时间最小的结果作为初最优目标值不小于上界,剪支找到整数解,更新上界
始解。
图8分支定价搜索过程示例
4分支定价求解是
&price
?
由于对决策变量进行了松弛,即经过第3节得
到的是松弛最优主问题,因此求得的最优解中可能
存在小数,这显然是不可行的。此时可以采用分支
定价法逐步确定每个非整数变量的整数取值。否
分支定界算法的思想是根据问题特点设计分
支策略,分解原问题可行域,在各子域内求解松弛
根据分支策略分为xij=0和xij=1两支,
问题,通过逐渐缩小解的上下界来获得最优整数解。
其与列生成结合被称为分支定价,每次分支后对当作为该节点的子节点加入BT
前节点重新进行列生成,优化主问题。
对于松弛最优解中的某个小数决策变量在
最优整数解中要么等于1,要么等于0。因此从一个
输出最优调度方案
小数解可以分出两支:=1与=0。此时对偶
变量会随之改变,主问题可能已经不是最优,需要图9未缩小解空间的分支定价流程图
再使用列生成改进主问题,&pricewithoutreducingthe
solutionspace
优。
固定=1后主问题可能不可行,有两种情况:
进行分支定价时,,由
(1)真不可解。原因是该变量和其他固定为1
初始解构成松弛限制主问题作为根节点。从根节点
的决策变量发生资源冲突。
出发,首先使用列生成求解本节点得到松弛最优解;
(2)伪不可解。将小数变为1后,由于约束(9)
的存在会影响其他工序决策变量的取值,使其相加
数决策变量进行分支,所得的两个新模型作为两
后不能等于1,从而违反式(8),也可能违反式(10)。
个子节点,
但并不能说明=1不可能存在于最优整数解中,
进行剪支;,
因为当前主问题是不完整的。
直至遍历完整个二叉树。分支定价搜索过程如图8
:.
例如图10所示的算例在进行某步分支时,当可解问题。可行解中应不包含任何松弛变量,因此
前主问题中工序0,1,2,3相关变量的信息如表3需要将其在目标函数中的系数设为一个很大的值。
所列,其中有些变量在之前的分支中已经确定了取对于式(8),松弛变量′在第行的系数为1,其
值为0或1,其余变量取值为主问题取得最优解时余为0;对于式(9),系数均为0;对于式(10),若工
1/(1)pi/(ri1,ri2)
对应的小数值。序处在前序,则系数为0,若处在后序,则系数为
1i
-。如果因确定了其他工序的决策变量为1而导致
0/(0)2/(2)0/(0)R1=2
工序原有的决策变量取值相加小于1,那么′会取
...
02
小数值补上,且一定满足其余约束。
1/(1)
3添加松弛变量是必要的,可以解决模型伪不可
图10某调度问题示例解的问题。我们在实验中发现求解中出现伪不可解
,如果不添加,基本不会对初始解有
表3图10算例主问题中变量取值任何优化。添加松弛变量后,主问题模型如式(14)—
(18)所示:
开始时间,是否在之前的分取值所需资源量min∑(𝑁+1)(𝑁+1)+∑𝑁′(14)
结束时间支中确定了取值=1
010,..
110,∑+′=1,∀∈(15)
210,∑∑𝑡≤,∀∈[0,],∀∈(16)
221,′
∑111−∑222−2≤0,∀(1,2)∈𝑃
232,
3,(17)
31
0≤≤1,0≤′≤1(18)
若该步分支将21确定为1,则和之前分支时已
经确定为1的产生资源冲突,因为0时刻所需在确定了=1后,除了真不可解的情况,模型
11
的资源量之和为3,大于资源总量2,因此=1一定可解,就能使用列生成