第３０卷　第２期运　筹　与　管　理
Ｖｏｌ．３０，Ｎｏ．２
２０２１年２月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥ
Ｆｅｂ．２０２１
收稿日期：２０１９ ０４ １０
基金项目：西南石油大学青年教师“过学术关”基金资助项目（２０１８９９０１０１４５）；西南石油大学科研启航计划项目（２０１８ＱＨＲ００４）；西南石油大学人文专项基金（
２０１８ＲＷ００５）；国家自然科学基金（７１８７１１７６）作者简介：宁敏静（１９８５ ），女，河南新乡人，讲师，博士，研究方向为项目管理及优化；郑小强（１９８１ ），男，副教授，博士，研究方向为能源替代行为决策；何正文（
１９６７ ），男，山西运城人，教授，博士，研究方向为项目管理及优化。基于随机活动工期的现金流动态均衡前摄性
与反应性项目调度优化
宁敏静１，　郑小强１，　何正文２
（１．西南石油大学经济管理学院，四川成都６３７００１；２．西安交通大学管理学院，陕西西安７１００４９）
摘　要：承包商的现金流动态均衡对不确定条件下项目的顺利实施有重要影响。作者研究基于随机活动工期的现
金流动态均衡前摄性及反应性项目调度问题，目标是在随机活动工期条件下，为承包商生成现金流均衡基准进度，并根据执行过程中的实际情况，动态地对其进行反应性调整。首先，通过建立前摄性调度优化模型生成基准进度，并提出两个反应性调度策略对其进行调整。其次，为以上诸模型的求解设计了模拟退火和禁忌搜索相结合的混合算法ｔａｂｕ ＳＡ。最后，针对前摄性调度模型，在随机生成的算例集合上对算法进行测试，并进行大规模仿真实验。研究结果可以为随机活动工期下承包商保持现金流动态均衡、确保项目顺利实施，提供定量化决策支持。关键词：现金流均衡项目调度；前摄性；反应性；禁忌搜索和模拟退火嵌套算法；随机活动工期中图分类号：Ｃ９３５；Ｆ２２４　文章标识码：Ａ　文章编号：１００７ ３２２１（２０２１）０２ ０１１７ ０７　ｄｏｉ：１０．１２００５／ｏｒｍｓ．２０２１．００５０
ＰｒｏａｃｔｉｖｅａｎｄＲｅａｃｔｉｖｅＣａｓｈＦｌｏｗＤｙｎａｍｉｃａｌｌｙＢａｌａｎｃ
ｅｄＰｒｏｊｅｃｔ
ＳｃｈｅｄｕｌｉｎｇＯｐｔｉｍｉｚａｔｉｏｎＢａｓｅｄｏｎＲａｎｄｏｍＡｃｔｉｖｉｔｉｅｓＤｕｒａｔｉｏｎｓ
ＮＩＮＧＭｉｎ ｊｉｎｇ１，ＺＨＥＮＧＸｉａｏ ｑｉａｎｇ，ＨＥＺｈｅｎｇ ｗｅｎ
２
（１．ＳｃｈｏｏｌｏｆＥｃｏｎｏｍｉｃｓａｎｄＭａｎａｇｅｍｅｎｔ，ＳｏｕｔｈｗｅｓｔＰｅｔｒｏｌｅｕｍＵｎｉｖｅｒｓｉｔｙ，Ｃｈｅｎｇｄｕ６３７００１，Ｃｈｉｎａ；２．ＳｃｈｏｏｌｏｆＭａｎａｇｅｍｅｎｔ，Ｘｉ’ａｎＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ７１００４９，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｉｔｉｓｉｍｐｏｒｔａｎｔｔｏｉｍｐｌｅｍｅｎｔｐｒｏｊｅｃｔｓｓｕｃｃｅｓｓｆｕｌｌｙａｎｄｓｍｏｏｔｈｌｙ，ｔｈｅｃｏｎｔｒａｃｔｏｒｓ’ｃａｓｈｆｌｏｗｏｆｗｈｉｃｈｉｓｂａｌａｎｃｅｄｉｎｕｎｃｅｒｔａｉｎｃｉｒｃｕｍｓｔａｎｃｅｓ．Ｔｈｅａｕｔｈｏｒｓｓｔｕｄｙｐｒｏａｃｔｉｖｅａｎｄｒｅａｃｔｉｖｅｃａｓｈｆｌｏｗｂａｌａｎｃｅｄｐｒｏｊｅｃｔｓｃｈｅｄｕ ｌｉｎｇｐｒｏｂｌｅｍｂａｓｅｄｏｎｒａｎｄｏｍｄｕｒａｔｉｏｎ
ｏｆａｃｔｉｖｉｔｉｅｓ．Ｔｈｅｐｕｒｐｏｓｅｏｆｔｈｉｓｐａｐｅｒｉｓｔｏｇｅｎｅｒａｔｅａｂａｓｅｌｉｎｅｓｃｈｅｄｕｌｅｆｏｒｔｈｅｃｏｎｔｒａｃｔｏｒａｎｄｔｏａｄｊｕｓｔｉｔｄｙｎａｍｉｃａｌｌｙｄｕｒｉｎｇｔｈｅｐｒｏｊｅｃｔｅｘｅｃｕｔｉｎｇｐｒｏｃｅｓｓ．Ｔｈｅｐｒｏａｃｔｉｖｅｓｃｈｅｄｕｌｉｎｇｏｐｔｉｍｉｚａｔｉｏｎｍｏｄｅｌｉｓｃｏｎｓｔｒｕｃｔｅｄａｎｄｔｈｅｎｔｈｅａｕｔｈｏｒｓｐｒｏｖｉｄｅｔｗｏｒｅａｃｔｉｖｅｏｐｔｉｍｉｚａｔｉｏｎｍｏｄｅｌｓｔｏａｄｊｕｓｔｔｈｅｂａｓｅｌｉｎｅｓｃｈｅｄｕｌｅ．Ｆｕｒｔｈｅｒ，ａｈｙｂｒｉｄａｌｇｏｒｉｔｈｍ，ｔａｂｕ ＳＡ，ｉｓｄｅｖｅｌｏｐｅｄｔｏｓｏｌｖｅｔｈｅｓｔｕｄｉｅｄｐｒｏｂｌｅｍ．Ｕｌｔｉｍａｔｅｌｙ，ｆｏｒｔｈｅｐｒｏａｃｔｉｖｅｓｃｈｅｄｕｌｉｎｇｍｏｄｅｌ，ｅｘｐｅｒｉｍｅｎｔｉｓｃｏｎｄｕｃｔｅｄｏｎｔｈｅｓｔａｎｄａｒｄｐｒｏｊｅｃｔｉｎｓｔａｎｃｅｓｓｅｔａｎｄｆｕｒｔｈｅｒｌａｒｇｅｓｃａｌｅｒｅａｃｔｉｖｅｓｉｍｕｌａｔｉｏｎｓａｒｅｐｅｒｆｏｒｍｅｄｏｎｅａｃｈｉｎｓｔａｎｃｅ．Ｔｈｅｒｅｓｅａｒｃｈｃｏｕｌｄｐｒｏｖｉｄｅｄｅｃｉｓｉｏｎｓｕｐｐｏｒｔｓｆｏｒｔｈｅｃｏｎｔｒａｃｔｏｒｓｔｏｅｎｓｕｒｅｃａｓｈｆｌｏｗｔｏｂｅｂａｌａｎｃｅｄｉｎｔｈｅｅｎｖｉｒｏｎｍｅｎｔｓｗｉｔｈｒａｎｄｏｍａｃｔｉｖｉｔｉｅｓｄｕｒａｔｉｏｎ．Ｋｅｙｗｏｒｄｓ：ｃａｓｈｆｌｏｗｂａｌａｎｃｅｐｒｏｊｅｃｔｓｃｈｅｄｕｌｉｎｇ；ｐｒｏａｃｔｉｖｅ；ｒｅａｃｔｉｖｅ；ｔａｂｕ ＳＡ；ｒａｎｄｏｍａｃｔｉｖｉｔｙｄｕｒａｔｉｏｎ
０　引言
在实际的项目管理中，管理者经常会遇到资金短缺的情况，导致项目拖期、甚至是资金链断裂进
而导致项目失败［１，２］。现实中因资金链断裂导致
项目失败的案例时有出现，例如“巨人大厦”项目
因资金链断裂，最终导致烂尾等。大型项目工期长且面临高度不确定性，活动工期波动、资源配置等都会对项目进度计划形成干扰，进而影响项目的现金流。因此，本文研究基于随机活动工期的现金流动态均衡项目调度问题，旨在为项目承包商安排一
个合理的调度计划，合理使用业主的支付以弥补资金缺口，确保项目的顺利实施。本文的研究可以为随机活动工期下承包商保持现金流入与流出的动态均衡，提供定量化决策支持，具有重要的现实意义。
前摄性及反应性项目调度是处理不确定扰动的常用调度方法［３］。ＶａｎｄｅＶｏｎｄｅｒ等［４］列举了多个插入时间缓冲的方法，发现开始时间关键度法由于关注活动权重及其变化性特征，因而效果最好。Ｌａｍｂｒｅｃｈｔｓ等［５］研究了资源可用量不确定时生成基准进度的方法。Ｂｒｕｎｉ等［６］通过一种可调整的鲁棒优化模型进行资源分配，以最小化最坏情形下的项目工期。寿涌毅和王伟［７］构建了工期不确定的资源受限项目调度的鲁棒优化数学模型，求解结果具有较强鲁棒性。张静文等［８］对关键链方法中的二次资源冲突困境进行了有效研究。马咏等［９］研究了柔性资源约束下的前摄性调度问题，通过资源柔性增加进度鲁棒性。
关于反应性调度，ＶａｎｄｅＶｏｎｄｅｒ等［１０］针对多个活动发生中断的情况提出新的反应性调度算法，以最小化进度偏差。Ｙａｎｇ和Ｇｅｕｎｅｓ［１１］研究了潜在活动是否发生情况未知时的反应性调度问题，目标是最小化拖期费用的权重和。Ｄｅｂｌａｅｒｅ等［１２］研究多模式资源约束反应性调度，开发精确算法和启发式算法进行求解。张沙清等［１３］针对任务拖期而导致的调度计划变更，提出资源流约束的反应调度算法。王艳婷等［１４］研究了比较两种资源分配方式与三类反应性调度策略组合而成的六种反应性策略。崔晓等［１５］研究了考虑信息处理成本的反应性调度问题，以确定最优的信息处理投入。
基于上述观点，本文亦采用前摄性及反应性调度方法进行研究。在本文的后续部分，首先构建问题优化模型，构建前摄性调度模型，为承包商生成一个现金流均衡的基准进度，再提出两个反应性调度模型，对不确定扰动进行调整；接着设计求解算法；然后用大量算例对算法进行验证并进行反应性仿真实验；最后总结全文。
１　问题界定及优化模型
本文采用ＡｏＮ（Ａｃｔｉｖｉｔｙ ｏｎ Ｎｏｄｅ）网络表示项目活动之间的逻辑关系。各活动工期为服从一定均值分布的随机变量，活动执行时产生一定的费用，完成后获得相应挣值。合同总价款为所有活动的挣值之和。要求项目必须在计划截止时间之前完成。项目采用里程碑支付方式，每次支付量基于承包商获得的累计挣值按支付比例计算，业主须在最后一次支付时付清全部剩余合同价款。
活动工期的随机性特征可能会对项目造成干扰，因此，在制定基准进度时应该考虑计划的稳定性。为了确保进度计划在执行过程中的稳定性，要求计划的鲁棒性不得低于一个设定的阈值，该值通过对活动工期随机分布的估计，结合项目总时间裕量，由项目管理者权衡决定。由此，前摄性调度模型可以界定为：在截止日期及鲁棒性阈值约束下，合理地安排活动开始时间，以实现承包商现金流均衡。
在项目实际执行过程中，各活动工期按照逻辑关系，依次变成确定值。若活动工期波动剧烈，则基准进度很可能发生中断。每次中断发生时，反应性调度模型被调用，以重新生成可行的基准进度，因此，反应性调度其实是一个多阶段决策过程。每个中断点的调度策略有两种：策略１（最小扰动策略）和策略２（现金流均衡策略）。
为了表述方便，表１总结了模型中用到的所有符号的含义。
表１　符号定义表
符号符号含义
相关参数ｉ表示活动ｉ，ｉ＝０，１，…，Ｎ＋１，其中活动０和Ｎ＋１分别是虚开始活动和虚结束活动μ（ｄｉ）活动ｉ的工期的均值
σ（ｄｉ）活动ｉ的工期的标准差
ｃｖ（ｄ
ｉ
）活动ｉ的工期的离散系数
ｃ
ｉ
活动ｉ的费用
πｉ活动ｉ完成后获得的挣值
Ｕ项目的合同总价款
Ｄ项目的截止时间
Ｒｏｂｕ 项目进度计划的鲁棒性阈值
θ支付比例
ｉｋ支付活动，ｉｋ＝１，２…，ｉＫ
ξｉ活动ｉ的权重系数，等于活动工期的标准差占所有的活动工期标准差之和的比重，即ξ
ｉ＝σ（ｄ
ｉ
）／∑
Ｎ＋１
ｉ＝０
σ（ｄｉ）
８
１
１运　筹　与　管　理          　２０２１年第３０卷
ＳＵＣＣｉ活动ｉ的所有紧后活动的集合，ｉ＝０，１，…，Ｎ
ＢｉＢｉ＝ｍｉｎｊ∈ＳＵＣＣｉｓｂｊ
－ｓｂｉ－μ（ｄｉ），ｉ＝０，１，…，Ｎ；ＢＮ＋１＝Ｄ－ｓｂ
Ｎ＋１ｐｋ第ｋ次支付的支付量，ｐｋ＝θ
·∑ｉ∈
ＰＡｋ
πｉ，ｋ＝１，２，…，Ｋ－１；ｐＫ＝Ｕ－∑Ｋ－１
ｋ＝１ｐｋ
ＰＡｋ第ｋ－１次支付至第ｋ次支付之间已完成的活动集合，ＰＡｋ＝｛ｉ：ｓｂｉｋ－１＋μ（ｄｉｉ－１）＜ｓｂｉ＋μ（ｄｉ） ｓｂ
ｉｋ＋μ（ｄｉ
ｋ）｝ＦＡｔｔ时刻已经开始的活动集合，ＦＡｔ＝｛ｉ：ｓｂ
ｉ＋μ（ｄｉ
） ｔ｝，ｔ＝０，１，２，…，ＤＦＰｔｔ时刻已完成的里程碑活动集合，ＦＰｔ＝｛ｉｋ：ｓｂ
ｉｋ＋μ（ｄｉ
ｋ） ｔ｝Ｇｔｔ时刻项目的累计资金缺口，Ｇｔ＝∑ｉ∈ＦＡｋｃｉ－∑ｉｋ∈ＦＰｔ
ｐｋ
，ｔ＝０，１，２，…，ＤＧｍａｘ项目实施过程中的最大累计现金流缺口，Ｇｍａｘ＝ｍａｘｔ＝０，１，…，Ｄ｛Ｇｔ
｝Ｔ
中断发生的时刻Ｆ
Ｔ
reactive和proactive的区别
Ｔ时刻已经完成的活动集合Ｐ
Ｔ
Ｔ时刻正在进行的活动集合ＵＴ
Ｔ时刻尚未开始的活动集合
ｄＴｉ
Ｔ时刻活动ｉ的工期ｗｉ活动ｉ的不稳定性权重系数
Ｌｏｓｓ
Ｔ
中断发生时项目进行调整所引起的损失值
决策变量
ｓｂｉ前摄性调度模型中活动的计划开始时间，非负整数，ｉ＝０，１，…，Ｎ＋１ｓＴｉ
反应性调度模型中活动的实际开始时间，非负整数，ｉ＝０，１，…，Ｎ＋１
１．１　前摄性调度模型
根据上述对问题的界定，基于随机活动工期的现金流均衡项目调度问题的前摄性调度模型可构建如下。这里，活动工期采用其随机分布的均值μ（ｄｉ）。ｍｉｎＧｍａｘ＝ｍａｘｔ＝０，１，…，Ｄ｛∑ｉ∈ＦＡｔ
ｃ
ｉ－∑ｉｋ∈ＦＰｔ
ｐｋ｝（１）ｓ．ｔ．ｓｂ
ｉ＝
０（２）ｓｂｉ＋μ（ｄｉ） ｓｂ
ｊ，（ｉ，ｊ）∈Ａ（３）ｓｂＮ＋１ Ｄ（４）∑Ｎ＋１
ｉ＝０
（ξｉＢｉ） Ｒｏｂｕ
（５）
ｐｋ＝θ∑ｉ∈ＰＡｋ
πｉ，
ｋ＝１，２，…，Ｋ－１ｐＫ＝Ｕ－∑ｋ－１
ｋ＝１
ｐ{
ｋ
（６）ｓｂ
ｉ为非负整数ｉ
＝０，１，…，Ｎ＋１（７）
以上模型中，目标要求式（１）最小化项目承包商的最大累计现金缺口Ｇｍａｘ；约束条件式（２）定义项目的开始时刻；式（３）为网络优先关系约束；式（
４）为项目工期约束；式（５）为鲁棒性阈值约束；式（６）计算每次的支付量；式（７）是决策变量的定义域约束。注意，若Ｒｏｂｕ
设置得过高，会造成模型无解；过低则不能起到保证基准进度稳定性的作用，因此，项目管理者必须审慎地权衡，以确保进度计划的可行性和稳定性。１．２　反应性调度模型
根据前摄性调度模型生成的现金流动态均衡基准进度，可建立基于两种策略的反应性调度模型分别如下。
１）最小扰动策略
  ｍｉｎＬｏｓｓＴ＝∑ｉ∈ＵＴ
ｗｉ
（ｓＴｉ－ｓｂ
ｉ）（８）
  ｓ．ｔ．ｓＴｉ＝ｓｂｉ
，
ｉ∈ＦＴＵＰＴ
（９）ｓＴｊ ｓＴｉ＋ｄＴｉ，ｊ∈ＵＴ
； （ｉ，ｊ）∈Ａ（１０）ｓＴｉ为非负整数，
ｉ＝０，１，…，Ｎ＋１（１１）
以上模型中，目标函数式（８）最小化活动开始
时间延迟所引起的总损失值ＬｏｓｓＴ
，使得项目尽可
能地按照基准计划稳定实施；约束条件式（９）将Ｔ时刻已经完成和已经开始但未完成的活动开始时间定义为其基准开始时间；式（１０）满足活动间的优先关系约束；式（１１）为决策变量的定义域约束。注意，反应性调度是一个多阶段决策过程，每次中
断发生时，需要更新开始时间ｓｂｉ
。策略１中承包商最终的最大累计资金缺口可按下式计算得到
  　Ｇｒｅａｌｍａｘ＝ｍａｘｔ＝０，１，ｋ，ｓＴＮ＋１｛∑
ｉ∈ＦＡｔ
ｃｉ＋∑
Ｔ ｔ
ＬｏｓｓＴ
－∑
ｉｋ∈ＦＰｔ
ｐｋ｝
其中，ＦＡｔ＝｛ｉ：ｓｉ＋ｄＴｉ ｔ｝，ＦＰｔ＝｛ｉｋ：ｓｉ
ｋ＋ｄＴ
ｉｋ ｔ｝。２）现金流均衡策略
  　ｍｉｎＧＴｍａｘ＝ｍａｘｔ＝０，１，ｋ，ｓＴＮ＋
１｛∑ｉ∈ＦＡｔ
ｃｉ＋
∑
Ｔ ｔ
ｃＴ
－∑
ｉｋ∈ＦＰｔ
ｐｋ｝
（１２）  　ｓ．ｔ．ｃＴ＝∑
ｉ∈ＵＴ
ｗｉ
（ｓＴｉ－ｓｂｉ）（１３）
（９），（１０），（１１）
上述模型中，目标要求式（１２）最小化项目承
包商实际最大累计现金缺口ＧＴ
ｍａｘ
；约束条件式（１３）计算得到中断发生时承包商调整基准计划的费用；其余各约束则与策略１中相同。同理，每次中断发生时都要对基准进度进行更新。在策略２
下，承包商最终最大累计资金缺口Ｇｒｅａｌ
ｍａｘ可通过对基准进度进行若干次调整的ＧＴ
ｍａｘ
取最大值而得到。９
１１第２期  宁敏静，等：基于随机活动工期的现金流动态均衡前摄性与反应性项目调度优化
２　算法设计
鉴于研究问题的复杂性，这里采用禁忌搜索和模拟退火相嵌套的混合算法ｔａｂｕ ＳＡ进行求解。针对特定的优化问题，目前已有多种不同的混合算法被开发出来，文献［１６］提出与遗传算法相结合的混合算法，通过优势互补，克服单一算法的不足，增强算法的搜索效率。基于体搜索的遗传算法虽然收敛速度快，但其生成邻点等操作较为复杂，计算量较大。本文选用ｔ
ａｂｕ ＳＡ算法，兼具全局搜索与记忆性等优点，由当前解生成邻点解的操作简单易行，计算量相对较小，并且更易于编程实现。２．１　解的表示及初始可行解的生成
开始时间偏移量列表ＳＬ：该列表由Ｎ＋１个开始时间偏移裕量εｉ∈［０，ｌｉ－ｅｉ］构成，其中，ｅｉ和ｌｉ分别是活动ｉ的最早和最晚开始时间，通过ＣＰＭ（ｃｒｉｔｉｃａｌｐａｔｈｍｅｔｈｏｄ）法计算得到。初始可行解ＳＬｉｎｉ
按如下方式构造：计算各活动的时间窗［０，ｌｉ－ｅｉ］，在时间窗内为各活动选择一个εｉ
，并计算各活动的开始时间，若ｓｂ
Ｎ＋１
Ｄ，且
∑Ｎ＋１
ｉ＝０
（ξｉＢｉ） Ｒｏｂｕ
，则接受Ｓ
Ｌｉｎｉ
作为可行解。否则，重复该步操作，直到生成可行的ＳＬｉｎｉ
为止。２．２　邻点生成及其性质
对于当前列表ＳＬｃｕｒ
，随机选择一个εｉ并将其值改变为区间［０，ｌｉ－ｅｉ
］中的另一值，计算各活动的开始时间，若ｓｂ
Ｎ＋１
Ｄ且∑Ｎ＋１
ｉ＝０
（ξｉＢｉ
） Ｒｏｂｕ
，则得到一个可行邻点Ｓ
Ｌｎｅｉｒ
；否则，重复上述操作直至获得一个可行邻点ＳＬｎｅｉｒ
为止。
通过对问题模型特征的分析，针对该邻点生成方式，提出邻点生成的相关性质。给定一个可行的进度安排，以支付时间Ｔｋ（ｋ＝１，２，…，Ｋ）为边界，该进度计划被分割成了若干段，即（０，Ｔ１），（Ｔ１，Ｔ２），…，（Ｔｋ－１，Ｔｋ）。通过这些区间和边界，我们可以定义两组活动集合，
Ｗｋ和Ｗｋ′，分别表示如下：
Ｗｋ＝｛ｉ｜Ｔｋ－１＜ｓｂ
ｉ
＋μ（ｄｉ）＜Ｔｋ
｝，Ｗｋ′＝｛ｉ｜ｓｂ
ｉ＋μ（ｄｉ）＝Ｔｋ
｝，ｋ＝１，２，…，Ｋ通过分析研究问题的特征，以这两类活动集合为基础，两个改进邻点生成的性质具体表述如下：
性质１　在生成邻点的过程中，如果以该邻点解为基础得到的两组活动集合Ｗｋ和Ｗｋ′（ｋ＝１，２，…，Ｋ），与当前解的两组活动集合相同，则该邻点是无效的，可以省略搜索。
证明　在项目执行过程中，在（Ｔｋ－１，Ｔｋ
）内发生的活动费用将在支付时刻Ｔｋ被补偿。因此，
随着活动费用的累积，承包商的累计资金缺口在Ｔｋ－１时刻达到最大。在Ｔｋ时刻，如果获得的支付少于在此时刻发生的总费用，则该最大缺口将继续增加；否则，将会减小。可见，在（Ｔｋ－１，Ｔｋ］内，最大资金缺口必将发生在时刻Ｔｋ－１或Ｔｋ。不难看出，在性质１的条件下，（Ｔｋ－１，Ｔｋ］内的最大资金缺口将保持不变，整个项目执行过程中的最大资金缺口Ｇｍａｘ也将保持不变。因此，该邻点是无效的，可以省略搜索。
性质２　在生成邻点的过程中，如果某些活动的开始时间发生改变，使得一个或多个活动从Ｗｋ′流向Ｗｋ，而其他活动仍然保留在原来的集合里，则该邻点是无效的，可以省略搜索。
证明　如果一个或多个活动从Ｗｋ′流向Ｗｋ，而其他活动仍然保留在原来的集合里，则时刻Ｔｋ－１上的累计现金流出随着Ｗｋ中活动数目的增多而增加。然而，Ｗｋ中的活动要在时刻Ｔｋ才能被支付，从而发生在时刻Ｔｋ－１上的累计现金流入保持不变。我们可以看到，在给定条件下，承包商在（Ｔｋ－１，Ｔｋ）内的累计资金缺口是增大的。在时刻Ｔｋ，由于在（Ｔｋ－１，Ｔｋ］内完成的活动没有发生变化，承包商的资金缺口将保持不变。综上，在性质２的给定条件下，（Ｔｋ－１，Ｔｋ］上的最大资金缺口（发生在时刻Ｔｋ－１或Ｔｋ）将进一步增加或保持不变，这导致项目执行过程中的最大累计资金缺口不会改善。因此，该邻点是无效的，可以省略搜索。２．３　算法参数设置
·初始温度：初始温度Ｔ０通过式子得到ＶＧｍａｘ／ｌｎＰｒ，其中ＶＧｍａｘ是初始解的５０个邻点中目标函数值的最大绝对差值，Ｐｒ是初始接受概率，设为０
．９７。·退火速率：从初始温度开始，温度按照比率ｃｏｏｌ（０＜ｃｏｏｌ＜１）持续下降，设为０．９５。
·迭代次数：在某一固定温度下的迭代次数ｓｔｅｐ达到１０·Ｎ时，进行降温处理。
·终止温度：温度降至终止温度Ｔ＿ｅｎｄ＝０．１时算法终止。该参数与终止条件相匹配。
·禁忌列表：均采用“先进先出ＦＩＦＯ（Ｆｉｒｓｔ ｉｎ Ｆｉｒｓｔ ｏｕｔ）”的原则进行更新：当算法从当前解向选定的邻点移动时，该移动的逆向移动从底部加入禁忌列表，避免算法重新退回到当前解；与此同时，最早进入列表的逆向移动从顶部移出，列表中其余逆向移动向上递进一位。所有位于禁忌列表中的逆向移动都是被禁止的，但是，如果一个被禁止的逆向移动能够生成比当前最好解还要好的邻点时，那
０２１运　筹　与　管　理          　２０２１年第３０卷
么它的禁忌状态可以被激活，以使算法能够移动到
该邻点上，从而避免错失问题的最好解。
２．４　混合算法ｔａｂｕ ＳＡ的搜索过程
将禁忌搜索嵌套在模拟退火中，算法终止条件是由模拟退火确定，步骤如下。
步骤１　输入初始温度Ｔ
０
、冷却速率ｃｏｏｌ（０＜ｃｏｏ＜１）、终止温度Ｔ＿ｅｎｄ，在每一温度下的迭代步数Ｎｕｍ。初始化禁忌列表ＴＬ。给定初始解Ｓ０及
其目标函数值Ｇ０
ｍａｘ
。
步骤２　循环温度设定：ｔｅｍｐ＝Ｔ
０
。
步骤３　循环迭代步数设定：ｓｔｅｐ＝０。
步骤４　在ｔｅｍｐ下由Ｓ０生成一个邻点Ｓ１，检查生成该邻点的移动是否位于禁忌列表ＴＬ中，若是转步骤５；否则，转步骤６。
步骤５　计算邻点下的目标函数值Ｇ１
ｍａｘ
。若
ＶＧ
ｍａｘ＝Ｇ１
ｍａｘ
－Ｇ０
ｍａｘ
＜０，激活生成该邻点移动的禁忌
状态，并更新禁忌列表，转步骤６；否则，转步骤４。
步骤６　计算邻点下的目标函数值Ｇ１
ｍａｘ
。若
ＶＧ
ｍａｘ＝Ｇ１
ｍａｘ
－Ｇ０
ｍａｘ
＜０，则接受Ｓ１：Ｓ０＝Ｓ１，Ｇ０
ｍａｘ
＝
Ｇ１
ｍａｘ
。否则，生成一个位于［０，１］之内均匀分布的
随机数Ｒｎｄ，若Ｒｎｄ ｅｘｐ（ＶＧ
ｍａｘ
／ｔｅｍｐ２），则接受
Ｓ１：Ｓ０＝Ｓ１，Ｇ０
ｍａｘ＝Ｇ１
ｍａｘ
；反之，拒绝Ｓ１。
步骤７　ｓｔｅｐ＝ｓｔｅｐ＋１。若ｓｔｅｐ Ｎｕｍ，转步骤
４；否则，转步骤８。
步骤８　按冷却速率将温度下降到一定的比例：ｔｅｍｐ＝ｔｅｍｐ ｃｏｏｌ。若Ｔ
０
＞Ｔ＿ｅｎｄ，转步骤３；否则，转步骤９。
步骤９　输出搜索到的结果，即最终的Ｓ０和
Ｇ０
ｍａｘ
，搜索结束。
３　算法测试及仿真分析
３．１　算法测试
针对前摄性调度模型，测试混合算法ｔａｂｕ ＳＡ及其他两个单独算法。算例由ＰｒｏＧｅｎ算例生成
器［１７］依据如下参数的不同设置得到：Ｎ、Ｄ（即项目工期的扩大倍数ρ）、Ｒｏｂｕ 、Ｋ、θ，其中，参数Ｎ取值为４种，其余各参数取值为３种，每种参数组合下生成的算例数为１０个，由此得到４×３×３×３×３×１０＝３２４０个算例，参数设置见表２。算法评价指标：满意解距离已知最好解的平均相对偏差ａｒｄ（％）、满意解距离已知最好解的最大相对偏差ｍｒｄ（％）、各自到的已知最好解的个数ｎｕｍ、搜索到的重复解的个数ｎｒｓ、搜索路径的分散性程度ｄｉｓ、剔除的可行但无效解的比率ｐｅｉ＿ＩＭ１（％）、ｐｅｉ＿ＩＭ２（％）。其中，ｄｉｓ等于搜索过程中所有邻点的分散性ｄｐ之和，本文规定当ε
ｉ
→εｊ（ｉ＝ｊ且εｉ≠
ε
ｊ
）时，ｄｐ＝１，当ε
ｉ
→εｊ（ｉ≠ｊ）时ｄｐ＝２。使用相同的初始解和终止条件，当搜索时长达到１００×（Ｎ－２）ｓ时算法终止（由实验确定）。采用ＶｉｓｕａｌＣ＋＋２０１０编程，在ＣＰＵ为２．１ＧＨｚ，内存为２．００ＧＢ的个人计算机上运行。结果如表３所示。
三个算法的比较。首先，混合算法ｔａｂｕ ＳＡ在ａｒｄ、ｍｒｄ和ｎｕｍ上都分别优于ＳＡ。这表明ｔａｂｕ ＳＡ中的禁忌列表发挥了作用，在搜索过程中避免搜索重复解。这可以通过ｎｒｓ来证明：ｔａｂｕ ＳＡ的ｎｒｓ明显小于ＳＡ的ｎｒｓ。其次，对于ａｒｄ和ｎｕｍ来说，混合算法ｔａｂｕ ＳＡ优于ＴＳ，对于规模较大的问题尤其如此。ｔａｂｕ ＳＡ的随机性（由ＳＡ带来）可以保证整个解空间都可能被搜索到，而ＴＳ在同样的终止条件下，解空间不能被完全搜索，导致错过满意解。ｄｉｓ可以证明：ｔａｂｕ ＳＡ的ｄｉｓ明显高于ＴＳ的ｄｉｓ。可知，在目前实验条件下，混合算法ｔａｂｕ ＳＡ比单独算法的求解效率更高。
两个性质的效果。首先，所有的ｐｅｉ＿ＩＭ１和ｐｅｉ＿ＩＭ２都大于０，但是都随着Ｎ的增加而降低。这表明两个性质在搜索过程中发挥了作用，但随着问题规模的增长，当前解的邻域随之变大，导致新生成的邻点落在ＩＭ１和ＩＭ２所描述的区间里的概率变小，进而使其效率下降。其次，对于所有这三个算法来说，ｐｅｉ＿ＩＭ１都大于ｐｅｉ＿ＩＭ２，即ＩＭ１比ＩＭ２更有利于提升算法的搜索效率。这表明生成邻点的过程与ＩＭ１所描述的区间更匹配。再次，ＴＳ的ｐｅｉ＿ＩＭ１和ｐｅｉ＿ＩＭ２大于ＳＡ和ｔａｂｕ ＳＡ的。在每次迭代过程中，ＴＳ的搜索路径在同一邻域里多次跳跃，有助于
邻点落在ＩＭ１和ＩＭ２所描述的区间里，而ＳＡ和ｔａｂｕ ＳＡ的搜索路径更无章可遁，进而落在以上区间的概率更低。
表２　ＰｒｏＧｅｎ的参数取值
参数取值
非虚活动的算例数Ｎ１０，２０，３０，４０
算例的起始和终止活动数从１，２，３中随机选取
最大紧前和紧后活动数３
活动ｉ的期望工期μ（ｄ
ｉ
）从［１０，２０］中均匀地随机选取
活动ｉ工期的标准差σ（ｄ
ｉ
）从［１，５］中均匀地随机选取
活动ｉ的费用ｃ
ｉ
从［１０，２０］中均匀地随机选取
活动ｉ的挣值π
ｉ
γｃｉ，γ从［１．３，１．５］中均匀地随机选取截止日期ＤρＣｍａｘ，Ｃｍａｘ为项目最早完成时间鲁棒性阈值Ｒｏｂｕ ξｒｏｂｕｍａｘ，ｒｏｂｕｍａｘ为项目的最大鲁棒值截止日期的扩大倍数ρ１．２，１．３，１．４
鲁棒性阈值的扩大倍数ξ０．２５，０．５，０．７５
支付次数Ｋ３，４，５
支付比例θ０．７，０．８，０．９
１
２
１
第２期  宁敏静，等：基于随机活动工期的现金流动态均衡前摄性与反应性项目调度优化

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。