基于里程碑支付的多模式多项目现金流平衡调度优化.pdf

第 卷第 期运 筹 与 管 理 ，年 月 收稿日期：基金项目：国家社会科学基金资助项目（）作者简介：何羽康（），男，山西运城人，博士研究生，研究方向：运筹与优化；贾涛（），通讯作者，男，山东泰安人，教授，博士，研究方向：运筹与优化，供应链与物流管理；王能民（），男，湖南双峰人，教授，博士，研究方向：供应链及物流系统的运营及优化。基于里程碑支付的多模式多项目现金流平衡调度优化何羽康，贾 涛，王能民（西安交通大学 管理学院，陕西 西安 ；过程管理与效率工程教育部重点实验室，陕西 西安 ）摘要：现金流入与流出的动态平衡，对于承包商平稳实施项目具有重要的现实意义。本文基于这一实际背景，研究了在里程碑支付条件下，活动具有多种执行模式的多项目现金流平衡调度问题。首先，在对研究问题进行界定的基础上，构建了多模式多项目现金流平衡调度优化模型并提炼了模型的基本性质；其次，针对问题的 属性，开发了禁忌搜索启发式求解算法，根据问题性质提出算法的改进措施；最后，用一个实际案例对模型和算法进行了验证，得到如下管理启示：基于最大现金流缺口发生时段，适当延后相关里程碑活动的完成时间或调整相关非里程碑活动的开始时间，同时，根据现金流分布合理平移部分单项目的进度计划，能实现现金流出与流入的最佳匹配并有效减小最大现金流缺口。关键词：多项目调度；现金流平衡；优化模型；禁忌搜索；基于里程碑支付中图分类号：；文章标识码：文章编号：（）：，（，；，）：，：，：，（）（），：，：；引言对于现实中的绝大多数项目来说，承包商通常会发生两种形式的现金流：现金流出和现金流入。在项目的实施过程中，如果承包商的现金流出与流入能够保持平衡，那么就不会出现现金流缺口，项目便可以顺利地向前推进和实施；否则，在现金流出与流入之间即会产生缺口，这会给项目的平稳实施造成困难并引发额外的融资成本。因此，在项目的执行过程中，如何保持现金流出与流入的动态平衡，是承包商必须面对和解决的一个关键问题。从本质上讲，项目的现金流出及流入均与项目调度紧密相关：一方面，现金流出的大小及时间取决于活动执行模式和开始时间的安排；另一方面，现金流入依据合同支付条件由项目的进展程度所决定。所以，通过对项目的合理调度可以有效地协调现金流出和流入，从而实现现金流的平衡。由此可见，以现金流平衡为目标的项目调度无疑是一个具有较高实用价值的研究问题。考虑到里程碑支付是现实中的最为常见支付条件之一，本文研究基于里程碑支付的多模式多项目现金流平衡调度问题。在论文的后续部分，首先在第 节对相关文献进行综述；然后在第 节构建问题的优化模型并提炼模型性质；第 节设计问题求解的改进禁忌搜索启发式算法；第 节用一个实际案例对研究进行验证；最后，第 节给出研究结论并指出未来的研究方向。文献综述考虑现金流的项目调度问题属于项目调度研究领域的一个重要分支，该分支目前存在大量的研究成果。例如，和 在考虑资金约束下，构建了三种不同的净现值模型并设计了两种新的调度方法。崔南方等 提出了基于现金流关键度的分散缓冲算法，从而在现金流绩效指标上取得了更优的结果。在平衡各个时期活动的融资需求与资金供给的前提下，和 研究了考虑融资的多目标项目调度问题。郑维博等 针对多模式净现值最大化项目调度问题，设计了双层嵌套禁忌搜索启发式算法。和 借助不同的启发式信息开发了一种蚁群算法，用于求解基于融资的项目调度问题。也有不少学者对多项目调度问题进行了研究，针对基于融资的多项目调度问题提出了一种启发式算法，通过计算实验验证了算法的有效性。和 利用约束规划构建了净现值最大化多项目调度模型。等 同时考虑了工期、成本、融资等多个目标，提出了一种第 期何羽康，等：基于里程碑支付的多模式多项目现金流平衡调度优化基于快速精英非支配排序的遗传算法。在考虑共享多技能人力资源前提下，于懿宁等 建立了局部调度及全局协调决策模型并设计了相应的求解算法。张静文等 针对分布式多项目调度问题，开发了一种自适应遗传算法。关于现金流平衡项目调度问题，等 研究了承包商最大现金流缺口最小化单项目调度问题，开发了问题求解的变邻域搜索、禁忌搜索和两者混合的启发式求解算法。宁敏静等 将上述问题扩展到随机活动工期环境中，使得现金流均衡项目基准计划具有应对工期随机变化的能力。等 研究了可重复使用资源约束下的多项目现金流平衡调度问题，设计了问题求解的模拟退火和禁忌搜索算法。然而，需要特别强调的是，关于多模式多项目现金流平衡调度问题，据作者所知，迄今尚未有系统深入的研究。优化模型构建及问题性质分析 优化模型构建现假定某承包商需要同时实施 个项目，项目 （，）由 个活动组成，其逻辑关系用 （）网络表示。在这些活动中，活动 和 分别是项目虚的开始和结束活动，其他活动均为实活动。活动 （，）具有种执行模式，当其以模式（，）执行时，工期和成本分别为 和 。活动 的挣值为，项目合同价格为 。注意，由于虚活动在现实中并不存在，因而其工期、成本和挣值均为。预付款比例为（），金额为。在 个实活动中，有（）个活动被约定为里程碑活动，它们构成活动集合 。在里程碑活动的完成时刻，业主基于已完成活动的累计挣值进行中间支付，支付比例为（），在中间支付中需按比例 扣除预付款。项目 的截止时间为，当项目完成时，业主须向承包商付清合同总价款。现假定活动 的执行模式和开始时间分别安排为 和，定义（，和（，）分别为项目 的活动执行模式和开始时间向量，则（，）构成项目 的进度计划安排。在 个项目中，将最早开始项目的开始时间表示为 ，最晚完成项目的完成时间表示为 。则给定 个项目的进度计划 （，），（，），（，），在其实施过程中的任一时刻 ，承包商的累计现金流出 可用下式计算：。在项目执行过程中，业主在 个里程碑活动完成时进行中间支付。令 和 分别为第 和 次支付时承包商已完成活动的集合，将第 （，）次中间支付的支付量记为，则（）（）。用 和 分别表示预付款及最后一次支付，则有：，。给定 个项目的进度计划，在其进行过程中任一时刻 ，承包商累计现金流入 可用下式计算：，其中，表示 的发生时间。将 个项目执行过程中 时刻的现金流缺口定义为，则由 和 便可计算出：。令 为所有 中的最大值，则本文所研究问题即是如何合理地安排 以最小化 ，其优化模型表述如下：，（），（，）；，（），（）（）（），；，（），（）和 为非负整数，；，（）其中，表示项目 中各活动之间的逻辑关系集合。在上述优化模型中，目标函数式（）最小化承包商最大现金流缺口；约束条件式（）确保某一活动 的开始时间不早于其紧前活动 的完成时间；式（）为项目的截止时间约束；式（）计算项目实施过程中间支付的支付量；式（）确定预付款及项目完成时刻的支付量；式（）为决策变量的定义域约束。问题性质分析给定一个多项目进度计划，业主的支付 的发生时间也随之确定。现假定在相邻两次支付所形成的时间区间（，）内，最晚开始活动的开始时间为 。那么，关于在区间（，）内的最大现金流缺口，存在如下性质 。性质 给定某一多项目进度计划 ，在业主的相邻两次支付所形成的时间区间（，）内，承包商运 筹 与 管 理 年第 卷的最大现金流缺口一定发生在 ，）时段上。现将在所有的（，）区间中，发生的那个区间记为（，），该区间内最后一个开始活动的开始时间记为 ，在 完成的里程碑活动记为 。基于上述定义，可以提出如下的性质 和性质 。性质 给定某一多项目进度计划，在不影响其他活动开始时间的前提下，如果里程碑活动 的开始时间可以延后，使其与在区间（，）内完成的某一非里程碑活动同时完成，那么执行该操作能够降低 。性质 给定某一多项目进度计划，在不影响其他活动开始时间的前提下，如果在区间（，）内完成的某一非里程碑活动可以提前至 时刻完成，或者推后至 时刻开始，那么执行该操作能够降低 。禁忌搜索启发式算法设计多模式项目调度问题已被证明为 问题，考虑到本文所研究问题的复杂性，从实用角度出发，采用禁忌搜索算法求解上述优化模型。解的表示及解码算法用如下两个集合表示问题的解：（）活动执行模式集合 ：该集合由 个项目的活动执行模式向量 构成：（，），它决定了项目活动执行模式的安排。（）开始时间偏移集合 ：该集合由 个项目的开始时间偏移向量 构成：（，），其中，（，），和 分别是活动 由关键路径法所决定的最早和最晚开始时间。令 为所有紧前活动都已安排了开始时间的活 动 所 构 成 的 集 合，那 么，给 定 一 组（，），其对应的多项目进度计划安排 可用下述解码算法生成：步骤 令 ：。步骤 输入项目 的开始时间；令 ：；根据 和 分别确定项目 中各活动的 和。步骤 基于 及活动之间的优先关系，依次安排 中的活动尽可能早地开始，从而获得一个初始的；进一步令：。步骤 将已安排了开始时间的活 动 移出 ，同时将所有紧前活动都已安排了开始时间的活动移入 。检查 是否为空集，若是转步骤；否则，转步骤 。步骤 令 ：。判断 是否成立，若成立转步骤 ；否则，转步骤 。步骤 由上述步骤所确定的活动开始时间 组成，与由 所决定的 构成项目 的进度计划安排（，），所有 个项目的进度计划安排共同组成（，），（，），（，）。输出多项目进度计划安排。初始解构造方式及改进措施问题的初始解（，）按下述步骤构造：步骤 给定一个单项目 ，将其所有活动均安排以成本最低的模式执行，由此得到一个。检查在 下项目关键路径长度是否大于项目截止时间。如果不大于，则已获得一个工期可行且成本最低的；否则，在关键路径上选择一个赶工成本增加最小的活动，将其执行模式变为工期较短的模式，重复该操作直至关键路径长度不超过 为止，由此得到一个可行的。对于其他项目也按照上述方式构造相应的，进而得到全部 个项目的活动执行模式向量，它们共同组成了 。步骤 给定一个单项目 ，根据 中的确定活动的执行模式，由此得到各活动的工期。在不违反活动之间的逻辑关系和项目截止时间约束的前提下，安排里程碑活动尽早开始，非里程碑活动尽晚开始，从而生成一个。根据 中各活动的开始时间确定其时间偏移，由此获得 。对于其他项目也按照上述方式构造相应的 ，进而得到全部 个项目的开始时间偏移向量，它们共同组成了 。步骤 输出所得到的初始解（，）。基于 中的性质 和 提出如下措施，对得到的初始解进行改进。在对（，）进行改进时，首先对其进行解码，获得对应的多项目进度计划；然后对 执行如下操作后再进行编码，从而得到改进后的（，）。步骤 输入需改进的多项目进度计划，计算 、和 。步骤 在不影响其他活动开始时间的前提下，检查是否可以将 右移（即延后其开始时间），使得其与在区间（，）内完成的某一非里程碑活动同时完成。如果可以，则执行该操作，转步骤 ；否则，转步骤 。步骤 在不影响其他活动开始时间的前提下，检查在区间（，）内完成的非里程碑活动中，是否存在可以左移（即提前其开始时间）至 完成的活动。如果存在，则对该活动执行这一操第 期何羽康，等：基于里程碑支付的多模式多项目现金流平衡调度优化作，转步骤 ；否则，转步骤 。步骤 在不影响其他活动开始时间的前提下，检查在区间（，）内完成的非里程碑活动中，是否存在可以右移（即延后其开始时间）至 开始的活动。如果存在，则对该活动执行这一操作，转步骤 ；否则，转步骤 。步骤 输出改进后的多项目进度计划。邻点生成机理及算法实施策略给定问题的当前解（，），其邻点解（，）用如下两个算子随机生成：（）模式改变算子：从 中随机选择一个，在选定的 中任选一个；在项目截止时间 的约束下，将所选 随机地变为另一可行的值，由此得到一个新的 ；该 与仍保持不变的 一起构成一个新解，记为（，）。（）偏移改变算子：从 中随机选择一个，在选定的 中任选一个；在项目截止时间约束下，将所选 随机地变为 ，中的另一个值，由此得到一个新的 ；该 与仍保 持 不变 的 一 起 构 成 一 个 新 解，记 为（，）。在得到（，）后，采用 中所给出的措施对其进行改进。考虑到在进行项目调度时，活动的开始时间必须在确定了执行模式之后才能安排，因此，将禁忌搜索算法设计为如下两个内外层相互嵌套的迭代搜索：内层在给定 下搜索满意的 并将结果反馈给外层，而外层在内层搜索返馈结果的基础上搜索满意的 ，内外层的搜索结果共同构成问题的满意解。对于内外层搜索分别定义禁忌列表，用于存储搜索过程中的从当前解到邻点解的逆向移动。所有位于禁忌列表中的逆向移动都是被禁止的，但如果某个被禁忌的逆向移动能够生成比当前最好解还要好的邻点解时，其禁忌状态可以被激活，以便算法能够移动到该解上。在算法的搜索过程中，两个禁忌列表均采取“先进先出”的规则进行管理，同时，算法探测过的最好解被保存下来并不断更新。算法的停机准则定义为其运行时间，即事先设定好一个 ，当算法的运行时间达到 时便停止搜索，并将保存的当前最好解输出为问题的满意解。案例研究 案例数据 公司是一家中型民营建筑企业，年月 日至 年 月 日，该企业同时实施了两个项目（分别称为项目和项目）。项目活动具有两种 执 行 模式（分 别用 执行 模 式 和 表示），活动挣值及在不同执行模式下的工期和成本均已知，其他数据如下：，；，；，。为表述方便，将 年 月 日上午 时记为 时刻，项目和项目分别于 和 时刻开始，它们的截止时间 和 分别为 和 时刻。改进算法与原启发式算法的对比为了评价算法的绩效并验证基于性质所提出的改进措施的效果，作者编写了两个版本的算法程序：原启发式算法 和改进算法 ，前者没有添加改进措施，而后者使用了改进措施。两个算法在运行到相同的 后停止，其内外层搜索的禁忌列表长度分别设置为 和 ，当内层搜索探测的可行解数达到 时跳出迭代循环。将 设置为 ，秒等 个不同值计算问题的满意解，结果表明，当添加了改进措施之后，算法的搜索效率明显提升：在相同的停机准则下，改进算法满意解质量均不差于原启发式算法；改进算法 秒即可找到使 最低的满意解，而原启发式算法则需 秒才能找到相同的满意解。实际进度计划与满意进度计划的比较项目和项目的实际进度计划 和由算法计算得到的满意进度计划 如下：（，），（，），其中，（，），（，），（，），（，）。（，），（，），其中，（，），（，），（，）；（，）。运 筹 与 管 理 年第 卷在实际进度计划下，承包商的最大现金流缺口 为 ，万元；而在满意进度计划下，该缺口 为 ，万元，比实际进度计划下降了 。此外，满意进度计划的现金流整体平衡情况也好于实际进度计划：多数 低于 ，而且曲线上 区域的时段明显多于 曲线。比较项目的实际进度计划和满意进度计划，可以发现二者的关键差异在于活动 和 执行模式的选择，以及活动 ，和 开始时间的安排，这些差异使得该单项目最大现金流缺口由 万元上升到了 万元；而在项目的两个进度计划中，关键差异为活动 和 开始时间的安排，它导致实际进度计划下的单项目最大现金流缺口上升了 。如果将项目和综合到一起考虑，可以发现，在满意进度计划下二者匹配得更为合理，通过将项目的进度计划向后平移个日历天，可使多项目最大现金流缺口由 万元下降到 万元。通过上述比较分析，可以得到如下管理启示：管理启示 ：以最大现金流缺口发生时段为参照，适当地延后该时段之前最后完成的里程碑活动的开始时间，可以使最大现金流缺口下降。管理启示 ：以最大现金流缺口发生时段为参照，适当地提前或者延后在该时段前后两次支付之间完成的非里程碑活动，可以减小最大现金流缺口。管理启示 ：给定多个单项目的满意进度计划，基于其现金流分布整体平移部分单项目进度计划，能够使现金流匹配更为合理并降低最大现金流缺口。结论论文研究了基于里程碑支付的多模式多项目现金流平衡调度问题。首先构建了问题的非线性整数规划优化模型，通过对模型的分析提炼出其三条性质；随后，针对问题的 属性，设计了内外层嵌套迭代的禁忌搜索启发式算法，基于问题性质提出算法的改进措施；最后，用一个实际案例对模型和算法进行了验证，通过多项目实际与满意进度计划的比较分析，揭示了二者的关键差异并得到如下管理启示：以最大现金流缺口发生时段为参照，适当延后该时段前最后完成的里程碑活动的完成时间，合理调整在该时段前后两次支付之间完成的非里程碑活动的开始时间，可使承包商的最大现金流缺口下降；给定多个单项目的满意进度计划，基于其现金流分布整体平移部分单项目进度计划，能实现多项目现金流的协调匹配并进一步减小最大现金流缺口。需要指出的是，本文的研究没有考虑资源约束对项目进度计划安排的影响；而且，当现金流缺口出现时，也没有给出填补缺口的最佳融资方案。未来作者会把资源约束考虑在内，并同时研究如何合理地进行融资以弥补项目实施过程中的现金流缺口，由此推动该问题的研究向更加贴近现实情况的方向迈进。参考文献：，：崔南方，梁洋洋，赵雁 考虑鲁棒性的 项目调度问 题 系 统 工 程 理 论 与 实 践，（）：，：郑维博，何正文，刘人境 基于融资能力约束的多模式 项目调度优化：双重视角 运筹与管理，（）：，：，：，：，：于懿宁，徐哲，刘东宁 考虑多技能人力资源的分布式多项目 调 度 问 题 系 统 工 程 理 论 与 实 践，（）：张静文，刘婉君，李琦 基于关键链改进搜索的遗传算法求解分布式多项目调度 运筹与管理，（）：，：宁敏静，郑小强，何正文 基于随机活动工期的现金流动态均衡前摄性与反应性项目调度优化 运筹与管理，（）：，（）：第 期何羽康，等：基于里程碑支付的多模式多项目现金流平衡调度优化