基于资源随机中断的反应性多模式项目调度优化

建设企业多项目管理中的资源调度问题研究黄健仓【摘要】随着社会经济及建筑行业的发展,建设企业经常需要同时承担多个大型项目的建设工作,对于多项目管理方法和技术的提升有迫切需求,特别是大型中央企业,常常面临多个项目在海内外地理分布上极为分散的经营生产常态.因此,资源约束下的多项目调度问题也就成为建设企业多项目管理中的核心问题.本文针对于该调度问题开展研究,以最小化项目时间为目标,给出受工期时间约束和资源约束的数学模型,并且借助于自适应遗传算法对该模型求解.另外,本文针对于实际案例进行求解分析,为建设企业大型多项目管理的实际操作提供了技术手段与方法参考,也为后续积极参与国家"一带一路"战略提供了一定的知识储备.【期刊名称】《中国软科学》【年(卷),期】2016(000)001【总页数】8页(P176-183)【关键词】建设企业;多项目管理;资源调度;自适应遗传算法【作者】黄健仓【作者单位】中国科学院大学工程科学学院,北京100049;中交第一航务工程局有限公司,天津300461【正文语种】中文【中图分类】F424.6近几年来，我国建筑行业持续稳步发展，越来越多的建设工程呈现出大型、复杂、群组的“巨项目”新形态，中国各大建筑企业承包的海内外项目的大型化、复杂化、区域群组特性尤为鲜明。

与此同时，国内建设企业的改革正在向施工设计总承包和专业总承包方向发展，逐步实现由现行的劳动力密集型向知识密集型、管理密集型的企业模型转变[1]。

对于有多个在建项目的大型建设企业而言，多项目同时运作是这些企业的特点，特别受“一带一路”战略推动，承建的项目多具备沿交通运输线路或海岸线分部的新特征。

因此建立具有相同地域属性、资源属性、目标属性等多项目管理方法，实施统一控制和管理，提高企业组织管理和合作效率，实现整体效益最优，对大型建筑施工企业在“一带一路”战略新常态下的持续发展具有重要的指导意义[2]。

项目型企业的多项目管理以项目为中心，关注整体项目的顺利完成，这其中包括多项目调度的分析和优化[3]。

