第 1 章 绪 论
1.1 课题背景
近年来，基于对全社会用电量未来走势的乐观估计，国内电源建设速度持续高涨。仅 2016 年上半年，我国新增发电装机 5699 万千瓦，同比多投产 1360 万千瓦。中电联预计，2016 年全年，全国基建新增发电装机 1.2 亿千瓦左右，其中非化石能源发电装机7000 万千瓦左右，煤电 5000 万千瓦左右。在如此大规模的投资建设活动中，有效的对电力工程项目进度进行管理可以使项目早日投产运行并产生效益，同时还能很好地减少资金占用。而合理的项目进度计划是有效进行进度管理的前提和保证。因此如何在施工过程中编制与优化施工进度计划，以实现均衡施工，达成工期最短具有重要的现实意义。电力工程建设项目的进度计划的编排工作是一个复杂的过程, 不仅要满足项目各项工序之间的紧前紧后关系，同时还要满足项目资源供给方面的限制，而且最终形成的调度方案还要兼顾合同工期的限制和资源投入的均衡性。在目前的进度管理实践中，一种方法是使用关键路径法（CPM）或计划评审技术（PERT）编排出满足工序间逻辑关系的最短工期，然后再依据类似工程的经验或一般性技术方案的资源投入计划将产生资源冲突的并行工序调整为串行工序以形成合同工期。以后再由项目执行单位依据自身条件编排竞争性计划、指导性计划以及实施性计划。每一层深入的过程中都要在更加具体的资源限制条件下满足上一级计划的关门工期。在这一过程中管理者始终处于工期与资源投入的权衡中，即加大资源投入以缩减工期还是延长工期以避免资源的脉冲式使用造成的浪费，最终实施方案的优劣比较依赖项目执行单位的技术经验水平。另外一种方法就是借助于资源受限项目调度问题（Resource-ConstrainedProjectSchedulingProblem,RCPSP）研究平台。资源受限的项目调度问题是调度问题的一个重要分支，也是项目管理领域的核心内容。众多学者已提出了丰富的模型和不同的求解算法。为了找到适合电力建设工程项目进度计划编排的模型，需要对该类工程施工过程中表现出的独特性进行深入分析。经过调研，电力建设工程项目的特点有：首先，电力建设工程工艺复杂，单位工程、单项工程、分部与分项工程，甚至到每个工序都要执行严格的质量与安全验收程序，并且工序之间的逻辑联系非常繁杂，因此编制进度计划过程中要应对更大的排序强度（Order Strength，OS）；第二，电力建设工程投资大，技术复杂，建设周期长，任务节点数多。这导致问题规模巨大，其模型与算法求解难度凸显；第三，电力建设工程配套设备与物资多。一般来说电力建设工程中物资采购成本能够占到总工程造价的 60%左右，而且品类多、数量大。不可更新资源约束种类多。且某些构配件与设备的提供存在时间窗；第四，配合建设企业较多，各种工作专业技术性强，分工复杂需要多部门多单位协作建设，不同的单位有各自的工作日历。这使得可更新资源种类多，且遵循不同的工作日历；第五，建设企业能力不同，工作执行模式会有多种；第六，为避免可更新资源的脉冲式使用，需对工作进行合理拆分。
............
1.2 国内外研究现状
关于项目调度问题的研究可以追溯到 20 世纪 50 年代。这个多学科交叉的领域吸引了来自运筹学、应用数学和工程技术方面专家的注意，线性规划、整数规划、动态规划、目标规划等运筹学中的决策方法得以应用到项目进度计划的编排与优化的工作中从而使这方面的研究取得了巨大进展，解决了多项困扰人们已久的问题。Conway、Maxwell和 Miller 几位学者在项目调度方面的研究工作[1-3]目前被公认为项目调度理论研究的始点。此后不久，计划评审技术[4]和关键路径法[5]被大量地应用在项目进度计划编排问题当中，在假设资源供给没有限制的情况下求解项目的最小工期。然而由于实际工作中，每项工作的进行都面临着诸如人员、材料、机械等各种资源的限制，因此研究者们开始深入研究在有资源限制的情况下如何规划工期。在 JohnsonTJR[6]首先提出资源受限项目调度问题（RCPSP）的概念以前，该问题还有其它多种称谓，如项目网络的资源分派（resourceallocationinprojectnetworks）[7]、项目规划的资源分派（resource allocation in project planning）[8]、带资源约束的项目调度（projectschedulingwithresourceconstraints）[9]、带有限资源的项目（projectswithlimitedresources）[10]。也有诸多学者对 RCPSP 问题的研究进行了详细的总结与梳理[11-13]。经过多年的发展，针对 RCPSP 问题的研究越来越深入，根据所带约束条件不同，可以划分为多模式 RCPSP(MRCPSP)、一般 RCPSP、广义优先关系 RCPSP(RCPSP-GPC)、多目标 RCPSP、任务可拆分的 RCPSP (或者 PRCPSP)、动态 RCPSP。总体来说都是要求在满足工序间时序约束与资源约束的前提下，明确所有工序的开始时间和完成时间，从而达成某些目标的最优化，比如总工期最短，综合成本最小，资源投入均衡等。此类问题属于 NP-hard 问题，求解困难。在经典的 RCPSP 问题模型中，资源供给水平维持恒定，但这一假设显然对模型在实际问题当中的应用设置了障碍，因为现实中各种资源的可获得性在很多情况下会不断地发生变化。为了解决此矛盾，一种思路是运用模糊网络计算的思想进行多目标优化[14]，而另一种思路就是使用工序拆分的技术来达到均衡资源的消耗和缩短总工期的双重目的。这就引出了任务可拆分的 RCPSP 问题。对于这种任务拆分技术的优势与劣势已经有很多学者进行了深入的探讨。
........
第 2 章 项目进度编排理论基础
本章以进度计划编排的步骤为切入点，然后逐步阐述在计划编排各步骤中涉及到的基本理论与概念。对于一个工程项目来说，进度目标十分重要，以建设电厂为例，一个120 万千瓦的发电厂，每提前一天发电，就可生产 3000 万度电，可创造利润数十万元。但进度目标也是与质量、成本、安全等目标相互制约、相互联系的，忽视其他方面而制定的调度方案，往往不能取得预期的效益。所以说在进度计划的编排阶段就需要统筹考虑几个方面的均衡控制，才能达到项目的正常运行。
2.1 进度计划编排的步骤
项目进度计划是对项目工作时间、活动开展顺序、空间布局以及资源配置的具体策划和统筹安排，是项目管理的基础性指导文件，也是进行项目进度控制的重要依据。针对项目的特点，科学合理的安排进度计划，控制活动时间，对保证项目按期完成、节约成本起着重要的作用。虽然可以根据不同的标准将进度计划分为不同的类型，但管理人员在编制任何完整的进度计划时都基本遵循相同的逻辑和步骤，主要包括以下几方面：（1）信息资料收集阶段要编制出科学合理的项目进度计划,就首先要广泛收集可靠的原始数据,作为进度计划编制的依据。其中比较重要的数据包括项目范围管理资料、项目合同条件、项目执行单位、各参建单位专业技术人员数量和技术水平、与拟建工程类似的已完工程进度计划资料以及此类工程各阶段的定额规定等等。这些资料是后续工作中工序划分、工序逻辑关系确定、工序执行模式选择、工序执行时长计算的重要依据，关系到进度计划编排的成败。（2）项目工作分解通常采用自上而下的层次分离法建立 WBS 模型，综合考虑项目的组成、项目进度计划系统类型、项目进展的总体部署以及项目执行单位的组织形式等情况,逐步将复杂的项目分解成若干相互关联的详细工作。通常要分解到满足底层单元的最小分项或检验批，以作为进度计划编制时的基本工序。例如，变电站土建工程-安装工程-主变压器安装-主变压器的芯部检查-附件安装。
.......
2.2 工作分解结构与工序定义
项目工作内容的分解过程通常采用工作分解结构方法，然后才能进行后续的工作。工作分解结构（WorkBreakdownStructure，简称 WBS）是最早由美国国防部提出的[49]，是一种用来定义项目和整合项目的范围管理工具。进行这项工作的目的是为了方便管理而将庞大的项目分解成较小的各项可交付成果。这种以可交付成果为导向对工作进行的层级分解，是合理、高效地完成项目进度计划编排的基础。WBS 作为项目进度管理中的一项重要工具，其优势在于：第一，工作分解结构可以使进度计划的编制者对项目全局有所把握，由于其结构严谨所以不会出现丢项或者重复的工序；其次，工作分解结构还展现了各项工序之间的相互联系；另外，管理人员可以方便地在工作分解结构中指定和标示项目中的里程碑事件，从而方便对项目整体进度的掌控。工作分解结构的表达形式一般为表格形式或者树状的层次结构图。同一项目的分解方法也可以根据秉持原则的不同而有所区别。比如可以根据项目的组成部分进行划分，也可以根据项目承发包的合同结构划分，或者参考管理单位的组织结构划分等等。建立 WBS 模型也要遵循几项基本要求：（1）某项任务的内容是其子项目工作任务内容的总和。（2）一个 WBS 项有且仅有一名负责人，但不排斥采用多人参与的原则。（3）在所建立的项目结构图中，一项工作任务有且仅有在一个地方出现的权限。（4）编制的 WBS 既可以保证项目工作的正常进行，也可以适应所能够遇见范围内的变更。（5）为使工作范围内的任务精准执行，要文档化所有的 WBS 项。（6）WBS 的执行方式与实际工作中保持一致。当分解至为完成各种项目可交付成果所必须进行的具体活动时，我们将其称之为工序。通常，每项工序有其预计的时间、成本和所需的资源。
..........
第 3 章 电力工程项目进度计划编排模型研究...........22
3.1 资源受限项目调度问题模型.......22
3.2 资源受限项目调度质量的评估..............23
3.3 传统资源均衡与工序拆分的研究方法.............24
3.4 工序拆分优化工期的原理...........26
3.5 非占先工序拆分.....27
3.6 电力工程项目进度计划编排模型的建立.........30
3.7 本章小结......34
第 4 章 电力工程项目进度计划编排问题求解算法..............35
4.1 基于优先级的分支定界法...........35
4.2 剪枝搜索策略.........37
4.3 本章小结......39
第 5 章 实例研究....40
5.1 测试集的选择.........40
5.2 测试集的改进.........42
5.3 测试集算例优化结果统计分析..............43
5.3.1 工期得到优化的案例比率...........43
5.3.2 优化幅度......44
5.4 某电力工程项目进度计划编排实例......44
5.5 本章小结......48
第 5 章 实例研究
本章采用仿真研究对项目进度计划编拍中采用非占先工序拆分与采用占先工序拆分两种情况的效果进行对比。首先对国际 RCPSP 研究领域通用的 PSPLIB 测试集进行了改进，以使测试集数据能够模拟电力建设工程项目中资源供给水平随时间变化这一特点。然后生成案例，并分别采用前文所建立的允许工序进行占先拆分的情况（P1）、只允许非占先拆分的情况（P2）和不允许进行工序拆分（P3）三种情况下的模型分别进行求解，接着对三种模型的求解结果进行了统计和对比。最后，根据某电力建设工程实际调研数据生成一个实例，计算并分析了不同工序拆分情况下的调度方案。使用 java 编程对文中所提的基于优先级的分支定界法进行实现，在主频为 2.3GHz 的四核 CPU、内存 8GB的计算机上运行，操作系统为 Windows10。
5.1 测试集的选择
相对于任意的占先工序拆分而言，非占先工序拆分所产生的条件比较苛刻，因此这种拆分在调度方案当中出现的数量会比较少。那么为了验证这种数量较少的工序拆分能否对调度方案的优化起到作用以及能够起到多大的作用；以及它的优化效果与能够任意拆分工序的调度方案差距会有多大这样的问题就需要选择合适的测试问题集来进行算例研究。国际 RCPSP 研究领域目前已经有了很多通用的测试集，设计这些测试集的初衷是为了测试和比较各种求解算法的性能。最早的经典资源受限响度调度问题测试集是由PattersonJ[21]设计并首先使用的，因此被命名为 Patterson 问题集。此案例集中包含了 110个案例，并且为了适应各种不同类型行业的研究，在设计之初就吸收了多种来源的调度问题实例。但这也同时造成了它不能有规律地反映影响项目调度的各种可能性的问题。另外，相对于其它测试集来说这个问题集当中的案例比较容易使用精确求解算法解算。随着软件技术的发展，一些学者将测试集开发成为随机问题生成器来弥补原测试集的不足之处。比如 DemeulemeesterE[52]等人尝试设计了最原始的调度问题生成器，使用这款软件设计案例时仅能够设定项目工序间的逻辑关系和项目工序总数，其它诸如资源系数、网络图复杂程度等参数均为默认值。为了适应研究需要，Kolisch R 等[20]在参考这种软件的基础上加入了更多的可调节参数，形成了通用性更强的 ProGen 问题集生成器（可以在网址 http：//129.187.106.31/psplib/进行下载）。ProGen 不仅可以构造单模式的资源受限项目调度问题，还可以生成多模式的资源受限项目调度问题。以 J30，J60，J90 和J120 四个基本问题集为基础，通过调节网络复杂度 NC、资源系数 RF、资源强度 RS 和工序节点数等几个参数可以模拟来自不同行业的问题，实现多种多样的研究目的。
..........
结论
资源受限项目调度问题既是项目管理领域的核心研究内容，同时也是调度问题的一个重要分支。好的项目调度方案可以缩短工期，节约资源，提高效率，获得更多经济利益。因此这个多学科交叉领域一直是国际上的一个研究热点。众多学者提出了丰富的模型和各种不同算法。本文的研究从实践出发，针对电力建设工程项目的特点，结合知识工程、项目管理理论、运筹学理论，提出了一种新的应用工序拆分技术求解项目进度计划编排问题的方法。本文的主要贡献可以归纳为以下几点：
（1）针对阻碍工序拆分技术在工程实际中应用的主要问题，即拆分代价难以量化的问题，找到了一种不会导致出现占先惩罚的工序拆分方法（非占先工序拆分），并给出了非占先工序拆分的详细定义。然后构建了相应的形式化数学模型，并设计了基于优先级的分支定界法对其进行求解。
（2）对国际 RCPSP 研究领域中通用的 PSPLIB 测试集进行了改进，使其能够模拟电力建设工程的特点。在 NC、RF、RR 三个传统参数之上又加入了 RR 和 RV 两个参量，使之存在可更新资源的波动和资源空窗期。
（3）通过算例分析对占先工序拆分与非占先工序拆分两种工序拆分模式在调度方案优化中起到的作用进行了量化研究。生成的案例分别用允许工序进行占先拆分的情况（P1）、只允许非占先拆分的情况（P2）和不允许进行工序拆分（P3）三种情况下的模型分别进行求解。并且根据对计算结果进行的统计分析。
..........
参考文献（略）