基于机动时间的可分解平行工序顺序优化研究

平行工序的顺序优化是解决资源有限项目进度计划问题的最有效、最普遍的方法之一。对于该类问题的研究目前主要基于工序的不可分解性,而现实情况下有些工序是任意可分的。基于此,本文首先提出了最小路长定理,在其基础上,建立了任意可分的两个平行工序调整为顺序工序的亏值模型,并进行了理论证明,此外,针对从n个可分解平行工序中选取一个与指定工序调整为顺序工序的优化问题进行了研究,在已给亏值模型的基础上设计出了优化算法,越是大型网络,该方法的优越性越明显。     

基于整数规划强对偶求解一类局域性资源受限项目调度问题

资源受限项目调度问题(简称RCPSP)是最具代表性的项目调度问题之一,调度过程可理解为,将受资源约束的平行工序调整为顺序工序。本文针对实际中广泛存在的资源局域、而非全局受限的情况,研究局域性RCPSP,并重点考虑一类问题：项目某环节的一系列平行工序,可用资源量只有一半,各资源可重复利用且具有相应多功能,但最多能承担2个工序,需将这些工序两两排列成对,实现项目工期最短。本文首先探索问题“局域性”特征,量化局域调度对项目工期的影响;基于此,构建只涵盖“局域调度工序”的0-1规划模型;再者,发展整数规划强对偶理论,结合Dangzig-Wolfe分解等方法,提出多项式时间的精确算法;最后通过算例测试,验证算法优势,例如,计算大规模算例的最优解,运用该算法比常规精确方法可快数万倍以上。     

甲供资源约束条件下南水北调工程项目群工期-费用优化模型研究

在研究项目群工期—费用优化问题时，首先剖析了项目群工期—费用优化机理。然后建立了甲供资源约束条件下项目群实施前的工期—费用优化模型，对初始网络计划进行优化，使业主支付款净现值最小。但由于项目群中各合同项目间存在资源竞争和工期冲突等矛盾，可能引起某一合同项目的工期延误。基于此，构建项目群实施过程中的工期—费用优化模型，对实施前优化后的网络计划进行动态调整。最后结合南水北调某X项目群对比了不同工期—费用优化下的结果。结果显示：两阶段的项目群工期—费用优化可实现项目群的费用控制目标，为项目经理确定项目群中各合同项目的起始时间提供依据。     

计及软逻辑的重复性项目离散时间费用权衡及其约束规划模型研究

在重复性项目中,如果一个工序适用软逻辑,则其在所有单元上的子工序可以任意改变施工顺序;当雇佣额外工作队后,同一工序中的多个子工序甚至可以同时执行。考虑软逻辑的重复性项目离散时间费用权衡问题(DTCTP-RPSL)旨在确定每个工序的执行模式、工作队分配方案和单元间的施工顺序,从而在满足给定截止日期条件下最小化项目总费用。已有研究均采用遗传算法求解此问题。但是,遗传算法属于启发式方法,不能保证解的最优性。本文首先建立了描述DTCTP-RPSL的混合整数线性规划(MILP)模型,然后从约束规划(CP)角度提出了求解此问题的CP模型。该模型以区间变量定义每个子工序,并利用CP表达式强迫所有变量在可行域内取值。与MILP模型相比,CP模型在保证解最优性的同时,减少了变量和约束的规模,提升了求解效率。数值实验表明,CP模型的性能优于MILP模型和遗传算法,能够在短时间内求出小规模和中等规模问题的最优解,以及较大规模问题的高质量解。     

多资源约束下基于关键链的项目群工期-费用优化

现有工期压缩模型未考虑资源约束下多合同项目工期压缩所产生的局部效应与整体效应,针对这一局限性,通过引入子网络,分析了基于关键链法的项目群工期—费用优化机理,据此,对项目群初始网络计划进行工期优化。借助关键链,除去计划工期的冗余时间,动态调整存在资源冲突的合同项目开始时间。在此基础上,分析工期动态优化对关键链和非关键链合同项目压缩费用产生的不同影响以及对子网络自身和项目群的影响。基于此,研究并构建了多资源受限下单一子网络和项目群工期-费用优化模型。最后,结合算例,分析了优化模型的可行性和优势。研究结果表明：模型能够有效地解决资源约束下项目群计划调整和工期-费用优化问题,从而能够为业主科学安排项目群中各合同项目的起始时间和资源计划提供依据。     

地域分散型多项目时间/成本权衡问题

实践中多项目可能分散在不同的地域，制订多项目计划时全局资源在项目间的转移时间不能忽略；项目活动有不同的执行模式，投入的预算越多，活动工期越短。地域分散型多项目时间/成本权衡问题涉及总预算在项目间的合理分配、全局资源在项目间的转移以及预算约束下的项目工期优化问题。针对该问题特点设计一种遗传算法，对带有预算约束的局部项目调度问题进行求解，采用序贯博弈谈判机制协调总预算在多项目间的分配并制订全局资源转移计划。基于多项目标准算例集MPSPLIB开展实验研究，一方面，探究求解该问题的序贯博弈谈判机制的协调效果；另一方面，分析并讨论问题规模、资源冲突强度和总预算对全局目标值的影响。     