第41卷第3期2024年3月控制理论与应用Control Theory&ApplicationsV ol.41No.3Mar.2024基于强化学习的多技能项目调度算法胡振涛1,崔南方1†,胡雪君2,雷晓琪1(1.华中科技大学管理学院,湖北武汉430074;2.湖南大学工商管理学院,湖南长沙410082)摘要:多技能项目调度存在组合爆炸的现象,其问题复杂度远超传统的单技能项目调度,启发式算法和元启发式算法在求解多技能项目调度问题时也各有缺陷.为此,根据项目调度的特点和强化学习的算法逻辑,本文设计了基于强化学习的多技能项目调度算法.首先,将多技能项目调度过程建模为符合马尔科夫性质的序贯决策过程,并依据决策过程设计了双智能体机制.而后,通过状态整合和行动分解,降低了价值函数的学习难度.最后,为进一步提高算法性能,针对资源的多技能特性,设计了技能归并法,显著降低了资源分配算法的时间复杂度.与启发式算法的对比实验显示,本文所设计的强化学习算法求解性能更高,与元启发式算法的对比实验表明,该算法稳定性更强,且求解速度更快.关键词:多技能资源;项目调度;智能算法;强化学习;并行调度引用格式:胡振涛,崔南方,胡雪君,等.基于强化学习的多技能项目调度算法.控制理论与应用,2024,41(3):502–511DOI:10.7641/CTA.2023.20566Reinforcement learning-based algorithm formulti-skill project scheduling problemHU Zhen-tao1,CUI Nan-fang1†,HU Xue-jun2,LEI Xiao-qi1(1.School of Management,Huazhong University of Science and Technology,Wuhan Hubei430074,China;2.Business School,Hunan University,Changsha Hunan410082,China)Abstract:Combinatorial explosion is a common phenomenon in multi-skill project scheduling,which leads to higher complexity in multi-skill project scheduling problem(MSPSP)than in traditional single-skill project scheduling problem. Heuristics and meta-heuristics have disadvantages in solving MSPSP.Therefore,based on the characteristics of project scheduling and the algorithmic logic of reinforcement learning,a multi-skilled project scheduling algorithm based on re-inforcement learning is designed in this paper.Firstly,the multi-skill project scheduling process is modeled as a Markov decision process(MDP).Then,a double-agent mechanism is proposed,and state integration method and action decom-position method are designed to reduce the complexity of value function learning.Finally,skills conflation algorithm is developed to reduce the time complexity of allocating resources in parative experiments between the proposed RL algorithm and heuristics show that the reinforcement learning(RL)has better performance,and experiments between the proposed RL algorithm and meta-heuristics show that the RL has higher stability and shorter running time.Key words:multi-skill resource;project scheduling;intelligence algorithm;reinforcement learning;PSGSCitation:HU Zhentao,CUI Nanfang,HU Xuejun,et al.Reinforcement learning-based algorithm for multi-skill project scheduling problem.Control Theory&Applications,2024,41(3):502–5111引言现代项目中存在着一类多技能资源,如R&D行业的多技能研发人员、工程项目中的多功能作业车等[1].这使得多技能项目调度问题(multi-skilled project sch-eduling problem,MSPSP)[2]成为近年来学者们关注的热点.在项目调度研究领域,资源的指派是最重要的研究内容之一,它不仅能影响项目的工期,还能影响调度计划的鲁棒性[3]、项目产品的质量[4]等.与传统的资源受限项目调度问题(resource constrained pro-ject scheduling problem,RCPSP)相比,MSPSP中资源的多技能特征增加了资源指派的难度,因为在多技能项目调度中,在为活动指派资源的同时,还要为资源收稿日期:2022−06−27;录用日期:2023−06−10.†通信作者.E-mail:***************;Tel.:+86150****7933.本文责任编委:周平.国家自然科学基金项目(71971094,71701067,72071075),湖南省自然科学基金项目(2019JJ50039)资助.Supported by the National Natural Science Foundation of China(71971094,71701067,72071075)and the Natural Science Foundation of Hunan Province(2019JJ50039).第3期胡振涛等:基于强化学习的多技能项目调度算法503指派技能,问题的维度增加,求解难度也更大.MSPSP属于NP难问题[5].作为组合优化问题, MSPSP中活动、技能和资源间可能出现组合爆炸.精确求解算法只能求解规模极小的算例[6].因此更多的研究集中于启发式和元启发式算法.如Almeida等[7–8]和胡振涛等[9]根据多技能资源的特征分别设计了基于静态资源权重和基于动态资源权重的启发式方法. Laszczyk等[10]、Javanmard等[11]和Tabrizi等[12]则设计了遗传算法予以求解,此外禁忌搜索[13]、蚁群算法[14]、差分进化算法[15]等也常被用于求解MSPSP.然而启发式算法往往需要根据项目特征设计规则或参数,导致算法迁移性较差.元启发式算法虽然通用性较强,但在求解大规模项目案例时常需要很长的时间才能求得满意解.此外,由于这些算法涉及的参数较多,加之项目调度问题自身的复杂性,算法的设计和使用常需要较深的专业知识辅助[16].机器学习作为近些年的热点研究对象,被广泛应用于计算机视觉、自然语言处理等领域.强化学习作为机器学习的方法论之一,具有参数少、迁移性强等优点,且在求解组合优化问题方面也有了显著的成果,如围棋游戏问题[17]、车间调度问题[18]、旅行商问题[19]等.而项目调度过程很容易建模为马尔科夫决策过程,这为应用强化学习算法提供了条件.此外,项目调度模型往往是明确的,如工序约束、资源约束和时间约束等,这为强化学习的采样提供了便利.如Sal-lam等[20]针对单技能项目调度问题,考虑了差分进化和布谷鸟算法,并以强化学习作为算法优选技术,在进化过程中从两个算法中选择其一;Sung等[21]针对存在活动反复的单技能项目中的资源分配问题,设计了强化学习算法.此外,Gai等[22]和Mao等[23]也将强化学习算法应用于求解项目调度中的资源分配问题.从现有文献看,项目调度问题应用强化学习的研究主要集中在近几年,且研究成果不多,尤其是针对多技能项目调度问题,尚未发现有深入的研究.基于此,以下第2部分构建了多技能项目调度问题的数学模型;第3部分在介绍强化学习算法和项目调度问题的基础上,针对工期最短的MSPSP设计了基于强化学习的求解算法;第4部分为数值实验及结果分析;第5部分总结了研究内容并提出了下一步的研究方向.2问题建模项目网络采用节点式(AON)表示,共包含n个活动节点,其中起始节点1和终止节点n代表虚活动;活动之间存在工序约束;以G=(V,E)表示项目网络,其中V={1,···,i,j,···n}表示活动集合,E为有向弧,表示活动的工序约束;活动i的工期是为d i,对技能l的需求量为TF il;资源具备多技能,R={1,···,k,···,K}表示资源集合,资源总量为K,RF kl表示资源的技能禀赋,当资源k可执行技能l时RF kl=1,否则RF kl=0;F={1,···,l,···,L}表示技能集合,技能种类为L.在以项目工期最短为目标函数的MSPSP模型中,决策变量有两个,即活动的开始时间S i,以及活动的资源分配x kli,当x kli=1时,表示资源k以技能l的形式被分配到活动i中去.相应的模型如下:min S n,(1)s.t.S i+d i S j,∀j,∀i∈P j,(2) x kli(RF kl−1)=0,∀k,∀l,∀i,(3)∑k∈Rx kli=TF il,∀i,∀l,(4)∑l∈Fx kli 1,∀k,∀i,(5)q ij+q ji 1,∀i,∀j,(6)∑l∈Fx kli+∑l∈Fx klj q ij+q ji+1,∀i,∀j,∀k,(7)S i∈T,q ij∈{0,1},x kli∈{0,1},∀i,∀j,∀k,∀l,(8)其中:式(1)表示目标函数;式(2)表示工序约束,其中P j表示活动j的紧前活动集合;式(3)表示资源只可执行其所掌握的技能;式(4)表示各活动的技能需求必须得到满足,且不会被分配到过多的资源;式(5)表示资源在一个活动中最多只能执行一种技能;式(6)表示两个活动不可互为前序,其中当活动i在活动j开始之前已完工时q ij=1,否则q ij=0;式(7)表示并行的活动不可使用同一资源;式(8)表示决策变量的可行域,T∈{0,1,···,t,···}表示时间点集合.3算法设计采用不同算法求解项目调度问题时,需要根据相应的算法逻辑解构问题,如基于规则的启发式算法需要根据规则解析项目的特征参数,元启发式算法在编码和解码时需要耦合项目的调度过程.以下将结合强化学习的算法逻辑,根据算法思想解构多技能项目调度过程,设计基于强化学习的多技能项目调度算法(reinforcement learning-based parallel scheduling algo-rithm for multi-skill project,RLP).在强化学习(reinforcement learning,RL)中,智能体(Agent)在环境(Environment)中处于不同状态(Sta-te)时,根据不同策略(Policy),尝试各种行动(Action),并被环境回馈以不同的奖励(Reward),一次“状态–行动–获得奖励–新状态–新行动–···”的过程,称为一个回合(Episode).主要过程如图1所示.504控制理论与应用第41卷⣦ 图1强化学习过程Fig.1Process of RL强化学习将问题建模为马尔科夫决策过程(mar-kov decision process,MDP),可用一个四元组表示,即MDP ={State ,Action ,P (a |s ),R (a |s )},元组内分别代表状态空间、行动空间、状态转移概率和回报函数.其中状态指的是智能体每次决策时所处的状态,具体到项目调度问题中,是每次决策时的活动、资源或其他项目要素的状态,状态信息越全面,价值函数便越精确,同时其值空间也越大;行动是智能体每次迭代时所做的决策,在项目调度问题中,背景和目标函数的不同,行动的内容也不同;强化学习的最终目的是通过更新价值函数获得一个最优策略使得整个事件的总回报(Return)最高,这里的回报即是所求解问题的目标函数.价值函数需要考虑的因素有两个:奖励和回报.奖励一般指即时奖励,是在一步行动后所获得的收益.回报一般指长期收益,是完成一个MDP 的收益和后续行动的奖励之和.在项目调度问题中,奖励和回报与目标函数有关,以工期最短为目标,则奖励和回报便和项目工期大小负相关.3.1基于并行调度的MDP 模型项目调度的本质是活动排程和资源分配.并行调度(parallel scheduling generation scheme,PSGS)和串行调度(serial scheduling generation scheme,SSGS)作为两种最常见的项目调度计划生成方式[20],都是通过迭代将项目活动一一加入到调度计划之中,是一种严格的MDP,这为项目调度问题应用强化学习算法提供了条件.引入一个多技能项目案例,项目网络及活动参数如图2(a)所示,资源数量为4,技能数量为3,资源技能矩阵为[010;101;101;100].图2(b)–(f)表示该项目调度过程中的甘特图,坐标系内的方块表示加入调度计划的活动,虚框内的方块表示未加入调度计划的活动.可以看出,该项目的调度过程是一个包含5个状态、4个行动的MDP,其中状态表示当前排程状况,行动表示从未排程活动中选择一个加入调度计划.如图2(b),state1表示当前状态尚未有活动加入排程,action1表示当前选择了活动2加入排程,达到新的状态state2,即图2(c).依照这种方式,直至所有活动加入排程,并达到state5,调度结束.PSGS 随时间迭代[24],在每个决策时点t ,从当前不违背工序及资源约束的活动集V s t 中选择活动加入排程,直至调度完成.用V c t 表示在时点t 已排程的活动,用V u t 表示在时点t 未加入排程的活动,可知V c t ∪V u t =V,V s t ⊆V u t ,∀t.(9)(b) ⭈⢩ 1(a) 亩ⴞ㖁㔌 ⍫ 313233343333333333333333(c) ⭈⢩ 2(d) ⭈⢩ 3(e) ⭈⢩ 4(f) ⭈⢩ 5图2项目调度的MDP 过程Fig.2MDP of project scheduling第3期胡振涛等:基于强化学习的多技能项目调度算法505从PSGS 的角度,项目调度过程是包含n −1个状态和n −2个行动的MDP.在时点t ,其完备的状态空间是V c t 及其内活动和资源的详细排程,即State(t )={{i |i ∈V c t },{S i |i ∈V c t },{R i |R i ={k |x kli =1,l ∈F },i ∈V c t }}.(10)在决策时点t ,行动是从V s t 中选择一个活动加入V c t 并为之分配资源,以R tj 表示在时点t 活动j 的一个可行的资源方案,则时点t 完备的行动空间是为Action(t )={{j |j ∈V s t },{R tj |j ∈V s t }}.(11)在每个回合内,所选活动的开始时间便是当前决策时点,这降低了行动空间的维度,此时的行动空间可以用式(11)的二元组表示.尽管如此,结合式(10)–(11)可以看出,二者仍极易产生组合爆炸.尤其是在MSPSP 中,一个活动往往有很多种可满足其技能需求的资源分配方案,这导致式(11)中{R tj |j ∈V s t }元素过多,使得状态与行动作为组合之后的再组合,其规模将呈现指数级增长.过于庞大的状态和行动空间会导致强化学习算法很难在较短的时间内训练出一个满意的价值函数,为此,设计双智能体机制,以降低多技能项目调度过程中的状态行动空间.3.2双智能体机制由式(11)可知在项目调度的MDP 中,一步行动包含了活动选择和资源分配,为简化行动内容,设计双智能体,见图3.其中Agent1用以指导活动选择,即式(11)二元组的第1项,Agent2指导资源分配,即式(11)二元组的第2项.3333(b)(c)3333图3双智能体机制Fig.3Mechanism of two agents3.2.1Agent1状态及行动定义在学习过程中,需要根据状态State1做出行动Act-ion1.首先分析状态空间State1,针对式(10)三元组的第1项,由式(9)知V c t 和V u t 关于V 互补,以V u t 代替V c t 表示State1不会丢失信息.更进一步地,在V u t 中,当前回合内行动所需要主要的信息是V s t .为了尽可能保留信息,提取已排程活动的个数信息且用V s t 代替已排活动具体内容,式(10)中第1项便转化为{|V c t |,V s t }.针对式(10)三元组的第2项,每次迭代内决策时点t 已为确定值,V c t 内活动的开始时间对当前选择哪个活动加入排程这一行动的影响较小,因此将之省略.针对式(10)三元组的第3项,影响决策最主要的因素是当前剩余资源,用当前剩余资源数量表示.综上,状态空间State1可整合为State1={|V c t |,V s t ,|R at |}.(12)再分析行动空间Action1,Agent1只考虑活动选择,即从V s t 中选择一个活动j 加入排程.其行动空间为Action1={j |j ∈V s t }.(13)可以看出,状态空间State1虽然也是三元组的形式,但是其第1项和第2项都是仅含一个元素的数组,这大大降低了状态空间的规模.而Action1的规模则等于|V s t |,即当前可开始活动的数量.3.2.2Agent2状态及行动定义在学习过程中,需要根据状态State2做出行动Ac-tion2.首先分析状态空间State2,在Agent1根据State1做出Action1后,达到新的状态State2,此时完备的状态需要明确已排活动所用资源及资源的使用时间,而Agent2只负责为Agent1所选活动分配资源,因此对Action2而言,最重要的状态信息是Action1所选择的活动j ,故状态空间State2省略为506控制理论与应用第41卷State2={j }.(14)再分析行动Action2,行动内容是为活动j 分配资源,行动的规模是在当前可用资源约束下,活动j 可行的资源分配方案个数.Action2={R tj }.(15)双智能体机制将调度中的每一步分为两个阶段,用State1和State2表示状态,既能降低状态的规模,也可以最大程度地保留调度过程中的主要信息.此外,Action1和Action2的规模分别等于V s t 内活动的数量和活动j 可行的资源分配方案数量.行动规模为二者之和,而不再是二者之积,这降低了价值函数的维度.以图3为例,当t =2,V c t ={2,4},V u t ={3,5},V s t ={3},则State1={2,{3},1},Action1={3},State2={3},Action2={{R 4}}.3.3价值函数以项目工期最短为目标的MSPSP 属于稀疏回报问题,本文的RLP 算法不考虑即时奖励,使智能体尽可能地搜索全局最优解.以Deadline 表示项目的工期期限,D S 表示当前调度事件S 的工期,最终回报为Reward =Deadline −D S .(16)强化Q 学习算法采用一个表格直观地表示价值函数.本文参考这种形式,针对Agent1和Agent2,设计了表Q aa 和Q ar ,其中Q aa 对应State1,Action1,Q ar 对应State2,Action2,Q 表的格式如图4所示.State1Action1O{0 1 10}{1 2 4 10}{2 3 4 5}2BB 㺘12ĂĂĂState2Action2,{1}{2}{O }12ĂĂĂ2BS 㺘图4Q aa 表与Q ar 表Fig.4Q aa and Q arQ aa 的行数可变,列数为n +1.第1列表示状态State1,第2到n +1列表示Action1.其中State1数组的第1个数值表示该状态下已排程活动数,最后一个数值表示该状态下可使用的资源数,中间数值表示当前可加入排程的活动.在调度过程中会不断产生新的状态State1,这些状态被不重复地列在Q aa 表第1列,因此Q aa 表的行是随着调度事件的产生不断增多的.而无论面临怎样的状态,Action1都是选择一个活动加入排程,即Action1的选择规模为活动数量n ,因此Q aa 表的列包括一个状态列及n 个行动列.Q ar 的行数为n ,列数为K +1.第1列表示状态State2,第2到K +1列表示行动Action2.在调度过程中,State2是Action1所选的活动,规模为项目活动数量n ,因此Q ar 表有n 行.而所选活动所能使用的最大资源数量是项目中的资源总数K ,即Q ar 表包括一个状态列和K 个行动列.3.4算法流程以PSGS 的角度看,以项目工期最短为目标的MSPSP,状态转移概率是已知且等于1的,然而其每一步的行动奖励是非即时且不确定的,即RLP 算法是Model-free 的,需要不断产生调度计划以供智能体采样,更新各状态行动的价值函数,基于此,算法流程包括两部分:调度(采样)过程和学习过程,见图5所示.图5RLP 算法流程Fig.5RLP algorithm flow chart第3期胡振涛等:基于强化学习的多技能项目调度算法507 3.4.1调度过程调度过程以PSGS为框架,随着决策时点t迭代,活动从V st 依次被加入V ct,直至完成调度.RLP采用Off-policy的方式以ε的概率随机选择,以1−ε的概率贪婪选择,其中ε∈[0,1].随机选择时,决策不参考任何经验信息,完全随机地选择活动和资源.贪婪选择时,根据Q表做出决策.其中Action1的贪婪决策过程为:根据当前调度进度,确定State1=state1,根据state1查询Q aa表决定Action1={j}.由于Q aa表中的状态空间初期并不完备,查询Q aa表时可能面临以下两种情况:第1种情况,在Q aa表中可以找到与state1一致的状态,即该状态曾被采样过.此时只需要找到对应行,从该行中选择Q值最大的活动j进入state2即可.第2种情况,在Q aa表中不存在与state1一致的状态,此时统计MDP下一步各个状态的最优价值: v(state1′)=max Q(state1′,action1′).而后根据v(state1′)选择最优价值最大的状态state1′,并将之与当前状态state1对比,选择一个在state1′中已排程而在state1中未排程的活动j作为Action1进入state2即可.采用这种方式的原因是:即便Q aa表中尚未有与state1完全一致的状态,也可以通过将当前状态向最优状态靠近的方式,进行贪婪寻优.Action2则相对简单,由State2={j},查询Q ar表中的第j行,根据当前可用资源R at剔除不可用资源,并根据活动j的技能需求,列出剩余资源的所有组合,从中选择Q值之和最大的资源组合分配给活动j,即可完成Action2进入最终状态state3.3.4.2学习过程RLP的学习过程是智能体不断从调度计划中汲取经验更新价值函数的过程.它以MC-update法作为价值函数更新方式,即在调度计划生成的过程中暂停学习过程,在调度计划生成过程结束后,再根据调度计划的工期更新Q表.首先,分析Agent1,与调度过程相似,在更新Q值时可能面临以下两种情况:第1种情况,在表中可以找到与state1一致的状态,此时直接更新对应Q值:Q aa(state1,action1)←Q aa(state1,action1)+ (1/N visit)·(Reward−Q aa(state1,action1)),(17)其中N visit是当前访问Q表中Q aa(state1,action1)位置的次数,Reward可根据式(16)获得.第2种情况,找不到与state1一致的状态,则增加Q aa表的长度,将state1及以下Q值直接加入表中: Q aa(state1,action1)←Reward.(18) Agent2的Q表是完备的,在表中一定能找到与sta-te2完全一致的状态,其更新方式为Q ar(state2,action2)←Q ar(state2,action2)+ (1/N visit)·(Reward−Q ar(state2,action2)).(19) 3.5算法优化3.5.1调度过程优化在MSPSP中,根据当前可用资源求解可开始活动集V st是一个难点,在单技能RCPSP,只需要对比资源需求数量和资源供给数量即可,而在MSPSP中,即便资源数量足够,活动也不一定可以开始.该问题可描述为:如何判断当前可用资源R at能否满足活动集V st 内所有活动的技能需求.整理V st的技能需求,对其内活动的技能需求求和,用TF stl表示V st内活动对技能l的需求量,则TF stl=∑i∈V stTF il,∀l.(20)整理资源的技能供给,由于在同一时刻每个资源只能被使用一次,尽管资源具备多技能,这些技能也是互斥的,因此有以下约束:x kli∈{0,1},∀k∈R a t,∀i∈V s t,∀l,(21)∑i∈V st∑l∈Fx kli 1,∀k∈R a t,∀l.(22)V st内活动在当前时点t可以同时开始的充要条件是:R at中资源的技能供给不少于V st的技能需求,即∑k∈R at∑i∈V stx kli TF s tl,∀l∈F.(23)因此以x kli为未知数,只需判断方程组(20)–(23)是否有解,即可判断V st是否可行.然而该方程组是0–1型线性整数规划问题,属于NP难问题.对此本文提出技能归并法,算法伪代码见表1.表1算法1:技能归并法Table1Algorithm1:Skills conflation algorithm输入:V s t,TF s tl,R a t,RF输出:Feasb,在当前资源约束下V s t可行时=11Feasb←1;2for z=1→L do3SkillComb z←从{1,2,···,L}中选出z个技能的所有组合;4for h=1→C z L do5Fs h←SkillComb z中的第h个技能组合;6supply←|{k|k∈R a t,∑l∈Fs hRF kl=0}|;7demand←∑i∈V s t∑l∈Fs hTF il;8if supply<demand then9Feasb←0;return10end if11end for12end for13return Feasb508控制理论与应用第41卷算法第3行列出了要归并的z 个技能的所有组合,第4–11行检验归并后的技能能否被当前资源满足,以supply 和demand 表示技能归并后的资源供给和活动需求.在过程中一旦出现供给不足则跳出所有循环,Feasb =0.若能通过所有组合的检验,则V s t 可行,Feasb =1.技能归并法的合理性来源于以下命题:命题若归并任意数量任意组合的技能后,R at 对所归并技能的供给数量,都不少于V s t 对所归并技能的需求数量,则至少存在一个资源分配方案,使得V s t 内的所有技能需求能被R at 满足.命题1Z 若对V s t ,资源R at 不存在可行的分配方案,则至少存在一个归并的技能组合,使得R at 对所归并技能的供给数量少于V s t 对所归并技能的需求数量,即使得supply <demand .可以看出命题1Z 为命题1的逆否命题,以下证明命题1Z.证资源R at 不满足V s t 有以下3种情况.第1种情况是,资源的总数量不足,即|R at |<∑i ∈V s t ∑l ∈FTF il .(24)式(24)不等号左侧为可用资源总量,它等于归并所有技能(即z =L )为一个技能后,资源对所归并技能的供给supply .同理,不等号右侧等于归并L 个技能后,活动对所归并技能的需求demand .因此式(24)等价于supply <demand ,符合命题1Z.第2种情况,资源总量足够,但是在某一个或几个技能上的数量不足,即∃l ∈F,∑k ∈R a tRF kl <∑i ∈V st TF il .(25)式(25)不等号左侧等于归并单个技能(即z =1)为一个技能后,资源对所归并技能的供给supply .同理,不等号右侧等于归并单个技能后活动的需求demand .因此式(25)等价于supply <demand ,符合命题1Z.第3种情况,可用资源总量足够,在每个技能上的资源量也足够,但是不存在可行的资源分配方案使所有技能需求被同时满足.出现这种情况的原因是资源技能的排他性,即一个资源虽然同时具备多项技能,但同一个时刻它只能执行一个技能.此时V s t 不可行的原因是技能之间存在抢夺资源的情况.分析两个技能l 和m 间抢夺资源的情况.首先,从R a t 中选出具备技能l 而不具备技能m 的资源R alt,具备技能m 而不具备技能l 的资源R amt,以及同时具备二者的资源R almt.将R al t 全部分配给技能l 的需求,将R am t 全部分配给技能m 的需求,技能l 和m 的需求至少仍有一个未得到满足,且剩余可分配的资源R almt无论如何分配,都不能使二者被同时满足,即两个技能需求的差额之和,大于R almt 的数量,即∑i ∈V st TF il −|R al t |+∑i ∈V st TF im −|R am t |>|R almt |,等价于|R al t |+|R am t |+|R alm t |<∑i ∈V st TF il +∑i ∈V st TF im .(26)式(26)不等号左侧等于归并l 和m 为一个技能,资源对所归并技能的供给supply .不等号右侧等于归并l 和m 后活动的需求demand .因此式(26)等价于supply <demand ,符合命题1Z.类似地,当出现两个以上的技能抢夺资源时,可推导出同样的结论.综合以上3种情况和式(24)–(26),命题1Z 得证,作为其逆否命题,命题1得证.证毕.由算法流程可知,技能归并法的时间复杂度为O(L ∑z =1C zL)=O(2L ).针对这一问题,文献[7–8]和文献[9]分别采用了最小费用最大流和二分图最大匹配法予以求解.在这两种方法中,该问题所对应的顶点包含活动的技能需求顶点和资源的技能供给顶点,顶点数量N =∑i ∈V s t ∑l ∈FTF il +|R at |,文献中Dijkstra 算法的时间复杂度为O(N 2),Hungarian 算法的时间复杂度为O(N 3).针对一个项目而言,技能种类L 是一定的,且往往不会太多,如文献[7–9]的项目算例库中最多技能种类为L =4.而在调度过程中,活动需求和资源供给往往是较多的,文献[7–9]中最多资源数量为25.对比可知,当面临技能种类较少的项目时,技能归并法的时间复杂度远小于其他算法.3.5.2学习过程优化针对Agent1,在每次迭代时,它需要根据当前访问次数更新Q 值,为此,设计了辅助表M aa ,其规模与Q aa 表相同,M aa (state1,action1)中数值的含义是:当前访问Q aa (state1,action1)位置的次数N visit .同样地,针对Agent2,设计了辅助表M ar ,其大小与Q ar 表相同,M ar (state2,action2)值的含义是:当前访问Q ar (state2,action2)位置的次数N visit .4实验与分析4.1实验设计为验证RLP 算法,设计了单项目算例实验和项目算例集实验.相关程序用Matlab R2017a 编写,测试平台为Windows 10操作系统,处理器为Intel(R)Core (T M)i7-6700CPU @3.40GHz.4.1.1单项目算例实验设计在实验对象方面,采用如下项目案例.图6是一个包含30个实活动的项目,拥有10个多技能资源,4项技能,其网络图及活动信息标注在图中,资源技能矩阵。

