分布式多项目调度管理与优化

以项目形式开展各项工作是现代企业广泛采用的高效管理模式，随着经济全球化以及信息技术的快速发展，企业组织所承担的项目逐渐趋于大型化、复杂化和多元化，在地域分布和组织管理上也越来越分散，多项目环境已经成为组织管理的常态。传统的多项目调度是将多个项目集成为“超级项目”，并由一个决策者基于全局共享信息进行资源的分配和集中式调度决策，显然该方式在如今的分散式管理环境下已不再适用。分布式资源受限多项目调度问题（Distributed Resource-Constrained Multi-Project Scheduling Problem,DRCMPSP）涉及多个项目的独立调度以及项目之间共享资源的协调分配，需要在整个系统目标范围内进行整合，以实现局部调度与系统协调的集成。理论上，DRCMPSP是对经典的资源受限项目调度问题（Resource-Constrained Project Scheduling Problem,RCPSP）的扩展，属于NP-Hard问题；实践上，分布式调度管理为地域及组织上分散的多项目管理者提供决策依据，进而提高分布式环境下多项目组织的管理效率。因此，该问题已成为项目管理与调度优化领域研究的新热点，具有重要的理论意义和应用价值。 本书结合多项目管理的实际背景，基于分布式决策的多智能体系统（Multi-Agent System,MAS），对分布式环境下的资源受限多项目调度问题（Resource-Constrained Multi-Project Scheduling Problem,RCMPSP）和时间/成本权衡问题（Time/Cost Trade-off Problem,TCTP）展开重点研究，同时拓展研究全局共享资源不确定情形下的DRCMPSP；通过设计有效的项目调度优化算法和资源分配协调机制，实现分布式多项目局部调度管理和全局资源协调的有效集成。本书的主要研究内容总结如下。 （1）梳理多项目管理的相关概念和主要内容。项目管理从诞生到目前被广泛应用经历了较长的时间，本书系统梳理其发展过程，并在此基础上全面概括多项目管理的相关内容，进而结合当今企业管理实践，深入分析多项目调度管理的特点。 （2）归纳分析多项目调度问题的研究进展。本书分别对传统集中式决策环境下的RCMPSP和TCTP的研究现状进行概述，按照不同的分类方式对DRCMPSP的相关研究进行梳理与总结，进而提出当前研究存在的局限性，为分布式多项目调度管理相关问题的展开奠定了研究基础。 （3）研究基于序贯博弈谈判机制的DRCMPSP。高层管理者在实际的项目管理中更加注重多项目整体性能的优化，以*小化多项目总延期成本为全局目标，较好地结合了分布式多项目管理的实际背景。本书基于MAS建立局部调度与资源协调两阶段决策模型，设计基于正向逆向调度改进的遗传算法（Forward-Backward Scheduling Improved Genetic Algorithm,FBSIGA）求解局部调度问题，以得到项目尽早完工的初始进度计划；设计考虑总延期成本的序贯博弈谈判机制，求解总延期成本*小的子博弈精炼纳什均衡（Subgame Perfect Nash Equilibrium），以此解决项目间的资源冲突问题。本书对基准问题库中的算例展开实验研究，并与基于不同协调机制的分布式决策方法的计算结果进行对比。结果表明：FBSIGA能够获得使各种规模项目尽早完工的初始局部调度计划；当全局资源越稀缺以及多项目规模越大时，采用基于序贯博弈谈判机制的两阶段决策方法能够更有效地降低多项目总延期成本。 （4）研究全局可更新资源可用量不确定情形下的DRCMPSP。考虑到共享资源因突发事件导致的不确定情况，本书将其建模为服从不同分布的随机变量，同时为避免由于活动中断导致项目成本的增加，将项目允许的*大活动中断次数约束加入局部调度优化模型。本书设计全局资源预分配和协调再分配的协调机制。在预分配阶段，按照项目单位延期成本比例分配全局资源可用量，建立各项目调度的马尔可夫动态决策过程模型，以*小化项目期望工期；在协调再分配阶段，根据活动重要度依次分配全局资源剩余可用量，以减小平均项目延期值。本书设计基于全局资源协调分配的Rollout近似动态规划算法，在每个决策点以基于优先规则的启发式算法为基准策略，仿真得到各项目期望工期*小的*优开工活动集合。本书对基准问题库中项目数不同且活动数为30个的多项目算例进行改编，将基于全局资源协调分配的优先规则启发式算法的求解结果作为目标值的上界，以评估Rollout策略的优劣，同时设计不考虑全局资源协调再分配的算法并与之进行对比。研究结果表明：全局资源可用量的分布形式虽对平均项目期望延期和求解效果的影响不大，但随机分布的方差越小，优化目标值和求解效果越好；Rollout策略和全局资源协调再分配过程对于减小平均项目期望延期值发挥着重要的作用。 （5）提出并研究分布式多项目时间/成本权衡问题。考虑到多项目共享一定的总预算，在分配得到的预算约束下，本书以*小化项目完工时间为目标建立局部调度线性规划模型；采用序贯博弈谈判机制协调总预算的合理分配，以实现多项目总延期成本的*小化。本书利用优化软件CPLEX求解小规模算例的精确解，得到*优目标值，即目标值的下界；分别探索设计了基于随机搜索策略、2-opt（两元素优化）策略以及混合启发式策略的序贯博弈谈判算法以求解大规模算例总预算的协调分配问题，并嵌入CPLEX求解局部权衡问题。本书改编基准问题库中不同规模的多项目算例并开展实验研究。研究结果表明：由于信息的不对称性，分布式决策得到的多项目总延期成本值不小于集中式决策的目标值，且增加总预算、延长项目截止日期以及降低活动边际成本均能有效地减少多项目的总延期成本损失；小规模问题利用CPLEX和基于随机搜索策略的序贯博弈谈判算法求解，能够得到精确的*优结果，采用基于2-opt策略的序贯谈判算法可以快速得到大规模问题的较优结果，而采用基于混合启发式策略的序贯博弈谈判算法能够得到各种规模问题的*佳求解效果。