（系统工程专业论文）考虑施工设备租赁的项目调度问题研究.pdf

i 华 中 科 技 大 学 硕 士 学 位 论 文 摘要摘要 工程建设中施工设备的租赁费用、运输费用、安装费用在工程总成本中占有一 定的比例。在项目调度的过程中，合理地安排需要施工设备的活动执行顺序能有效 地降低工程建设项目的总成本。 本文研究了施工设备租赁对工程建设项目成本和活动执行顺序的影响。通过分 析工程建设中的施工设备租赁费用、施工设备的安装费用、施工设备的运输费用、 项目的持有成本、项目提前完工的奖金和延期完工的罚金等项目总成本因素，建立 了考虑施工设备租赁的项目调度问题的混合整数规划模型，并对模型中施工设备的 资源约束、活动关系、工期底线等约束条件进行了分析。针对此问题，提出了基于 优先规则的串行调度求解方法，设计了几个比较合理的优先规则，经工程实例测试， 对算法的有效性进行了验证，并对模型中活动持有成本系数、罚金系数、奖金系数 等相关参数进行了灵敏度分析，讨论了各参数变化对项目总成本的影响。 结合实际的工程项目背景，本文考虑了工程建设中施工设备的租赁费用，建立 了此类项目调度问题的数学模型，提出了有效的启发式求解方法，在实际工程建设 中具有一定的应用价值。 关键字：关键字：工程建设，项目调度，设备租赁，项目总成本，混合整数规划， 串行调度方案，优先规则 ii 华 中 科 技 大 学 硕 士 学 位 论 文 abstract rent, transition cost and setup cost of equipment share a certain proportion of the total project cost in construction project. in project scheduling, it can effectively reduce the total cost of construction project by scheduling the activities, which should be executed with help of equipments, in a reasonable order. the effect of equipment renting on the total cost and schedules of activities in construction project is discussed in this thesis. firstly, items in the total cost, rent, setup cost, transition cost of equipments, holding cost of project, rewards for early completion and penalty for delayed completion are analyzed respectively. secondly, project scheduling problem with equipment renting is modeled as a mip model where constraints such as capacity of equipments, relationship among activities, due date of project are included. thirdly, a priority-rule based serial scheduling schema is proposed to solve the above problem and some reasonable priority rules are designed. finally, the results of the numerical experiments on an illustrative example project shows the effectiveness of the approach and sensitivity analysis of parameters, like activities cost coefficient, penalty coefficient, reward coefficient in the model is made to find how the total cost of construction project will be affected by those parameters. with the demand from construction project, project scheduling problem with equipment renting which considers the objective of minimizing the total cost including rent for equipment is discussed and an effective heuristics for this problem is proposed which has practical significance in actual construction projects. key words: construction project, project scheduling, equipment renting, total cost of project, mixed integer program, serial scheduling schema, priority rules 独创性声明 本人声明所呈交的学位论文是我个人在导师的指导下进行的研究工作及取得的 研究成果。据我所知，除文中已标明引用的内容外，本论文不包含任何其他人或集 体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文 中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。 本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密，在_年解密后适用本授权书。 本论文属于 不保密。 （请在以上方框内打“”） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 1 华 中 科 技 大 学 硕 士 学 位 论 文 1 绪论绪论 在现代经济社会，企业进行生产的主要目标是追求利润。为了使企业的利润最 大化，各企业都会采取各种措施，像调整生产流程，改进工艺等技术，来尽量减小 生产中的各种成本，达到企业利润最大化的目的。 在工程建设中，由于工程建设的特殊性，在项目的开展过程中，往往需要各种 不同类型的、价格昂贵的施工设备。像在南水北调中线工程中的穿黄段，就需要盾 构机，由于目前国内还没有掌握盾构机的自主研发技术，如果从国外进口，每台的 价格近千万美元，因此就采用租赁的方式，大概每台每天的租金在一万人民币左右。 因此，在工程建设中，施工设备的租赁费用占项目总成本的一定比例。如何安排工 程建设中的施工设备工作计划，来减小工程建设的成本，增加利润，成为项目管理 人员的重要任务。本章先介绍选题的目的、意义，接着介绍施工设备的研究现状以 及资源受限项目调度问题的求解算法，最后介绍了本文的章节安排。 1.1 课题来源课题来源 本课题来源于以下的项目：水利部南水北调中线管理局的“机电设备管理子系 统” 。目前该子系统已经开发完毕，并且在南水北调中线工程中得到使用。作者参与 了该系统的研发工作，并在系统的实施过程中，了解了许多施工设备如盾构机是如 何进行调度的。 1.2 课题的提出、研究的目的及意义课题的提出、研究的目的及意义 在研究生阶段，作者先后参与了一些实际项目，如“南水北调中线工程机电设 备管理子系统” 、 “二滩物资管理决策支持子系统” ，这些管理系统都是服务于和支撑 工程建设的，在项目的按期完工和成本管理方面都起到了重要的作用，也在一定的 程度上达到了节约工程建设成本的目的。 2 华 中 科 技 大 学 硕 士 学 位 论 文 在实际工程建设项目中，经常会出现下面问题：在工程建设项目的开展中，需 要用到许多不同类型的特殊、昂贵的施工设备，造成工程建设的成本很高。在满足 项目工期的前提下，项目承包商需要考虑项目中各活动之间的逻辑关系和各种不同 类型的特殊、昂贵的设备的数量限制，并且在满足其它方面的资源约束的前提下， 处理好活动、设备以及设备和活动之间的调度顺序，以达到在满足项目工期的要求 下， 工程建设项目的总成本(包括施工设备的租赁费用、 安装费用、 运输费用等)最低。 因此，本文的研究目的是：考虑施工设备租赁的工程项目调度问题中，在满足 项目的工期底线约束和施工设备种类约束的条件下，使工程建设的总成本最低。 考 虑 施 工 设 备 租 赁 的 项 目 调 度 问 题 属 于 资 源 受 限 项 目 调 度 问 题 (resource-constrained project scheduling problem，rcpsp)，是项目调度问题中的一 类研究问题。考虑施工设备租赁的项目调度问题需要在同时满足项目活动间的时序 关系约束、项目的工期底线约束、施工设备类型和设备数量等约束条件下，合理的 调度项目中的各活动，达到项目管理者所需要的某种管理目标最优的目的，因此比 一般的项目调度问题更难得到问题的最优解，是 np-hard 组合优化问题中的一种。 在现代市场经济条件下，在工程建设的各个阶段中所需要的设备等资源往往处 于不断变化的状态，如设备的保养、原材料的消耗等。而世界市场的竞争越来越激 烈，为了让各工程承包商有更强的竞争力，就不得不在有限的资源条件下，减小企 业生产的成本，这就对承包商的要求越来越高。承包商比较关心项目的进度、质量、 成本。因此，如何有效的在工程建设中，合理的安排各施工设备的工作计划，达到 减小项目成本的目的，就成为承包商关心的主要问题，所以，研究考虑施工设备租 赁的项目调度问题，在理论上和实践上都具有重要的意义。 理论上，关于资源受限项目调度问题的模型和求解算法等研究成果很多，如关 于项目工期最小、净现值最大化等问题的模型和算法已经非常丰富，已经有一些关 于工程建设设备问题方面的研究，但大多集中在设备的采购、分配等方面，很少有 关于考虑施工设备租赁的项目调度问题的研究。所以研究考虑施工设备租赁的项目 调度问题，具有一定的理论研究意义。 在实践中，考虑施工设备租赁的项目调度问题广泛存在于工程建设项目中，是 3 华 中 科 技 大 学 硕 士 学 位 论 文 工程建设中常见的一类生产调度问题。面对去年爆发的全球经济危机，我国有 1500 亿元用于铁路、公路、水利等重大基础建设设施中，占刺激经济投资总额的 3.75%。 在市场经济体制下，以利润最大化为目的的今天，承包商对项目成本的要求越来越 高。研究考虑施工设备租赁的项目调度问题，就是要在工程按期完工的条件下，合 理的安排施工设备在活动中的执行顺序，达到节约项目成本的目的。因此研究考虑 施工设备租赁的项目调度问题，具有非常重要的实践意义。 1.3 文献综述文献综述 1.3.1 工程建设设备问题的研究现状工程建设设备问题的研究现状 在工程建设中，专家所做的决策通常是不精确的或含有一定的不确定性，因此， 采用线性规划，利用工程建设环境中的不精确的信息，是很难得到最优决策的。在 具有不确定性的条件下，确定工程建设所需设备的数量一般采用模糊线性规划。 eshwar 和 kumar 采用模糊数学，确定了具有确定工期的工程建设项目中所需要的 施工设备最优数量1。 yeo 和 ning 主要是解决工程建设设备采购管理的不确定性2。作者组合了供应 链管理和关键链管理的技术，提出了一种扩大的关键链管理模型来管理工程建设中 大型设备采购管理中的不确定性，这种模型把不确定性没有单纯的看作一种威胁， 而是看作一种减小施工设备采购时间的机遇。 manavazhi 和 adhikari 通过统计，确定了尼泊尔的地铁工程中施工设备采购延 迟发生的概率，并且评估了这种延迟对地铁工程的总成本的影响3。 从上面的文献综述可以看出，目前关于工程建设设备研究主要集中在设备的采 购管理、设备在工程建设中的分配等问题上，很少有关于考虑施工设备租赁的项目 调度问题的研究，因此，考虑施工设备租赁的项目调度问题，在理论上和实际应用 上，都具有一定意义。 4 华 中 科 技 大 学 硕 士 学 位 论 文 1.3.2 资源受限项目调度问题的产生资源受限项目调度问题的产生及求解算法及求解算法 项目是由活动组成的，活动在执行的过程中，不仅受到工期的约束，像最早完 成时间、最晚完成时间等，还要受到资源的限制。因为在大多数工程项目中，由于 资源的价值过高(如地铁施工中的盾构机)而不可行或者资源的数量是有限的(如人力 资源)。 因此， 如何在满足各种约束条件下， 利用有限的资源来达到工程项目的目标(如 项目的总工期最短、工程的总费用最小等)，成为项目管理的一个重要问题。 关键路线法(cpm)被广泛的应用在工程建设项目中描述活动网络，但是，这种方 法有它们自己的缺点。cpm 网络的一个缺陷就是它不能用图形来描述完成一个项目 中所需要的各种资源。正是由于这种方法不能有效的处理受到约束的资源，所以根 据这种方法编制的计划往往不能满足实际的需求，这就产生了资源受限项目调度问 题(resource constrained project scheduling problem, rcpsp)。 精确算法和启发式算法是求解资源受限项目调度问题的两类方法。精确算法主 要包括这些方法：枚举法4、分支定界法5等。 由于精确算法主要用于求解活动数目不超过 60 的小规模问题，当活动数目更大 时，解空间呈指数增大，因此求解困难。对于大规模的资源受限项目调度问题一般 采用启发式算法以及后来产生的现代启发式算法求解。调度产生方案和优先规则是 启发式算法不可缺少的两个部分6，调度产生方案分为并行和串行调度产生方案。后 来又出现了被称为现代启发式算法的算法，如模拟退火7、禁忌搜索8、遗传算法9 等。下面详细介绍精确算法和启发式算法。 1) 精确算法 用于求解资源受限项目调度问题的精确算法主要是枚举法与分支定界法。 talbot 和 patterson 提出了一种枚举法10。他们把项目中的所有活动按照活动的 优先关系列举。 接着把所有的活动从时间 t=0 向后迭代和按照项目的工期底线向前迭 代，来驱动时间窗的进行。johnson 提出了只有一种资源约束的资源受限项目调度问 题的枚举法11。在此基础上，stinson 提出了宽度优先的分支定界法1213。这种算法 中的枚举树的每一个节点代表一种可行的部分调度方案。 5 华 中 科 技 大 学 硕 士 学 位 论 文 demeulemeester 和 herroelen 在 christofides 提出的深度优先的分支定界基础 上，提出了新的算法14,15。和 stinson 的宽度优先的分支定界不同之处主要在于枚举 数上，宽度优先的分支定界中新的节点是考虑已经调度的活动的集合，而他们的方 法是采用延迟集合的方法。延迟集合采用两种方法删减枚举数：一种是左移一步方 法变化而来的，另外一种是采用“替代集” ，替代集中的活动是当前还没有调度的， 但是其紧前活动都已经调度了，成为了部分调度集合。 brucker 应用从工作车间问题中得到的启发， 得到了一种新颖的算法16。 他们为 工作定义了四种不同的关系：(1) 连接关系：指工作之间满足紧前紧后关系约束的； (2) 分离关系：指不同的工作由于资源冲突而不能并行的执行；(3) 并行关系：指不 同的工作至少在一个工作时段内能同时进行的。(4) 可行关系：不满足以上所有分类 的工作。mingozzi 利用一种新的数学公式推导出了一种新的下界和枚举模式17。这 种方法采用了可行集合的概念。所谓可行集合指：这些活动不满足时序关系约束， 但是活动所需要的资源的总和没有超过每种资源的供应量。 doersch 和 patterson 引进了二进制整数规划来求解净现值最大化项目调度问 题18。这种规划模型为项目中活动之中的费用引入了现金约束，这导致了随着活动 执行过程中得到的现金，可用的现金也随着增加。smith-daniels 在 doersch 和 patterson 提出的数学模型的基础上，引入了原材料约束和成本19。因此，项目的净 现值最大化问题受到原材料和资金约束。 tavares 提出了一种新的解决方法，通过对一些互相联系的项目进行变分法得到 优化结果20。目标函数是求下面费用的最大值：随着项目进行产生的纯利润的一部 分、项目总支出中的一部分，由于项目延期完成造成的罚金。这种动态规划已经在 葡萄牙的一项大型铁路工程建设中得到了成功的应用。 patterson 等人提出了 0-1 规划模型和一种求解资源受限项目调度中的净现值最 大化问题的逆向算法21。 这种算法的特别之出在于它也能用于求解工期最小化问题。 其核心思想是：工期最小化问题比净现值问题容易求解的多，因此可以用它带有现 金流右移一步的启发式算法得到初始可行解。baroum 和 patterson 为净现值最大的 项目调度问题设计了一种分支定界法22。yang 等在 talbot 和 patterson 的基础上， 6 华 中 科 技 大 学 硕 士 学 位 论 文 为净现值目标问题设计了一种新的求解算法23。 icmeli 和 erenguc 利用延迟替代集的概念提出了一种求解带有现金流的资源受 限项目调度问题的分支定界法24，这种方法的优点是能很快的减少分支数。 2) 启发式算法 (1) 求解最小化工期问题的基于优先规则的启发式算法分为以下几类： 基于优先规则的启发式算法 这种算法由两个部分组成：调度产生方案和优 先调度规则25。可行的调度产生方案可以分为两类：并行和串行的调度产生方案。 在每一个阶段，调度产生方案都形成能调度的活动的集合，即决策集合。而优先调 度规则则是从决策集合中选择一个即将能调度的活动。并行调度方案的可行调度活 动集合是这样定义的：在当前所有没有调度的活动中的紧前活动已经被调度的活动 集合；并行调度方案的决策集合是这样定义的：满足资源约束的，并且紧前活动已 经被调度，在当前调度时段内能开始调度的活动集合。这两种调度方案都最多要进 行 n 次反复迭代(n 是项目中活动的个数)。 基于分离弧的启发式算法 这种算法采用了 balas 用来解决工作车间的思想 26。基于分离弧的基本思想是在时序关系(连接弧的集合)的基础上，增加了分离弧， 这就导致了由于资源限制而不同同时调度、在技术上独立的活动集合的这种禁止的 关系被破环，产生了由于时序约束和资源约束的不能在最早完工时间的调度也是可 行的。 现代启发式算法 这种方法都是把解决方案编码为一个长度等于活动数目的 列表。这个列表通过采用上面所叙述的优先规则能转换为项目的调度方案。 kohlmorgen 等人扩展了最初用在求解工作车间问题的算法27，他们在资源受限项目 调度问题中采用局部搜索算法。 (2) 求解净现值最大化问题的启发式算法分为以下几类： 优化指导方法 这种方法开始于 russell 研究用启发式算法求解净现值最大的 资源受限项目调度问题28。他采用来自求解无资源限制的净现值最大问题和工期最 小化问题的观点，形成了 6 种不同优先规则的启发式算法。 基于参数的方法 smith-danels 和 aquilano 通过比较用最晚-开始关键路线 7 华 中 科 技 大 学 硕 士 学 位 论 文 调度和最早-开始关键路线调度求解工期和净现值问题29，得到了这种方法。这种方 法基于下面的假设：现金流出发生在每个时段的开始，而单一的工程支付在工程项 目完成后才能得到。 现代启发式算法 现代启发式算法在最近几十年才得到广泛、成功的应用。 icmeli 和 ermeli 在一种简单的单通道算法中采用禁忌搜索算法30，产生了一种可行 的调度。在初始解的基础上，通过在活动的完成时间不会破环活动的最早、最晚完 成时间约束的前提下，把当前的完成时间内把每个活动一次向前或向后移动一个单 位时间，可以改善初始解。 在适应策略成功的应用在复杂的路由和生产问题的促进下， zhu 和 padman 采用 多种启发式组合来求解项目调度问题31。他们采用六种随机优先规则来处理项目调 度问题中的不同方面，如资源约束和活动网络拓扑图来调度活动。基本的假设在于： 通过大量的反复迭代后，启发式采用的规则会改变项目调度中的相关约束。 1.4 本文的研究方法及章节安排本文的研究方法及章节安排 1.4.1 本文的研本文的研究方法究方法 考虑施工设备租赁的项目调度问题实质上属于资源受限项目调度问题，因此， 本文在研究资源受限项目调度问题的数学模型和算法的基础上，通过分析考虑施工 设备租赁的项目调度问题的成本组成，提出考虑施工设备租赁的项目调度问题数学 模型，并给出了问题的求解算法，最后运用一个工程实例来证明了模型的合理性、 算法的正确性，并对相关参数进行了灵敏度分析。 1.4.2 本文章节安排本文章节安排 本文章节安排如下： 第一章给出了本文在研究中需要的相关背景知识。在阅读文献的基础上，介绍 了工程建设设备的研究现状，并介绍求解资源受限项目调度问题的精确算法和启发 8 华 中 科 技 大 学 硕 士 学 位 论 文 式算法，最后介绍了本文的章节安排。 第二章将在介绍了项目管理相关概念的基础上，介绍描述项目调度的活动网络 图，重点描述资源受限项目调度的分类；分析考虑施工设备租赁的项目调度中产生 的各种费用，并运用资源受限项目调度的相关理论与方法建立相应的数学模型。 第三章介绍考虑施工设备租赁的项目调度问题的求解算法。采用基于优先规则 的启发式算法得到活动的调度方案和施工设备的工作时序，在满足各种约束条件的 基础上，达到考虑施工设备租赁的工程建设项目总成本最小的目的。 第四章将给出考虑施工设备租赁的项目调度问题的一个具体实例，并用第三章 介绍的启发式算法求解，分析模型的求解结果，并且将对相关参数进行了灵敏度分 析。 第五章将对本文进行总结，针对本文的不足之处，提出以后的研究方向。 9 华 中 科 技 大 学 硕 士 学 位 论 文 2 考虑施工设备租赁的项目调度问题建模考虑施工设备租赁的项目调度问题建模 考虑施工设备租赁的项目调度问题属于资源受限项目调度问题一种特例，它除 了具有资源受限项目调度问题的特点以外，还有自身的特点。它的约束条件是项目 工期、时序和设备数量等约束条件。目前关于工程建设设备的研究主要集中在设备 的采购管理、设备在工程建设中的分配等问题上。在工程建设中考虑施工设备租赁 问题的研究很少。 本章先介绍了项目调度问题的组成，接着介绍了描述项目调度问题的活动网络 图，最后根据求解目标的不同，对资源受限项目调度问题进行分类，确定了本论文 研究的问题所属类别；并在分析施工设备租赁的项目调度问题的基础上，对考虑施 工设备租赁的项目调度问题进行建模。 2.1 项目调度问题项目调度问题 项目调度问题由活动、资源、活动间的紧前紧后关系组成32。这三个元素是任 何项目调度问题不可缺少的部分。下面分别介绍这三个部分。 2.1.1 活动活动 活动是项目的基本组成元素。在有些文献中活动也称为任务、工作等32。为了 成功的完成项目，活动必须采用某种模式完成。模式决定了活动的持续时间(完成活 动所需要的时间)、所需要的资源的种类、数量。 2.1.2 资源资源 按照资源的种类进行分类，活动中所用的资源可以分为不可重用资源 (nonrenewable)、可重用资源(renewable)、双重受限资源(double constrained)和部分可 重用资源(partially renewable) 32,33。 上面每种类型的资源都有一个量，即活动中使用的每种资源的种类、数量都是 10 华 中 科 技 大 学 硕 士 学 位 论 文 有限的，不可能无限制的为工程建设供应，本文所研究的考虑施工设备的项目调度 问题中的资源属于可重用资源(主要是施工设备)。 2.1.3 紧前紧后关系紧前紧后关系 通常，由于技术上的原因，有些活动必须在其它一些活动完成之后才能开始， 这就导致了活动之间在时间上有先后关系。在工程项目中，经常采用活动网络图来 描述项目中各个活动之间的紧前紧后关系。活动网络图在后面的章节介绍。 2.2 活动网络图活动网络图 活动之间相互制约或相互依赖的关系叫做活动之间的逻辑关系34。活动的这种 逻辑关系可以分为施工组织关系和施工工艺关系33，这两种关系在活动网络图中表 现为活动的先后关系。 在工程项目中，单代号网络图和双代号网络图已经被广泛地用来描述项目中的 活动，产生了基于事件和基于活动的活动网络。单代号网络图和双代号网络图34都 是由箭线、节点、代号组成。下面详细的介绍这两种活动网络图。 2.2.1 单代号网络图单代号网络图 节点、箭线、代号是单代号网络图(activity-on-arc)的三个组成元素34。图 2.1 是单代号网络图。 代号 活动名称 持续时间 2 b d2 1 a d1 图 2.1 单代号网络图示例 11 华 中 科 技 大 学 硕 士 学 位 论 文 1) 节点 节点可以用圆圈或方框表示，如图 2.1 用圆圈表示节点。节点在单代号网络图 中表示活动。圆圈或方框里写上活动名称、代号、持续时间以及其它的时间参数等。 2) 箭线 单代号网络中的箭线表示活动之间的紧前紧后关系。紧前活动、紧后活动在单 代号网络图分别表示为箭尾节点、箭头节点。箭线不占用任何资源，也不消耗时间。 3) 代号 为了在单代号网络中区分所有的活动，所以一个活动只能有唯一的一个用正整 数表示的代号。 2.2.2 双双代号网络图代号网络图 和单代号网络图一样，双代号网络图(activity-on-node)也是由节点、箭线、代号 组成的34。 1) 箭线 与单代号网络图不一样，活动在双代号网络图中用箭线表示，由于活动的执行 需要消耗资源和时间，所以一条箭线表示一项活动的全部内容。活动名称或内容写 在箭线的上面，持续时间写在箭线的下面。箭尾事项表示活动的开始，箭头事项表 示活动的结束。箭线的方向表示活动的执行方向。 2) 节点 与单代号网络图一样，双代号网络图也是用圆圈表示节点的。在双代号网络图 中，节点表示两个活动的连接点，它的意义是：只有前一个活动结束后，后面的活 动才能开始，同时节点不消耗时间和资源。双代号网络中的节点编号也必须用正整 数表示。 并且箭头节点的编号要小于箭尾节点的编号。 图 2.2 是双代号网络图的示例。 12 a d1 图 2.2 双代号网络图 12 华 中 科 技 大 学 硕 士 学 位 论 文 2.3 活动活动网络图网络图的的时间参数计算时间参数计算 活动作为项目的基本组成元素，它的持续时间、开始时间、结束时间等参数直 接影响项目的工期,上面介绍的两种网络图只能表示项目中各个活动执行的先后顺 序。在实际工程建设项目中，还需要知道每个活动的最早、最晚开始时间，最早、 最晚结束时间。因此在实际项目中，确定活动的持续时间和时序关系之后，可以绘 制出网络图，从而确定活动的各种时间参数以及关键路线、关键活动，为网络计划 的优化、调整做准备34。下面给出双代号网络图的时间参数的计算公式，在给出计 算公式以前，先定义各种时间参数： 1) 活动 j 的持续时间，即活动 j 从开始到结束所经历的时间，用 j d表示；2)活 动 j 的最早开始时间，即活动 j 的所有紧前活动结束后，活动 j 能开始的最早时间， 用 j es表示；3)活动 j 的最晚开始时间，即在不影响项目的计划完工工期的前提下， 活动 j 能开始的最晚时间，用 j ls表示；4)活动 j 的最早结束时间，与最早开始时间 相关的参数，用 j ef表示；5.活动 j 的最晚结束时间，与最晚开始时间相关的参数， 用 j lf表示34,35。 由于受到活动间紧前紧后关系的约束，双代号网络图中的活动是按时间先后顺 序分布的，因此，计算最早时间的时候必须从起始节点开始，沿着箭线的方向逐个 活动进行计算，直到终止节点为止。 假设项目的第一个活动编号为 1， 则活动 1 的最早开始时间为 1 0es ， 设( )p j为 活动 j 的紧前活动集合，|( ) j stesjp j表示活动 j 的紧前活动集合中，各个活 动的开始时间集合，|( ) j ddjp j表示活动 j 的紧前活动集合中，各个活动的持 续 时 间 的 集 合 。 则 活 动j的 最 早 开 始 时 间 为 max jj esd， 其 中 , ( ) jj esst dd jp j。 活动 j 的最早完成时间为活动 j 的最早开始时间加上其持续时间。因此，活动 j 13 华 中 科 技 大 学 硕 士 学 位 论 文 的最早完成时间为() jj esd。 由此可以得到项目的工期，即项目中活动最大的最早完成时间。假设项目中最 后的一个活动的编号为 n，则项目完工工期为max n def。 最晚开始时间和最晚结束时间的计算步骤和计算最早时间不一样，计算最早时 间是从项目的开始活动开始的，是正向计算的，但计算最晚时间是逆向的，从项目 的终点开始的逐项计算的。因此必须计算紧后活动的最晚时间后，才能计算本活动 的最晚时间参数34，具体的计算步骤如下： 除去网络图中终点节点的其它活动的最迟完成时间为其紧后活动中最迟开始时 间的最小值34，设 j s为活动 j 的紧后活动的集合，且| jj lflfjs为活动 j 的紧 后活动的集合中所有活动的最晚完成时间的集合，则活动 j 的最晚完成时间为： min jjj lflfd，( )js j (2.1) 活动 j 的最迟开始时间为该活动的最晚结束时间减去该活动的持续时间，即： jjj lslfd (2.2) 2.4 项目调度问题的项目调度问题的分类分类 这里根据项目中可能用到的多种不同的资源、活动执行的多种模式，通过阅读 文献，给出了一个通用的资源受限项目调度模型，并根据不同的参数，进行了分类， 下面先给出了资源受限项目调度的数学模型32。 假设一个项目由 n 个活动组成，不失一般性，在该项目中加上两个虚拟活动(既 不消耗资源，也不占用时间)0，n+1，活动 0 表示仅有的一个最早开始活动，活动 n+1 为仅有的一个最晚结束的活动。项目中的各个活动应该满足相关的紧前紧后约 束。( )p j表示活动 j 的紧前活动集合，( )s j表示活动 j 的紧后活动集合，活动 j 的持 续时间(执行时间)被表示为 j d。 集合r、r分别表示可重用资源、不可重用资源集合。活动 j 在其持续时间内 14 华 中 科 技 大 学 硕 士 学 位 论 文 消耗的可重用资源 k 的资源量表示为 jk r ， k r表示资源 k 的资源总量。在多模式项目 中， j m表示处理活动 j 的模式的集合。在模式 m 下，活动 j 的持续时间表示为 jm d， 活动 j 消耗的可重用资源 k(不可重用资源 k)的量为 jkm r ( v jkm r)，同时 v k r表示整个项目 工期内第 k 不可重用资源的数量。 如果 t l表示可行的时间调度集合， r l表示可行的资源调度集合，则 tr lll表 示可行的活动调度的集合。 brucker 等人提出了一种对资源受限项目调度问题的分类的三段标记法： | 6。现在扩展这种分类方式，针对具体的问题来刻画模型。 :表示资源环境：为了区分特殊的设备调度问题和项目调度问题，引入了 ps(ps,project scheduling ,项目调度)或者是mps(multi-mode project scheduling, 多模式项目调度)， ps问题能扩展到, ,psm ，在考虑到不可重用资源和多模式项 目调度问题时，可以表示为, , ; , .mpsm 。 , , ; , ,mpsm 的具体含义如下：m 表示多模式项目调度，这种调度需要 m 中可重用资源，每种可重用资源的数量为，每个活动消耗的可重用资源量最多为 ；同时需要种不可重用资源，每种资源的数量为，每个活动消耗的可重用资源 量最多为。如果, , ; , ,m 被代替，则所有的参数在输入的时候确定14。 ：表示活动特性：像用 j d表示活动持续时间，prec表示一般的活动间的优先 关系；temp表示活动间一般的最小最大开始时间间隔限制。 ：目标函数：即资源受限项目调度问题的求解目标。根据所查阅的文献资料， 目前资源受限项目调度问题的研究目标可以分为以下几类636： 1) 最小项目工期问题 这类问题是目前项目调度问题领域研究的最多的，也是最广泛的，也是资源受 限项目调度问题的核心问题。最小化项目的工期就是求项目中最晚结束活动的最早 15 华 中 科 技 大 学 硕 士 学 位 论 文 完成时间。也就是求终止活动的最早完成时间。一般来说，在求解项目的最小工期 问题的时候，必须考虑到活动的紧前紧后关系约束和项目所受到的资源约束。 2) 净现值最大化问题(net present value maximization) 当综合考虑项目开始和随着项目的进行而不断投入的现金和项目完工后的收益 的重要影响的时候，就诞生的净现值最大化问题。由于净现值体现了项目的优劣程 度，因此，净现值准则是一种更适合刻画项目绩效的方法。 3) 质量目标问题(quality maximization) icmeli 和 rom37是第一个详细考虑项目调度中的质量目标问题的。他们38通过 在全美国范围内调查后提出了项目调度中质量最大化问题。 4) 成本最小化目标(cost minimization) 由于成本管理也是项目管理的三大目标之一，因此在实际项目中，成本目标更 加具有实际意义。所以这类问题也受到许多研究团体的研究。成本最小化目标问题 可以分为两类：(1) 活动成本；(2) 资源成本。 活动的执行方式像开始时间、活动执行的模式直接影响活动的直接费用。有很 多以活动成本为目标的例子，像时间-成本优化问题。时间费用优化问题就是在满足 项目的工期的约束下，找到活动的持续时间与活动成本之间合理的均衡，使项目的 总成本最小。活动的持续时间可以分为连续的和离散的。近代许多研究都集中在把 多模式下的资源受限项目调度问题和时间-成本均衡问题一起讨论，这就产生了压缩 模式下的多模式资源受限项目调度。这种问题的目标是使组成项目成本的各种活动 成本最小化，如果项目在工期计划完工日期时间还没有完成，将产生由于项目没有 按时完成的罚金，罚金与拖延的工期有关。 另外的一种成本是资源成本。在以资源成本为目标的调度问题中，项目活动的 调度影响项目的间接成本。资源成本问题可分为资源水平问题和资源投资问题。资 源投资问题的成本是与项目中需要的资源的数量的成本相关的。 考虑施工设备租赁的项目调度问题中主要的资源是施工设备，属于可重用资源， 并且施工设备的种类和数量是一定的；活动的执行方式采用单模式执行，活动之间 的时序关系为一般的紧前紧后关系，即活动在其紧前活动完成之间不能开始；优化 的目标是：工程建设的总成本最小。因此，按照上面介绍的资源受限项目调度问题 的分类方式，本文研究的考虑施工设备租赁的项目调度问题属于：单模式下的项目 16 华 中 科 技 大 学 硕 士 学 位 论 文 调度问题，每种施工设备的数量是 1，优化的目标是项目的总成本最小。 2.5 考虑考虑施工施工设备租赁的项目设备租赁的项目调度问题调度问题 2.5.1 问题特点问题特点 考虑施工设备的项目调度问题属于资源受限项目调度问题的一种特例，它除了 具有资源受限项目调度问题的一般特点外，本文所研究的考虑施工设备的项目调度 问题具有独特的特点，具体如下： 1) 考虑施工设备的项目调度问题具有明确的工期底线和项目完工日期，即工程 建设项目必须在工期底线以前完成，如果在项目完工日期以前没有完成的，需要支 付工程延期完工的罚金，反之就会得到工程项目提前完工的奖金。 2) 考虑施工设备的项目调度问题主要研究的是活动和施工设备之间的关系，本 文研究的主要是工程项目调度问题，施工设备的种类和数量是约束条件。 2.5.2 成本分析成本分析 在给出考虑施工设备的项目调度问题的数学模型以前，先考虑一个基本的需要 一种施工设备的调度问题：该调度过程只需要一种施工设备 i 来执行活动，其中活动 j、r 需要施工设备 i 来完成,活动 k 不需要施工设备 i 参与。并且 j 是 k 的紧前活动， k 是 r 的紧前活动，施工设备调度模型如图 2.3。 活动j 活动k 活动r闲置 设备租赁 场所 图 2.3 施工设备调度模型简图 有闲置时间的设备调度过程 三个活动的时序关系 没有闲置时间的设备调度过 17 华 中 科 技 大 学 硕 士 学 位 论 文 从图 2.3 通过分析，得到如下的施工设备过程： 1) 施工设备从租赁场所出来，被用来执行活动 j，然后闲置在工作场所，直到活 动 k 完成后，再参与活动 r 的执行。在这种调度方式中，只需要把施工设备从租赁场 所运到活动地点一次，然后要么闲置，要么用来执行活动。并且在这种调度方式中， 产生了一次施工设备安装费用(施工设备从租赁场所到活动地点的运输费用计算在安 装费用里面)，闲置费用，所以设备的利用率很低。 2) 施工设备从租赁场所出来，在执行完活动 j 后，把施工设备运回租赁场所， 直到活动 k 结束后，再把设备运到工作地点执行活动 r。在这次调度中，需要安装费 用两次，但是没有闲置费用。 通过上面的施工设备调度过程，可以得到考虑施工设备的项目调度问题，会产 生以下费用： 1) 施工设备租赁费用 施工设备是工程建设中必不可少的资源，只要工程建设项目的进行，就需要各 种施工设备。这里假设处理活动所需要的施工设备都是采用租赁模式，因此需要支 付施工设备的租赁费用。同时假设一台施工设备同一时间只能处理一个活动，如果 某一活动需要某一施工设备才能开始，则这台施工设备会从该活动开始，一直到活 动结束才能离开，并且这台施工设备在工作期间不能被其它的活动占用。 2) 运输费用 指的是把施工设备从一个活动地点运送到另外一个活动地点所用的费用。施工 设备的运输费用可能会影响需要施工设备的活动的先后时序关系。 3) 安装费用 这里指把施工设备从租赁场所运送到活动地点的费用以及为活动开始而做准 备、调试设备的费用。 4) 活动持有成本 活动持有成本的概念相当于库存持有成本的概念，把在每一阶段完成的活动的 价值的百分比作为工程成本的一部分。 5) 工程的奖金或者罚金 18 华 中 科 技 大 学 硕 士 学 位 论 文 在资源受限工程建设项目中，由于有些资源的数量是有限的，会导致有些活动 延期开始，因此可能会导致项目延期完工。为了刻画这种工程项目提前完工和延期 完工对工程建设项目成本的影响，就引入提前完工的奖金和延期完工的罚金。如果 项目延期完工，就会受到罚款；如果项目提前完工，就会得到奖金。因此把工程的 奖金或罚金作为工程的总成本，能够在一定的程度上保证工程按期完工。 6) 闲置费用 指由于施工设备闲置在活动地点，没有参与任何活动的执行，而支付的施工设 备的租赁费用。考虑到施工设备闲置时也需要支付租赁费用，可以考虑把施工设备 送回租赁场所，等到活动需要施工设备的时候，再调度施工设备，这时只需要支付 安装费用。因此，在工程建设中，需要全面考虑施工设备的安装费用和施工设备的 租赁费用。 通过分析上面的考虑施工设备的项目调度问题中产生的费用，可以得到考虑施 工设备的项目调度问题的目标就是让上述各种费用的总和最小，即施工设备的租赁 费用、工程提前完工的奖金、工程延期完工的罚金、施工设备的运输费用、施工设 备的安转费用及活动的持有成本总和最小。 2.6 考虑考虑施工施工设备设备租赁的项目租赁的项目调度调度问题的数学模型问题的数学模型 假设一项工程建设项目包含着 j 项活动,这 j 项活动一共需要 i 种不同的施工设 备，每种不同类型的施工设备的数量只有一台。在这里，每种施工设备是可重用资 源，即在处理完一个活动后，可以用来处理下一个活动。对于项目中的每一个活动， 都只有唯一的一种工作模式。由于组织上及技术上的要求