模糊多目标资源受限项目调度问题的优化方法
刘士新;宋健海
【期刊名称】《系统工程学报》
【年(卷),期】2008(23)6
【摘要】设计了一种求解模糊多目标资源受限项目调度问题的遗传局域搜索(GLS)算法,目标是生成近似有效解集以便决策者在决策过程中有更多的选择.算法利用线性加权效用函数将多目标组合优化问题转换为单目标组合优化问题,通过系统的方法生成目标权系数向量,对于每次生成的权系数向量,调用GLS算法求解以极小化效用函数为单一目标的子问题,由此生成的近似有效解集更加具有多样性.实验结果表明:本文算法可以针对多目标资源受限项目调度问题生成较好质量的近似有效解集,在多数指标上优于其它两种对照算法.
【总页数】7页(P744-750)
【作者】刘士新;宋健海
【作者单位】东北大学信息科学与工程学院,流程工业综合自动化教育部重点实验室,辽宁,沈阳,110004;上海宝信软件股份有限公司,MES事业部,上海,201900【正文语种】中文
【中图分类】C934
【相关文献】
1.基于混沌差分进化粒子群算法的模糊资源受限项目调度问题 [J], 何立华;马芳丽
2.多模式资源受限项目调度问题的优化方法 [J], 贾艳;李晋航;张跃刚;郑义
3.求解模糊资源受限项目调度问题的遗传算法 [J], 王宏;林丹;李敏强
4.基于双种群蚁群算法的多目标资源受限项目调度问题研究 [J], 宋红星;曹文彬
5.资源受限工程调度问题的优化方法综述 [J], 刘士新;王梦光;唐加福
因版权原因，仅展示原文概要，查看原文内容请购买。

