基于MAS的多模式分布式资源约束多项目调度.pdf

第 卷第 期运 筹 与 管 理 ，年 月 收稿日期：基金项目：国家自然科学基金资助项目（）；陕西省自然科学基金资助项目（）作者简介：张豪华（），男，河南许昌人，博士研究生，研究方向：项目调度；白思俊（），通讯作者，男，陕西澄城人，博士，教授，博士生导师，研究方向：项目管理。基于 的多模式分布式资源约束多项目调度张豪华，白思俊（西北工业大学 管理学院，陕西 西安 ）摘要：针对实践中分布式多项目的活动往往具有多种执行模式，提出多模式分布式资源约束多项目调度问题。在项目动态到达环境下，考虑活动不同的执行模式，以工期最短和多项目延期成本最小为目标分别构建局部单项目调度模型和全局多项目决策模型，采用改进变邻域搜索算法求解初始局部调度计划，并设计基于模式调整的全局协商调度算法求解全局决策模型，通过双层算法实现分布式多项目调度中局部单项目调度与全局多项目调度系统性协调，减少项目中断和多项目延期成本。基于构建的多模式测试集进行的多项目数值实验表明：本文设计的双层算法可有效求解多模式分布式多项目调度问题，并且对不同规模问题求解具有良好的适应性。关键词：多模式；多项目调度；变邻域搜索；协商机制中图分类号：文章标识码：文章编号：（）：，（，）：，（），（），（），（），（），（），（）（），：；引言随着市场竞争越来越激烈，企业通过管理稀缺资源同时实施多个项目的情况更加普遍，相关研究也表明，的企业都会同时开展多个项目 。这些项目在地域和组织上逐渐地分散化，企业既要保证各项目的顺利进行，又需要将有限的共享资源合理分配给每个项目。而传统的将多个项目组合为一个大项目进行调度的集中式调度方法，忽略了每个项目的特殊性，会造成项目的资源浪费或原进度计划不可行 。因此，分布式资源约束多项目调度 问 题（，）被提出。该问题是指在多项目执行环境下，每个项目由独立的项目管理者根据本项目目标进行独立的调度决策，但是项目间需要共享有限的全局资源，而共享资源由管理多项目的高级经理进行调度。分布式多项目调度集中了系统决策与分散管理的特点，每个项目的实施除了需要全局资源外，还需要本项目专属的局部资源。多 系统（，）是一种由多个独立主体（）通过相互协作组成的分布式结构系统。多 系统与分布式多项目管理实践中的双层管理机制相一致，即同时存在负责分布式多项目之间资源调度与协调的高级项目经理（，）和负责单个项目内部资源配置和协调的项目经理（，）。因此，一些学者将多 系统引入分布式多项目调度建模中 。中自利 之间会对有限的全局资源竞争，但各个 需要服从 安排，并与 相互协作确定全局资源的分配以及活动的开始时间。目前，的研究主要考虑资源需求和完成时间是单一活动模式的情况。例如：彭武良等 和张静文等 研究了活动仅有一种执行模式下，分 布 式 多 项 目 调 度 的 全 局 资 源 协 调 机 制；等 研究了活动单一模式下，分布式多项目调 度 的 全局 资源 拍 卖 机制；刘 婉 君 等 以 及 和 研究了活动单一模式下，项目动态到达并考虑转移时间的多项目调度问题。然而，在多项目管理实践中，一些活动会有多个执行模式，每个模式对应不同的活动持续时间和资源需求。现有关于多模式的研究，主要关注单项目情况下的多模式。例如：宁敏静等 对活动工期不确定情况下的多模式单项目现金流均衡调度问题进行了深入探讨，并采用模拟退火算法进行求解。但是由于多项目更为复杂，资源既有全局资源又有局部资源，单项目多模式的方法并不能有效解决多项目环境下的多模式调度问题。而现有文献对多项目多模式的研究相对较少，并且大多采用集中式的 方 法 研 究 多 项 目 多 模 式 调 度 问 题。例 如：等 在多个项目集中组成超大项目的情况下，探讨了资源转移受限的多模式多项目调度问题；王伟鑫等 在考虑任务可拆分情况下，采用集中式的方法建立了多模式多项目调度模型和算法。运 筹 与 管 理 年第 卷集中式方法假设项目间的所有资源和信息都是完全共享的，未考虑分布式多项目管理上的分散性。本研究基于 系统，考虑活动的不同执行模式，将分布式多项目调度中局部单项目调度与多项目系统性协调进行集成，进而得到优化的分布式多项目调度计划。本文的主要贡献在于：）采用改进变邻域搜索算法（，），并运用并行调度生成方案，解决局部单项目多模式调度问题。）提出多模式分布 式 资 源 约 束 多 项 目 调 度 问 题（，），在该问题中引入 系统，构建基于模式调整的协商机制，根据项目的到达时间和全局资源量，集成局部调度和全局调度确定多项目调度计划。）通过实验研究，验证局部调度算法和全局资源协商机制的有效性，并分析基于模式调整协调机制的效果。本研究不仅更加符合分布式多项目调度的实际情况，并且可有效减少工期拖延、资源闲置和项目中断，进而提高企业分布式多项目管理的效率。问题描述 以多项目延期成本最小为目标，确定一个满足优先关系约束、局部资源约束和全局资源约束的多项目调度计划。该问题由多个相互独立的子项目组成，每个项目对应一个 ，每个子项目具有不同的到达时间。多个项目由 负责协调。首先，根据掌握的本项目开始时间、局部资源限量、活动间逻辑关系和活动执行模式等信息，以项目工期最短为目标，独立地做出本项目的调度决策，并向 提交全局资源需求和对应活动的模式信息。其次，收到 提供的信息后，根据全局资源信息和本文构建的基于模式调整的协商机制，分配全局资源给各个 。最后，根据分配的全局资源对原调度计划做出相应调整，以满足全局资源约束，进而得到最终的分布式多项目调度计划。由于 的自利倾向，为实现本项目工期最短，会优先按照工期最短的施工模式安排活动，以便在全局资源争夺中更早更多的获得全局资源。基于此，本文按照活动不同模式对应的工期不同，将活动模式分为：长工期模式、中工期模式和短工期模式。短工期模式工期较短资源需求强度往往较高，但是由于全局资源有限，之间会对有限的全局资源互相竞争。为实现对复杂环境下的多项目协调与全局优化，本文设计了基于模式调整的协商机制。该协商机制在 完成局部调度并提交全局资源和活动模式信息给 后开始执行，在满足资源约束和工序关系前提下，通过对原计划中的一些活动调整执行模式，最大程度的实现项目执行的连续性，减少项目中断，提高资源利用率，并合理安排延期成本较高的项目，减少分布式多项目延期总成本。不仅使每个项目局部调度得到优化，还实现对分布式多项目整体的协调与优化。本文使用的符号定义如表 所示。表 符号定义符号含义符号含义多项目中的第 个项目，项目 的实际完成工期项目集合，项目 关键路径工期项目 的第 个活动 ，第 个项目局部资源项目 的活动集合，第 个项目局部可再生资源 项目 到达并且开始的时间 第 个项目局部不可再生资源项目活动中的某一时刻，全局可再生资源时刻序号，为多项目计划工期上限 第 个项目第 个活动采用 模式对第 种局部可再生资源的需求 第 个活动的执行模式，第 个项目第 个活动采用 模式对第 种全局可再生资源的需求 活动 执行第 个模式的活动时间 第 个项目第 个活动第 模式对第 种局部不可再生资源需求 项目 第 个活动开始的时间项目 单位时间延期成本 基于 的两阶段模型 局部调度模型由于每个项目的独特性，各个子项目的 为生成全局资源需求计划和本项目调度计划，需要根据本项目的局部资源、项目开始时间、活动模式和活动优先关系等局部信息，在暂不考虑全局资源限量的条件下，进行本项目内部的局部调度，从而得到本项目的局部调度计划。因此，以工期最短为目第 期张豪华，等：基于 的多模式分布式资源约束多项目调度标构建如下的局部调度模型：（）；，（）（）；，（，），（）；，（）；，（），（），（）上式中，为决策变量，若项目 的活动 采用 模式且在时刻 结束时为 ，否则为 。式（）为目标函数，即最小化项目工期；式（）表示每个活动只能选择一种执行模式；式（）表示优先关系约束，确保活动在其所有紧前活动结束后开始，其中 是 的后续活动；式（）表示正在执行的活动使用的局部可再生资源量不能超过其可用量；式（）表示项目 使用的局部不可再生资源量不能超过总资源量；式（）表示项目 的开始时间不能早于项目到达并且可以开始的时间；式（）为决策变量可行域约束。全局决策模型 根据 提交的活动开始时间和活动模式等信息，在发生全局资源冲突时，先调整活动模式以满足全局资源约束，若不满足，则按照如下模型确定调度：（）（）；，（）此外，还需要满足约束式（）（）（）。式（）为全局协商的目标函数，即多项目延期总成本最小。由于项目的重要程度不同，因此不同项目的延期成本不同，项目延期时间等于项目结束时间减去项目开始时间 和关键路径工期 ；式（）表示全局资源需求量不能大于可用量，其中 表示全局资源需求发生冲突的时刻；式（）（）（）约束条件与局部调度约束相同。算法设计由于局部调度阶段 暂不考虑全局资源限量，故其本质上是多模式项目调 度问 题（）。是比 更复杂的 问题，大部分商业求解器无法在短时间内对大规模算例进行求解，因此本文采用 算法求解局部调度问题，并在局部调度的基础上进一步构建全局协商调度算法，求解全局调度问题，通过局部和全局双层算法求解 。局部调度算法本文基于局部调度问题的特征，采用由活动优先关系 和模式 双层列表对解进行编码，该列表上层由 个满足优先关系的活动序号组成，下层由每个活动对应的模式 组成。解码按照并行调度生成机制（）进行解码。模式列表 采用符合 自利倾向的最短工期规则选择初始模式，当两种及以上模式工期相同时，选择资源总需求最少的模式打破平局。算法具体步骤如下所示：初始化相关参数，运行次数 ，时刻 。按照模式选择规则确定模式列表 。按 照 随 机 活 动 优 先 级 规 则，采 用 生成可行调度，选择工期最短的可行调度作为初始调度计划 并输出其 。判断 工期是否等于 ，若等于，运 筹 与 管 理 年第 卷则该 达到最优直接转入 ，若不等于则进入 。对调度计划 的活动列表 依次采用 和 改变邻域结构，模式列表 采用邻域构造规则，通过对调度计划 的模式链表和活动列表 的变换生成邻点解集 。从 中删除重复解，并选择满足活动优先关系的解，按照并行调度生成满足资源约束的可行调度计划集合 。选取初始解 和 中工期最短的调度计划作为新的调度计划。运行次数 ，当 时，返回 。当 时算法停止，转入 。输出最终结果。基于模式调整的全局协商调度算法合理有效的全局协商机制是解决 问题中分配全局资源的关键。本文基于局部调度算法，设计求解全局决策模型的全局协商调度算法。由于全局资源有限和 的自利倾向，通常会首先按照短工期模式需求的全局资源提交给 。根据 提交的全局资源需求信息，将有全局资源需求的活动开始时刻定为需要协商的协商点。并对所有协商点进行判断，若该协商点处全局资源不能满足所有 的需求，则对该协商点处开始的活动进行协调。为减少项目中断，先根据活动模式信息依次调整活动模式，调整后若仍不满足，需要根据全局协商决策模型，确定活动安排顺序和模式。将协商点处活动调整信息反馈给 对原计划进行调整，为避免活动开始时间变动造成新的局部资源冲突，因此对原计划协商点后开始的活动按照火车调度规则进行平移调整。所有协商点都满足全局资源约束后，基于模式调整的协商完成。具体过程如下：汇总 提交的全局资源的需求计划。从 时刻开始，有全局资源需求开始处定为需要进行决策的协商点，协商点处待安排的活动集合为。若 协 商 点 处 待 安 排 的 活 动 数 量 且全局资源需求小于全局资源可用量，则按照 提交的最优资源需求进行安排；若大于资源限量，依次调整至中工期、长工期模式，直到满足全局资源限量。若协商点处待安排的活动数量 ，由 组织 进行协商。优先分配全局资源给延期成本高的项目，若超过全局资源限量，按照延期成本升序对协商点活动依次调整为全局资源需求少的施工模式，调整至满足全局资源约束时停止，若模式调整后仍不满足全局资源约束，则进入 。按照变邻域搜索算法求解全局协商调度决策模型，确定协商点处项目活动开始时间和模式，根据求解结果将全局资源分配信息和相关活动信息传递给 。更新本项目协商点处的活动开始时间和模式，并根据更新的活动开始时间，按照平移策略调整该协商点后的活动开始时间。将调整后的全局资源需求信息再次提交 。重复执行 ，直至多项目总计划期内无资源冲突，输出最终结果。数值实验为了进一步评估本文各项目局部调度 算法以及基于 的全局协商调度算法的效果，基于 算例库中的算例构造分布式多项目进行数值实验。编程语言使用 ，算法运行环境为：（）（）、内存的个人电脑。实验设计本文采用的 算法对局部调度和全局协商调 度 都 有 重 要 意 义。因 此，本 文 首 先 采 用 算 例 库 验 证 算 法 的 有 效 性，在 算法有效性的基础上进一步构建测试集验证基于模式调整的全局协商调度算法的有效性。由于目前尚无直接用来测试多模式分布式多项目调度问题的标准问题库，并且 算例库中 算例没有多模式，为验证基于模式调整的全局协商调度算法的有效性，需要进一步构造适用 的 问 题 集。本 文 采 用 基 于 标 准 问 题 库 中 算例集进行修改后作为测试集，修改方法是在测试集中分别随机选取若干项目，在 ，中随机生成不同项目的单位时间延期成本，项目到达时间取关键路径的 。此外，还需要在多项目算例中随机添加 种全局可更新资源，全局资源量不小于所有活动中全局资源需求最大的活动需求量，并且不同模式对应不同的全第 期张豪华，等：基于 的多模式分布式资源约束多项目调度局资源需求量，具体确定方法可参考 的研究。实验结果与分析首先，使用 算例库中多模式算例测试局部调度 算法。算例中，有两种可更新资源和两种不可更新资源，每个活动有三种不同执行模式。每个算例运行 次，并取结果中的最优解作为最终解。每次变邻域搜索过程生成邻点解不小于 。将运算结果分别与 公布的最优下界（）和关键路径下界（）进行比较，（）和 （）分别表示在每个算例集中 算法得到的最优解（）与 和 的平均相对偏差。验证结果如表 所示，算法计算速度较快，计算出每个实例时间均在 秒之内，并且具有较好的规模适应性，计算结果优于 公布的大多数算法。本文提出的基于模式调整的全局协商调度算法实质是在全局资源约束条件下，协调来自多个项目具有不同执行模式的活动，使得每个项目因全局资源限制造成的中断次数、项目延期总成本最小，全局资源使用效率最大。为了验证该算法的有效性，在其它条件保持不变的情况下，分别计算以下三种情况的分布式多项目的平均项目延期和延期总成本：）随机分配一种模式，不进行模式调整，不考虑项目的延期成本；）仅采用模式调整解决全局资源冲突并生成满足全局资源约束的调度计划；）在进行模式调整时考虑项目延期成本，并生成可行的全局资源调度计划。平均项目延期（）是所有项目的实际工期超过关键路径工期的平均值。项目延期总成本（）是指各单项目实际工期超过关键路径工期产生的延期成本之和。结果如表 所示。表 局部调度 算法实验结果参数 （）（）（）（）平均时间（秒）表 不同情况下 的平均项目延期和延期总成本问题集随机确定模式调整协商机制相对偏差 （）（）由数值实验结果和图 可知，基于模式调整的协商机制与随机确定一种模式和仅进行模式调整两种情况相比，分别平均节省 和 。基于模式调整的协商机制与随机确定一种模式情况相比 平均减少 ，而与仅进行模式调整情况相比 平均未减少，主要是由于每个项目的延期成本不同，为了实现项目延期总成本最小化，需要提前安排一些项目延期成本较高的活动，会对工期产生一定影响。随着算例规模的增加，各项目对全局资源的竞争加剧，项目的延期总成本逐渐增加，但通过模式调整和优先安排延期成本高的项目活动可有效减少项目延期总成本的增加。图 延期总成本对比 结语本文针对以往仅考虑活动有一种执行模式的运 筹 与 管 理 年第 卷分布式多项目管理问题提出多模式分布式多项目调度问题，研究了活动具有多模式情况下资源约束型分 布 式 多 项 目 调 度 问 题。基 于 建 立 了 的两阶段模型，将分布式多项目调度中局部单项目调度与全局多项目调度系统性协调进行集成。并针对局部多模式项目调度，提出改进变邻域搜索算法，针对全局资源调度设计一种基于模式调整的协商机制，在 和 的合作下最大程度的实现各个项目执行的连续性以及局部调度目标和全局目标的统一，提高分布式多项目管理的效率。基于改进的 测试集进行了数值实验，结果验证了 算法和基于模式调整的协商机制针对测试集的有效性，并且有效减少了项目延期总成本。在资源供应不稳定的情况下，活动的多种模式的调整还有利于提高项目的鲁棒性。未来研究将在资源具有不确定性情况下，建立多项目鲁棒性衡量指标，构建资源不确定条件下的分布式多项目全局资源分配与鲁棒性调度集成优化模型。另外，分布式多项目间资源需要多次转移，往往也会产生一些相应的费用。因此，考虑资源转移费用、多项目延期成本和鲁棒性多目标优化是本文下一步的研究方向。参考文献：，（）：刘东宁，徐哲，李飞飞 基于合作博弈协商机制的分布式资源受限多项目调度 系统工程理论与实践，（）：彭武良，陈良威，马雪丽 分散式项目群调度的双目标优化 方 法 研 究 管 理 工 程 学 报，（）：张静文，刘婉君，李琦 基于关键链改进搜索的遗传算法求解分布式多项目调度 运筹与管理，（）：，：，（）：刘婉君，张静文，刘万琳 基于拍卖机制的资源转移时间型动态分布式多项目调度 中国管理科学，（）：，：，（）：宁敏静，何正文，刘人境 基于随机活动工期的多模式现金流 均 衡 项 目 调 度 优 化 运 筹 与 管 理，（）：，（）：王伟鑫，王旭，葛显龙 任务可拆分的多模式多项目调度模型与算法 计算机集成制造系统，（）：（，），（）：第 期张豪华，等：基于 的多模式分布式资源约束多项目调度