基于鲁棒优化模型的项目调度策略遗传算法

针对任务工期不确定的资源受限项目调度问题,提出了求解该问题的鲁棒优化数学模型。在随机规划基础上,针对该鲁棒优化模型设计了遗传算法。算法通过多种任务优先规则生成初始种群以保证种群多样性。应用该遗传算法对项目实例进行了求解,分析表明所求得的项目调度策略能够有效应对任务工期不确定性导致的随机差异,具有较强的鲁棒性。参数分析表明决策者可以通过调节模型权重系数有效平衡解的可行性与最优性,有助于决策者根据风险偏好进行选择。     

活动重叠模式与资源约束下的项目调度优化

采取活动重叠模式通常是加速研发的有效手段,带有活动重叠的资源受限项目调度问题是经典资源受限项目调度问题的扩展.首先,深入分析了活动重叠对于项目调度的影响,对活动重叠及其不确定进行详细描述与建模,提出了活动重叠导致下游活动返工时间的二项分布概率模型;其次,构建了以最小化研发项目期望工期为目标的优化调度模型,设计了基于串行进度生成机制的遗传算法对大规模问题进行优化求解;最后,基于PSPLIB J60问题库中480个算例分析了该算法的计算结果,并考察了网络参数、资源参数和重叠参数变化时,采用活动重叠模式对缩短项目工期的影响.研究结果表明:活动对资源的需求强度越小或资源稀缺程度越低,可重叠活动对数量就会增加,项目工期缩短得越明显;网络复杂度的变化对缩短项目工期的影响不大;项目中重叠活动对越多,重叠导致的下游活动返工的概率越小,项目工期缩短的越明显.     

基于逆控制工序的重复性项目最短工期计算方法

最短工期问题是重复性项目调度中的一类常见问题。本文首先根据不同类型控制工序工期与总工期之间的变化关系,提出并证明了总工期的计算公式,给出了逆控制工序存在的必要条件。然后提出了最短工期问题的优化策略,即只需对所有满足逆控制工序必要条件的工序系进行执行模式的选择,而其余工序系直接选择最快执行模式。最后以该策略为基础设计了新的遗传算法。算例分析表明,与现有的其它算法相比,极大地简化了计算量,提高了计算效率。     

GPRs条件下时间-费用权衡问题的初始最优解

求解时间-费用权衡问题时,特别是在确定项目的最优时间-费用曲线时,首先必须找出初始最优解,即费用最低的总工期,然后在该解的基础上,用最低的压缩费用将总工期逐步缩短。在工序之间只有严格优先关系下,各工序的费用最低的工期就是初始最优解。但是当工序之间存在一般优先关系(简称GPRs)时,各工序都选用费用最低的工期往往无法满足既定的优先关系,使得项目不可行,因此必须考虑其它费用较高的工期,并且在时间约束范围内使得总费用最低。所以求解GPRs条件下时间-费用权衡问题的初始最优解是一个项目调度问题。针对该问题,首先,通过分析GPRs及其表示方法的特点,建立了该问题的数学模型;其次,通过对该模型进行对偶变换,将其等效转化为产销平衡的运输模型。运用已有的相关算法能够简便有效地求得该模型的最优解,并跟据初始-对偶关系可求得原问题的最优解。     

基于资源流网络优化的Max-npv项目调度

活动拖期通过资源流网络的传递会严重影响项目的净现值收益。针对该问题，本文首先在确定性环境下采用模拟退火算法(SA)构建了Max-NPV(Maximize the Net Present Value)非鲁棒性基准调度计划，然后考虑到活动工期的不确定性，设计了MEPC(Minimize Expected Penalty Cost)资源流网络优化算法，通过鲁棒性资源分配实现净现值期望惩罚成本最小化。大规模仿真对比实验结果表明，在活动工期低、中、高三种不确定性程度下，相对于采用随机资源分配算法(SA+RRAS)构建的非鲁棒性调度计划，SA+MEPC算法构建的鲁棒性调度计划在项目净现值实际收益、调度计划的“解”鲁棒性和“质”鲁棒性三个方面都取得了更好的结果，并且应对活动拖期风险的能力也更强。     

基于拍卖机制的资源转移时间型动态分布式多项目调度

实践中,企业并行实施地域上分散的多个项目时,资源在各子项目之间的转移时间是影响多项目整体进度的关键因素,同时在动态多项目环境下,新项目不断到达且到达时间不可预知使得制定多项目调度计划遭遇更大困难。本文在动态环境下对资源转移时间型分布式多项目调度问题进行建模和求解,基于多代理系统建立分布式多项目调度问题的动态模型,并将拍卖理论引入其中,设计一种基于时间窗拍卖机制的分布式多代理系统(DMAS/ATW),在动态环境和资源转移时间约束下为多项目配置全局资源。通过一个具体的分布式多项目示例详细分析DMAS/ATW算法的动态调度过程,并基于MPSPLIB中的分布式多项目算例开展数值实验。实验结果表明：无资源转移时间约束时,DMAS/ATW算法求得的平均项目延迟同比相关文献中的DMAS/RIA算法最多减少42%,平均减少26%;有资源转移时间约束时,DMAS/ATW算法对1/3算例集的求解结果优于DMAS/RIA算法在无资源转移时间约束时的结果,验证了本文DMAS/ATW算法求解效果的优异性。对算例规模和全局资源利用系数的实验分析还表明,DMAS/ATW算法对不同规模和资源约束紧张程度的算例都具有良好的适应性。     