云计算中的网络资源调度与优化随着云计算技术的不断发展和普及，越来越多的企业和个人开始将自己的业务和数据迁移到云平台上。

云计算作为一种基于网络的计算模式，可以为用户提供弹性的计算、存储和网络资源。

在云计算环境中，网络资源调度与优化是实现高效、可靠和安全云计算的关键。

一、网络资源调度的意义与挑战云计算中的网络资源调度是指根据用户需求和系统优化策略，将网络流量和计算任务合理分配给云平台中的各个节点，以实现资源的高效利用和性能的最优化。

网络资源调度的意义在于：1. 提高资源利用率：通过合理安排网络资源的调度，可以充分利用云平台中的计算、存储和网络资源，减少资源的浪费，提高资源的使用效率。

2. 保证服务质量：通过有效的网络资源调度，可以确保云平台用户的网络连接稳定、延迟低，从而保证用户的业务正常运行。

然而，网络资源调度也面临着一些挑战：1. 大规模的网络拓扑：云平台通常由大量的网络节点和关联的网络设备组成，网络规模庞大，调度算法需要考虑到网络的复杂性和拓扑结构。

2. 异构的资源分布：在云平台中，不同节点上的计算、存储和网络资源可能具有不同的性能和特点，调度算法需要根据需求和资源状况进行合理分配。

