《基于活动成本目标的资源受限多项目进度计划》由会员分享，可在线阅读，更多相关《基于活动成本目标的资源受限多项目进度计划（51页珍藏版）》请在金锄头文库上搜索。
1、华中科技大学 硕士学位论文 基于活动成本目标的资源受限多项目进度计划 姓名：郑彦琦 申请学位级别：硕士 专业：系统工程 指导教师：陈学广;刘振元 20070604 华 中 科 技 大 学 硕 士 学 位 论 文 I 摘 要 资源约束下的项目调度问题(Resource Constrained Project Scheduling Problem, RCPSP)，要求在满足项目任务的紧前关系和资源约束的条件下，优化项目的进度安 排，从而最小化项目工期。很多经典的调度问题，例如flow shop 、job shop等调度 问题，一定程度上都可以看作是RCPSP的特例。如果进一步扩展RCPSP，考虑多
2、个 相互独立的并行项目，同时这些项目又共享设备、场地或人力等有限资源，就产生 了资源约束下的多项目调度问题。在实际工程作业中，并行多项目进度计划是调度 的前提和重要组成部分。 然而，资源约束下的项目调度问题中很少关注活动成本目标，问题中以活动成 本最小化为目标时也是一类 NP-Hard 问题。 在对该问题进行分析的基础上，考虑活动的单执行模式，本文建立了活动成本 最小化单目标的多项目进度计划数学模型。其中，模型描述了各项目活动的紧前紧 后约束、可重用资源约束以及工期约束，并在单项目中应用到的基于优先规则的启 发式算法的基础上进行了改进。针对活动成本目标，挑选了几个较为合理有效的优 先规则，提出
3、了一个适合该目标的多项目进度计划的启发式算法，并给出了算法步 骤，分析了该算法的时间复杂性。通过具体算例的验证，MATLAB 仿真得到的进度 计划说明该模型是可行和有效的，并且该算法可以得到可行解。 本文结合多项目的背景来研究活动成本目标下的资源受限工程项目进度计划， 对推进活动成本目标的工程调度研究及其应用具有积极意义。 关键词关键词：项目进度计划 资源受限 多项目 活动成本 优先规则 华 中 科 技 大 学 硕 士 学 位 论 文 II Abstract Resource-constrained project scheduling problem (RCPSP) is to optimi
4、ze the scheduling of projects and minimize the project due-date under the requirements of the activities with precedence relationship and the constraints of resources. Many classic scheduling problems, such as flow shop, job shop and etc., can be seen as special cases of PCPSP. If PCPSP is expanded,
5、 considering a number of independent parallel projects as well as limited resources such as equipments, venues, human resources shared by those projects, a resource-constrained multi-project scheduling problem can be created. In practical engineering operations, parallel multi-project scheduling is
6、the premise of the problem and its important component. There is little attention paid to activities cost of project in resource-constrained project scheduling problems (RCPSPs). When considering the objective of minimizing activities cost, the problem is also NP-hard. Based on the analysis of this
7、issue, a mathematical model is put forward for the cases the activities are executed in single execution mode. The mathematical model describes the single objective, minimum activities cost of a multi-project, considering the activities with precedence relationship, renewable resource constraints an
8、d due date constraints. A heuristic algorithm given in my paper was proposed to solve this problem. The proposed algorithm expanded and enhanced the original heuristic scheduling algorithm based on priority rules. According to the objective of the model, some more reasonable and effective priority r
9、ules for a multi-project heuristic scheduling algorithm was selected; the algorithm and its time complexity was described. Through the validation from a concrete example, the MATLAB simulation results showed that the model is effective and the algorithm is a feasible solution. The issue researched t
10、he resource constrained project scheduling problem based on project activities cost objective with multi-projects background. It must play a positive and significant role to promote the research and its application for project scheduling based on activities cost objective. Keywords: project scheduli
11、ng, resource constrain, multi-project, activities cost, priority rules 独创性声明独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到，本声明的法律结果由本人承担。 学位论文作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有
12、权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密 ，在_年解密后适用本授权书。 不保密。 （请在以上方框内打“” ） 学位论文作者签名： 指导教师签名： 日期： 年 月 日 日期： 年 月 日 本论文属于 华 中 科 技 大 学 硕 士 学 位 论 文 1 1 绪论 1.1 课题来源 本学位论文所开展的研究工作来源于以下的科研项目： (1) 二滩水电开发有限公司投资招标的 “雅砻江物资管理工程调度系统” 。 目前， 该系统已
13、经基本完成了物资供应，物资转运，物资调拨，物资在途等管理模块的功 能开发。 (2) 华中科技大学科学研究基金：项目调度与原材料订货集成优化问题的研究。 1.2 课题的提出、研究的目的及意义 2006年7月至今，作者或参与或了解到许多项目背景，如“三峡工程散装水泥/ 粉煤灰实时调运指挥系统”，“龙滩工程物资设备实时调运指挥系统”等，都属于 是工程建设期间服务的生产运行指挥系统，在保证工程建设的质量和进度方面都起 到了十分关键的作用，并产生了重大的经济效益和社会效益。 结合工程建设的实际，可以将以上问题推广到一般情形，即：大型的工程涉及 到多个项目的并行实施， 项目管理者需要充分考虑各资源(可重用
14、)能力的约束和项目 工期底线的约束，合理地优化各项目的调度顺序，从而达到工程建设的目标要求。 其中最直接最明显的就是经济效益，即最小化项目活动成本目标。这里的项目活动 成本包括静态的活动固定成本和动态的活动完工持有成本(包括保险、维护、保养费 用等)。 一般情况下， 资源约束下的工程调度问题(Resource-constrained project scheduling problem, RCPSP)，要求在满足项目活动的紧前关系和资源约束的条件下，优化项目 的进度安排， 从而最小化项目工期。 很多经典的调度问题， 例如Job Shop、 Flow Shop、 串行和并行调度等问题，都可以看作
15、是RCPSP的特例。如果进一步扩展RCPSP，考 虑涉及多个相互独立的项目，但这些项目之间又存在对共享资源的竞争，就产生了 资源约束下的多项目调度问题。 华 中 科 技 大 学 硕 士 学 位 论 文 2 资源约束下的多项目调度问题是一类重要的问题，因为在现实情况下，组织经 常同时开展多个相互联系的项目，但企业资源往往处于变化状态，如人员的调动、 假期及硬件资源的耗损和增加等等，并且物料资源也是有限的，不可能所有的可执 行任务都能同时获得所需的资源。此外，随着全球网络化经济的发展，世界市场的 竞争变得越来越激烈，企业项目的规模也越来越大，对项目管理的要求也越来越高。 其中高达90%的项目都是在
16、多项目环境下执行的1。 因此，如何有效地合理调度项目，分配有限的资源就显得非常重要。众所周知， 项目的进度和其产生的经济效益向来是项目管理者最关心的问题，而且项目的进度 计划是项目调度的前提和重要组成部分，调度以进度计划为依据，进度计划通过调 度来实现，所以基于活动成本目标的资源受限多项目进度计划研究，在理论和实践 两个方面都有着重要的意义。 从理论上来说，在多项目调度领域研究中，研究成果虽然非常丰富，但是进度 计划大多都是基于缩短项目工期的，很少关注活动成本目标，存在一定的局限性， 所以基于活动成本目标的资源受限多项目进度计划研究将是多项目调度研究领域中 一个有益的补充。 从实践的角度来讲， 资源受限的工程调度问题广泛存在于建筑工程、 软件开发、