An adjustable robust optimization model for the resource-constrained project scheduling problem with uncertain activity durations

This paper addresses the resource-constrained project scheduling problem with uncertain activity durations. An adaptive robust optimization model is proposed to derive the resource allocation decisions that minimize the worst-case makespan, under general polyhedral uncertainty sets. The properties of the model are analyzed, assuming that the activity durations are subject to interval uncertainty where the level of robustness is controlled by a protection factor related to the risk aversion of the decision maker. A general decomposition approach is proposed to solve the robust counterpart of the resource-constrained project scheduling problem, further tailored to address the uncertainty set with the protection factor. An extensive computational study is presented on benchmark instances adapted from the PSPLIB.     

具有时间转换约束的离散时间-费用权衡问题研究

离散时间-费用权衡问题(DTCTP)是项目进度中研究最多的双目标优化问题,它通常以三种形式出现:(1)P1:截止日期问题,在项目截止日期约束下使完成项目的总费用最小;(2)P2:预算问题,在费用预算约束下使项目工期最短;(3)P3:工期-费用曲线问题,找出全部有效的工期-费用模式集合。然而,考虑时间转换约束(TSC)的DTCTP却很少被关注。本文首先介绍时间转换约束的问题描述,在此基础上,建立具有活动类型时间转换约束的DTCTPTSC-P2模型;从实用角度出发,设计求解模型的遗传算法;最后,用一个真实项目实例说明模型的合理性和算法的有效性,对算例分析结果表明,该模型对承包商更准确地进行项目工期-费用权衡决策具有借鉴意义。     

基于图的广度搜索的进度生成机制

启发式算法是解决资源受限的项目调度问题的经典方法之一，通常用来生成元启发算法初始解，传统的串行（SSGS）和并行（PSGS）是生成项目调度方案的经典机制，本文基于图的广度优先搜索算法，提出了一种考虑任务节点位置因素的广度生成机制（BSSGS），并验证了算法的效果。借鉴广度搜索算法定义进度生成机制中的当前任务集合C、候选任务集合D以及阶段变量g等，对各任务节点进行层次划分并定义任务调度秩序；结合优先规则选择候选任务j^*并进行资源R_k（t）调度更新，进而生成完整的调度方案；案例分析表明新机制在满足优先规则和资源约束的同时兼顾了任务节点在网络中位置因素，拥有对于局部复杂网络不回避，对关键节点及时调度等明显优势；选择PSPLIB中算例，在不同优先规则下对新机制进行了测试，测试结果表明新的进度生成机制在LPT、SPT、MTS和MIS等优先规则下，在平均最短工期、平均资源利用率及最优调度方案率等方面优于串行和并行进度生成机制，且算法时间复杂度与传统机制相比并未增加，仍为O（J²，K）。     

Robust Resource Allocation Decisions in Resource‐Constrained Projects*

The well‐known deterministic resource‐constrained project scheduling problem involves the determination of a predictive schedule (baseline schedule or pre‐schedule) of the project activities that satisfies the finish–start precedence relations and the renewable resource constraints under the objective of minimizing the project duration. This baseline schedule serves as a baseline for the execution of the project. During execution, however, the project can be subject to several types of disruptions that may disturb the baseline schedule. Management must then rely on a reactive scheduling procedure for revising or reoptimizing the baseline schedule. The objective of our research is to develop procedures for allocating resources to the activities of a given baseline schedule in order to maximize its stability in the presence of activity duration variability. We propose three integer programming–based heuristics and one constructive procedure for resource allocation. We derive lower bounds for schedule stability and report on computational results obtained on a set of benchmark problems.     

基于柔性资源约束的前摄性项目调度优化研究

不确定环境中，项目进度计划鲁棒性的高低直接影响项目能否顺利实施。本文研究了具有随机活动工期的柔性资源约束下的前摄性项目调度优化问题，目标是在柔性资源和项目工期的约束下，借助对活动开始时间合理的进行安排进而得到拥有最大鲁棒性的进度计划。首先对研究问题进行界定；随后构建优化模型，并根据问题NP-hard属性和模型特点设计了双层嵌套禁忌搜索启发式算法，通过内外两层交互搜索寻找满意解；最后通过一个实际案例对本文研究进行说明，并分析关键参数对进度计划鲁棒性的影响，得到如下结论：相对于资源无柔性情况下的项目进度计划而言，资源具备柔性后得到的项目进度计划的鲁棒性更高，具有更强的抗干扰能力，能够保证项目稳定执行；同时，项目进度计划鲁棒性分别随着项目工期的延长、资源可用量的增加或资源柔性的提高而上升。