3. 多维度的资源需求：云平台用户的需求可能涉及到计算资源、内存、带宽等多个维度，调度算法需要考虑各个维度的需求，并进行综合优化。

二、网络资源调度的关键技术为了实现网络资源的高效调度和优化，云计算中存在多种关键技术。

1. 资源调度算法资源调度算法是网络资源调度的核心，其目标是根据用户需求和系统优化策略，合理分配资源，最大化满足用户需求的同时实现资源的高效利用和平衡负载。

常用的资源调度算法包括最佳适应算法、贪心算法、遗传算法等。

2. 路由策略路由策略是网络资源调度的重要组成部分，它决定了网络包从源节点到目标节点的路径选择。

通过合理的路由策略，可以降低网络拥塞、减少延迟，提高网络性能。

3. 动态负载均衡动态负载均衡是一种通过实时监测网络状况和资源利用情况，在不同节点上动态调整资源分配的策略。

云计算平台中的资源预测与调度优化方法研究云计算平台作为一种新的计算模式，已经在各个行业中得到广泛应用。

在这种模式下，计算资源可以按需分配和实时扩展，极大地提高了计算效率和资源利用率。

资源预测和调度优化是云计算平台领域的重要问题，对于提高资源利用率、降低能耗和提升用户体验具有重要意义。

