基于资源共享的延迟惩罚最小化的多项目调度优化.doc

《基于资源共享的延迟惩罚最小化的多项目调度优化.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于资源共享的延迟惩罚最小化的多项目调度优化何华1,2，何正文1,2，刘人境1,2(1.西安交通大学管理学院，陕西西安710049；2.过程控制与效率工程教育部重点实验室，陕西西安710049)摘要：对可并行进行的多项目调度问题进行定性描述，在共享资源的数量约束下，构建了以多项目延迟惩罚总和为目标函数的优化模型。鉴于问题的强NP-hard属性，为模型设计了迭代循环求解的启发式遗传算法。运用实际案例对研究进行验证，分析关键参数对合同双方项目收益的影响，得到如下结论：与实际进度安排相比，满意进度安排下承包商因延期完工而遭到来自于业主的罚款数额出现了明显的下降；业主的单位

2、延迟罚款费用、共享资源池中的资源数量也会影响承包商对项目的进度安排，并对双方的项目收益产生重要影响。关键词：RCMPSP项目调度；延迟惩罚；资源共享约束；优化模型；遗传算法中图分类号：C935；F224.33文献标识码：A1引言多项目调度问题广泛地存在于建筑工程、软件开发、飞机及轮船制造等单件或小批量生产方式的企业中。如何在项目的工期约束和资源的能力约束条件下，合理地安排多项目的调度顺序，已成为项目管理者最关心的问题。在理论研究领域，资源共享下的多项目调度问题（resource-constrainedmulti-projectschedulingproblem,RC

3、MPSP）是一类重要的组合优化问题，此类问题通常被划分为两种，即“资源有限—工期最短”优化和“工期固定—资源均衡”优化。如何根据各项目的延迟罚款额来合理地分配共享资源，使得总项目的延期罚款数额最小是企业的现实困境，亦是我们开展理论研究的着眼点，据此得到的研究结果也更加具有实用价值。关于RCMPSP项目调度问题的研究始于1968年的Fendley[1]，他率先对多项目进度安排问题开展了研究，在对3-5个项目进行组合分析后，得出基于最小空闲时间的优先规则性能最好的结论。此后，众多学者将注意力投入到该问题的研究中，使其成为项目调度研究领域的一大分支。对于基本的RCMPSP

4、项目调度问题，其求解方法经历了从精确算法到启发式算法的发展过程。伴随求解算法的不断改进，RCMPSP问题的基本模型也得到了扩展。近年来，关于RCMPSP项目调度问题的研究成果不断涌现，Kimand和Leachman[2]研究了在动态的多项目环境中，假设每个项目有一个指定的完工日期，项目在其完工日期的前后完成有一个相应的奖惩，如何解决总的延迟成本最小的问题。Dumond和Mabert[3]研究了在动态的多项目环境中，如何选择各项目的优先级，为所有的项目较准确地预测完工日期的问题。此外，国内也有部分学者对该问题进行了研究，例如，寿涌毅[4]结合串行进度计划生成机制和逆向

5、算法的优点，研究了资源约束下多项目调度的迭代算法。周永华[5]建立了多项目环境中经营过程配置优化模型，并运用遗传算法求解优化模型中的随机资源分配问题。廖仁[6]采用基于优先规则的启发式方法对多项目调度问题进行了研究。傅杰等[7]研究了基于权值的优先调度算法。何正文等[8]概述了基于优先权规则的RCMPSP启发式算法的研究现状，对项目进度的表达方式及常用的超启发式策略进行了总结。通过对多项目研究动态进行梳理可以看出，国内迄今尚未发现从项目里程碑任务的完成节点出发，对RCMPSP项目调度问题进行深入研究的相关文献。项目基金：国家自然科学基金资助(71371150);新世

6、纪优秀人才支持计划资助(NCET-13-0460).作者简介：何华（1984-），博士研究生，研究方向：项目调度及优化。联系电话:13402946061,E-mail:angelsighhe@163.com,本文从项目里程碑任务的完成节点出发，研究基于资源共享的延迟惩罚最小化的RCMPSP项目调度问题。通过合理安排非关键路径上任务的开始时间，调整各项目任务的资源使用次序，使资源分配动态曲线的高峰尽可能降低，以达到资源消耗的均衡状态。在论文的后续部分，作者首先对研究问题进行界定；随后建立优化模型；根据问题的特点设计遗传算法；借助一个实际工程项目——XW公司多项目资源配

7、置案例对论文研究进行案例分析；最后总结全文并给出研究结论。2问题界定典型的资源受限下的多项目调度问题涉及若干个并行项目和一个共享资源库，资源库中包含若干种数量有限的资源，本文假设所有资源均为可更新资源。项目之间除存在资源的竞争与冲突之外，相互独立。项目内部的各任务之间为结束—开始的网络活动关系，且不存在任务抢占、反馈与循环。RCMPSP问题可以描述如下：在一个项目组内包含个相互独立的并行项目，每个项目内部有个任务，其中第个和第个任务为虚拟的起始和终止任务，且虚拟任务不占用资源和时间。并行的个项目共享种可更新资源，其中第种资源的供应量是，第个项目第个任务的开工时间