计划评价与审查技术(Program Evaluation and Review Technique,PERT)是20世纪50年代中期发展起来的一种科学的计划管理技术,它是一种从任务的总进度着眼,针对任务的组织计划、任务的实施及其指挥调度,而把任务在完成过程中所采取的技术上和组织上的设想及其内在协同关系定量地描述出来,通过分析计算、优化处理以求对技术、人力、资金、物资等资源在需要和可能之间不断加以协调平衡的组织管理技术。计划评价与审查技术的核心是网络计划技术,在网络计划技术中最核心和最复杂的问题就是网络计划的调度优化问题,它决定了工程项目利润的高低。在长期的实践应用中,网络计划优化基本都采用了运筹学中的网络计划技术以及数学规划等方法,但是这些方法存在很多缺陷。遗传算法是一种并行的全局搜索的高效求解问题的方法,其本质上就是处理离散优化搜索问题的,它不要求问题空间的连续性,不需要梯度信息,其鲁棒性(Robust)已经得到了证实,在处理大型复杂优化问题上已经取得了显著的成绩,所以在解决较大规模网络计划的多目标综合优化问题时,具有其它方法无法比拟的优势。在计划评价与审查技术中,网络计划优化问题从优化问题分类的角度看是一个离散的组合优化问题。在长期的实践应用中,网络计划优化基本都采用了运筹学中的网络计划技术以及数学规划等方法,到目前为止,解决网络计划优化问题的典型方法有网络计划技术、分支定界算法、启发式算法、智能优化算法等。1.网络计划技术最常见的网络计划进度优化方法是2003年白思俊提出的强制缩短法,即采取措施使网络计划中的某些关键工作的持续时间尽可能缩短。目前关于工期进度优化方法的研究思路也集中于不断改进强制缩短法,力求在优化项目工期的同时,使所增加的额外成本最小。吴育华等学者提出了割集平行路线差额法解决工期优化的算法。刘津明运用“最大流最小截”理论研究了工期一成本非线性变化时工期优化的算法思路。随着现代信息技术的日益成熟,使用Management scientist等软件可以非常迅捷的求出基于上述强制压缩法进行进度优化的最优结果。2.分支定界算法分支定界算法是求解NP-hard问题的一种有效方法,其基本思想是利用搜索树将问题的解空间按照一定的规则分割成子空间(分支过程),再利用合理的定界方法排除那些不必再进行搜索的子空间(定界过程),实现缩小有效搜索空间的目的。3.启发式算法启发式算法主要有基于优先规则的启发式算法和采样算法。基于优先规则的启发式算法由两个要素组成:计划生成方案和优先规则。计划生成方案可分为串行调度方案(serialScheduling Scheme,简称SSS)和并行调度方案(Parallel Scheduling Scheme,简称PSS),两种方法都是对一个不完全计划进行扩展,直至生成一个完全计划。采样算法一般使用一种计划生成方案和一条优先规则。在调度过程中不直接使用优先权系数,而是根据优先权系数v(j)计算工作j被调度的概率φ(j),再根据φ(j)调度E_n中的工作。根据φ(j)计算方法的不同,采样算法可分为随机采样算法(Random Sampling,简称RS)、带有偏好的随机采样算法(BiasedRandom Sampling,简称BRS)和基于后悔值的随机采样算法(Regret-Based Random Sampling,简称RBRS)。4.智能优化算法近年来,模拟退火(Simulated annealing,简称SA)、禁忌搜索(Tabu Search,简称TS)和遗传算法(Genetic algorithm,简称GA)等智能优化算法在求解组合优化问题方面显示出了较强的能力,在求解网络计划优化方面也有了一些应用。针对网络计划优化的智能优化算法主要包括以下要素:(1)编码,按照某种对应规则与惟一可行调度计划相对应的一组代码;(2)解码,采用一定规则将编码转换为可行调度计划的过程;(3)初始解,采用其他方法得到的一组编码,对应初始的可行调度计划;(4)邻域解,一组编码经过一步特别定义的操作所能得到的所有新的编码的集合。其中尤以网络计划技术的应用最为广泛,但是这种基于直观推理和逻辑分析基础之上的传统方法存在着一定的缺陷。首先,它在解决网络计划优化中的各个问题时具有很强的针对性,不能同时解决多方面的问题;其次,它在处理工作繁多、逻辑复杂的问题时效率较低;同时,很多模型和方法都是基于很具体的某种类型的网络计划,而不能应用于所有的工程项目。因此当对于工作繁多、逻辑复杂的网络优化问题,传统的各种优化方法如线性规划的单纯形法,非线性的分枝定界法,动态规划法,各种启发式算法,填谷消峰法等,一般都无法承受其计算的复杂程度,并且优化的效果受到一定的限制,所以本文选择用遗传算法来研究网络计划优化问题。论文利用遗传算法对计划评价与审查技术中的优化问题进行研究,主要研究内容如下:首先,本文对项目调度问题的基本概念和研究现状进行了简要阐述;对项目调度问题的分类和数学模型进行了讨论;对遗传算法的有效性理论依据---模式定理和积木块假设进行了理论性论述。其次,本文详细论述了利用改进遗传算法对单项目网络计划调度优化问题进行了应用研究。1.对单项目网络计划中资源优化问题进行了研究,针对资源优化中的资源均衡和资源受限工期最短两个问题分别建立了遗传算法模型进行求解;2.研究了时间费用优化问题,针对时间与费用的两种常见关系——连续型和离散型,分别设计了对应的遗传算法优化方法;3.对时间、费用和资源三个目标,建立了一个多目标综合优化的遗传算法模型,用遗传算法对其进行综合优化。针对以上每个问题,本文分别举出了应用实例,对遗传算法的效果进行了验证。本文重点讨论了利用改进遗传算法对多项目网络计划调度优化问题进行了应用研究。1.对资源受限的多项目调度问题进行求解,建立了新的优化模型,提出了新的改进遗传算法优化方法,并与其它启发式方法进行了对比分析;2.提出了多项目的资源均衡优化的遗传算法方法;3.对时间和资源均衡两个目标建立综合优化模型进行优化,并结合应用实例,通过对结果的对比分析,证明本文所设计的算法的正确性与高效性。论文对每个方面的模型都进行了案例分析计算,分析和计算的结果不仅验证了模型的正确性、求解的高效性,还在一定程度上证明了模型的实际应用价值。本文基于改进遗传算法对计划评价与审查技术中的网络计划调度优化问题进行了研究,其中对单项目网络计划进行综合优化及对多项目网络计划进行时间和费用的优化是本文的难点,也是本文的创新之处。论文的主要创新如下:1.针对单项目网络综合优化问题,提出了利用改进的遗传算法进行综合优化的方法。结合网络优化问题自身的特点,提出了分阶段的综合优化模型。首先进行资源约束下的费用优化,然后进行资源均衡优化。资源约束下的费用优化方法将费用优化和资源有限时间最短优化方法进行了有机结合,在进化过程中前者为后者提供了工作的时间和资源信息以及选择个体的标准信息,后者为前者提供了资源的约束,使得费用优化过程中的每个个体都能够满足资源的限制,最终求出满足约束条件的最低费用。第二阶段主要进行资源均衡优化。从第一阶段得到工程的工期以及工作的时间费用等信息,采用工期固定、资源均衡优化的优化方法。实例证明,该方法能够在各个目标之间进行协调,取得较好的综合优化效果。2.建立了资源受限的多项目调度问题的模型,提出了利用混合遗传算法进行多项目调度优化的新方法。通过动态建立十字链表来存储各个项目中工作之间的相互约束关系,然后将所有项目的工作混合在一起进行编码。初始化分两部分进行,首先应用十多种比较常见的启发式方法,按照启发式规则来生成一部分染色体,然后应用完全随机选择的方法生成另外一部分染色体。遗传算子操作采用基于广泛搜索的交叉算子和集中搜索的基于邻域的变异算子,评价函数采用权重系数的方法将三个工期目标转化为一个加权目标对最终结果进行评价。选择算子采用比例选择法与最优保存策略相结合的方法。此方法克服了两层决策模型的某些不足,而且不需要在编制网络计划时通过添加虚工作将所有项目的网络计划图合并为一个。对比实验表明,此方法与其它15种启发式方法相比取得了较好的优化结果。3.提出了资源受限的多项目调度优化与资源均衡优化问题相结合的双目标优化方法。首先对网络计划中的资源分配问题进行了优化,该问题分为两种类型,一种是工期固定情况下的资源均衡优化,解决了多种资源均衡优化的问题;另一种是资源有限工期最短优化,在参考前人文献的基础之上,有效的用混合遗传算法求解了该问题。然后对网络计划中的费用问题进行了优化,针对费用优化中工作持续时间与费用的关系中常见的两种类型——连续型与直线型,分别给出了相应得遗传算法,优化结果表明,优化后不仅资源更为均衡,而且还节略了部分类型资源。