资源预测是指根据历史数据和未来的需求预测，提前分配和调度计算资源，从而达到系统性能的优化。

资源预测的准确性对于云计算平台的性能至关重要。

准确的资源预测可以提前分配资源，避免资源闲置和资源短缺的问题，提高资源利用率。

资源预测方法主要包括基于统计的方法和基于机器学习的方法。

基于统计的资源预测方法是一种常见且有效的方法。

它通过对历史数据的分析和统计，构建预测模型。

其中，时间序列模型是一种常用的方法。

时间序列模型可以分析和预测数据中的趋势和周期性波动，如ARIMA模型、指数平滑模型等。

此外，统计回归模型和相关分析模型也常被用于资源预测。

这些方法通常需要大量的历史数据，并假设未来的需求与过去的需求有一定的关系。

由于云计算平台的需求变化较为复杂和不确定，基于统计的方法在预测准确度上存在一定的局限性。

基于机器学习的资源预测方法是近年来发展起来的一种新方法。

机器学习方法可以通过对大量的历史数据进行训练，自动学习和发现资源需求的规律和模式，并进行预测。

常用的机器学习方法包括支持向量机、随机森林、神经网络等。

这些方法能够处理非线性关系和高维数据，并且克服了基于统计方法在面对复杂和不确定数据中的缺点。

机器学习方法在资源预测领域取得了较好的效果，并且不断有新的方法和算法被提出。

资源调度优化是指在资源预测的基础上，通过合理的调度算法和策略，使得资源的分配和利用更加高效和灵活。

资源调度优化可以进一步提高云计算平台的性能和资源利用率。

资源调度优化方法主要包括静态调度和动态调度。

静态调度是指在任务提交前，根据任务属性和系统状况，通过合理的算法进行资源的分配和调度。

资源不确定环境下模具多项目预测-反应式调度算法张沙清;陈新度;陈庆新;陈新【摘要】针对模具多项目执行过程中由于可再生资源发生故障而导致的调度计划变更问题,提出了一种预测-反应式调度算法.利用生灭过程理论对可再生资源的不确定性进行分析,通过大量基于启发式策略的仿真计算构建了一个相对稳定的基准调度计划,建立了以调度计划变更费用最小为优化目标的反应调度模型,并用混沌微粒群优化算法进行求解.通过仿真计算分析了所提算法的可行性与有效性.【期刊名称】《计算机集成制造系统》【年(卷),期】2010(016)012【总页数】9页(P2688-2696)【关键词】资源不确定;生灭过程;模具;多项目调度;预测-反应式调度;混沌微粒群优化算法【作者】张沙清;陈新度;陈庆新;陈新【作者单位】广东工业大学机电工程学院,广东,广州,510006;广东工业大学管理学院,广东,广州,510520;广东工业大学机电工程学院,广东,广州,510006;广东工业大学机电工程学院,广东,广州,510006;广东工业大学机电工程学院,广东,广州,510006【正文语种】中文【中图分类】TH1660 引言资源受限的项目调度问题(Resource Constrained Project Scheduling Problem,RCPSP)是项目管理的重要研究方向之一,前人对此问题已经做了大量卓有成效的研究。

然而,在项目执行过程中,由于不确定的客观因素的影响,往往造成原有的调度计划无法继续执行,需要制定新的调度计划。

总体上看,专门研究风险性和不确定环境下项目调度理论与方法的文献较少。

对现有文献进行初步归类,可以大致分为两大类:¹将项目网络图的结构假设为确定性,而将项目中的其他参数,如任务工期等作为不确定性变量、对项目调度方案的制订开展研究,文献[1]全面地叙述了这类研究工作,主要存在反应性调度、随机性调度、模糊调度和前摄鲁棒性调度四类不同的调度方法;④将项目网络图的结构也假设为随机性,研究项目调度计划与控制方法,文献[2]和文献[3]介绍了这类研究工作,主要包括单机、同等并联多机、带有紧前约束的Job-Shop和Flow-Shop以及图示评审技术(Graphical Evaluation and Review Technique,GERT)网络的研究情况。

带有活动重叠的多模式资源受限项目调度问题初梓豪;徐哲;于静【摘要】为了缩短项目工期、优化资源利用效率,研究了带有活动重叠的多模式资源受限项目调度问题,构建了活动重叠-返工时间因子矩阵,对多模式下的活动重叠和返工时间进行了完整的数学描述,以最小化项目工期为目标,建立了带有活动重叠的多模式项目调度优化模型;设计了改进的遗传算法并对问题进行求解,在经典的双链编码遗传算法的基础上,设计对初始种群活动链的预处理阶段以加速算法的求解效率,并针对多模式活动重叠问题设计了专门的解码方法.通过实验研究验证了该算法较其他方法具有更好的求解能力和表现,以一个小规模算例演示了模型在处理工期缩短问题上的有效性.通过全因子实验设计分析了问题参数对缩短项目工期的影响,为项目管理者确定项目调度方案提供了决策依据.%To reduce the project time and optimize the resource utilization,the multi-mode resource-constrained project scheduling problem with activity overlapping was proposed.The overlap and rework activity time factor matrix was designed to describe the relations between overlap and rework,and the multi-mode resource-constrained project scheduling optimization model with activity overlapping was proposed whose objective was to minimize the project's duration.A revised genetic algorithm based on specific schedule generation mechanism was presented to solve the model.Based on the classic double list encoding genetic algorithm,a preprocessing stage of the activity list was designed to improve its efficiency.The model and algorithm were demonstrated by using an example project andcomparative experiments.The duration of project was tested and analyzed through full factorial design,which provided basis for decision makers.【期刊名称】《计算机集成制造系统》【年(卷),期】2017(023)003【总页数】10页(P557-566)【关键词】项目调度;资源受限;多模式;活动重叠;遗传算法【作者】初梓豪;徐哲;于静【作者单位】北京航空航天大学经济管理学院,北京100191;北京航空航天大学经济管理学院,北京100191;天津理工大学管理学院,天津300383【正文语种】中文【中图分类】N945资源受限项目调度问题(Resources Constrained Project Scheduling Problem, RCPSP)研究的是通过优化项目目标获取一个满足活动优先关系和有限资源约束的基线进度计划[1]。