多模式多项目资源均衡及其优化方法 数学与应用数学本科毕业论文 12页

TONGRENUNIVERSITY学号：2009043010本科毕业论文多模式多项目资源均衡及其优化方法系别:数学与计算机科学系学科：理学专业：数学与应用数学专业指导教师：贵州●铜仁2013年06月数学与应用数学专业本科毕业论文贵州●铜仁2013年06月Tongrenuniversity\n数学与应用数学专业本科毕业论文贵州●铜仁2013年06月Tongrenuniversity\n目录（理科）摘要IAbstractII引言11、问题描述及模型设计12、算法描述及设计22.1启发式算法22.2基于优先准则的启发式算法23、数值实验34、结论65、参考文献：66、致谢7\n多模式多项目资源均衡及其优化方法数学与计算机科学系数学与应用数学专业吴悠摘要针对多执行模式的多项目资源均衡问题，不考虑项目之间的承继约束，只考虑项目权重和资源限制等因素，建立多执行模式多项目资源均衡问题的数学模型。采用基于优先准则的启发式算法：最长持续时间准则（LongT）启发式算法和最大资源需用量准则（MaxR）启发式算法对所建模型进行求解，并用数值实验去检验所建模型的合理性和有效性，从而得出一种较为合理可行的调度方案，使得需建项目工作的资源得到合理的配置。关键词：资源均衡多模式启发式算法II\nMultimodemulti-projectresourcebalanceanditsoptimizationmethodMathematicsandAppliedMathematicsDepartmentofmathematicsandcomputerscienceWuYouABSTRACTFormultipleexecutionmodelofmulti-projectresourcebalanceproblems，notconsideringinheritanceconstraintamongprojects,butconsideringthefactorsbetweenprojectweightandresourceconstraints,establishingthemathematicalmodelofthemultipleexecutionmodeandmulti-projectresourcebalanceproblems.Usingheuristicalgorithmthatbasedonpriorityrule:TheLongestActivityTime(LongT)andTheMaximumResourceDemand（MaxR）thatsolvethemodel.Aswellasusingnumericalexperimentstoexaminetherationalityandefficectivenessofthemodel,thengettingapracticalmethodtomakethereasonableconfigurationofresourcestotheneedofprojectwork.Keywords:ResourcebalanceMultiplemodelHeuristicalgorithmII\n引言随着社会的不断发展和科学技术的不断提高，项目计划管理的实践地位得到了很大提高。同时也引起了科研工作者和企业决策者的广泛关注。特别是近些年来，企业为了最大化的获得财富，也为了生存，一方面，企业所承接的项目越来越多，另一方面，承接的项目越来越复杂（即项目有多种执行模式可供选择）。单凭企业管理者或项目调度人员的已有经验已经不能很好的解决这类复杂问题。因此，解决这类多执行模式的多项目资源均衡问题，引起了企业管理者及研究者们的高度重视，并成了企业面临的首要问题。基于此，在资源受限条件下，只考虑项目的权重因素，不考虑项目与项目之间的承继约束，建立多执行模式多项目资源均衡的数学模型。由于此类问题比较复杂且约束条件多，因此本文利用基于优先准则的启发式算法：最长持续时间准则（LongT）启发式算法和最大资源需用量准则（MaxR）启发式算法求解所建模型，两种启发式算法都获得了模型的可行解，得到的数值试验结果证明所建的模型是合理可行的。1.问题描述及模型设计假设某企业在未来时间段天内共承接了个项目，现将每个项目看作一个整体，并且这些项目都是相互独立的，即项目之间不存在逻辑关系。每个项目的完成有种执行模式可供选择，但是，每个项目只能选定其中一种执行模式，且在执行过程中不得中断或改变其选择的模式，表示项目的开始执行时间，表示项目选择的执行模式，表示在第天所执行的所有项目的集合，在所有项目执行过程中共有种资源，项目以模式执行所花费的时间为，以及其在已选模式下，每天需要第种资源的资源量为，第种资源在第天的总限量为则，(1)设整个工期内第种资源总限量为，则对种资源的需求量为（2）当执行方案使得（1）、（2）都满足时，那么执行方案在利用第种资源时的资源利用方差为7\n（3）于是多执行模式多项目资源均衡问题的数学优化模型为：2．算法描述及设计2.1启发式算法多执行模式多项目资源均衡问题属于优化组合问题，也属于NP难问题，解决该类问题主要有两类方法，精确算法和启发式算法。我们所熟知的精确算法有0—1算法，整体线性规划法和分枝定界法等。常用的优化方法精确算法能很好的解决规模小、维数低和变量少的优化问题，也能获得优化问题的最优解，但是对本文所研究的这类多项目多执行模式的高维多约束多变量的复杂问题很难求解。，并且对于任务较多的项目来说此类算法难以实施。本文所建模型不仅维数较高，且变量多，很难用精确算法去解决该类问题，所以人们开始尝试用一些不一定能够求解得最优解的算法，即启发式算法对其求解。（1）启发式算法的原理启发式算法是一种建立在直观或已有经验为基础的算法，在满足时间的需求和空间的占用的情况下，把待解决的优化组合问题的每一个实例都给出一个可行解，但所得到的可行解与最优解之间的偏离程度事先不一定能够预计。（2）启发式算法的优点启发式算法操作起来简单，程序编排也不难，易于修改，使用起来方便，而且运算速度快，获得解所需时间也较少。虽然不能像精确算法那样找到优化问题的最优解，但是能找到较为满意的可行解。此外，启发式算法还可以用于精确算法中，这样互相混合产生的算法能很好的解决某些优化问题。2.2基于优先准则的启发式算法7\n基于优先准则的启发式算法是解决项目计划管理问题的一类最为常见的启发式算法。这类启发式算法主要由调度生产方案以及优先规则两个要素组成。调度方案主要是用来产生一个合理可操作的调度，但是在产生可行调度的过程中需要用优先规则来确定任务集中各任务的优先值，由优先值决定任务的先后排序。基于优先规则的启发式算法包括一次调用和多次调用两种方法。其中，一次调用法是应用最早的启发式算法，即在算法中只调用一次调度方案和一个优先规则。多次调用方法是指多次调用产生方案，获得若干个调度，从中选取结果最符合现实生产的作为最优调度。(1)最大资源需要量准则最大资源需要量准则(TheMaximumResourceDemand,简称MaxR)是在所有可能安排的活动中首先安排那些资源需要量最大的活动，即它是根据资源需要量的大小顺序优先安排的，如果现实生产需要我们满足一组目标而不是要求满足某一目标，这一准则是很有价值的。(2)最长的活动时间准则最长的活动时问准则((TheLongestActivityTime,简称LongT)首先安排那些完成时间最长的项目活动，即它是按活动所需要的时间从长到短进行排序的，其目的是为了使工程后期所安排的活动能尽快结束。3．数值实验问题设某企业一共承接了10个项目，每个项目有两种执行模式，且要求在T=60(天)内完成所有项目。各项目分别消耗3种资源，此3种资源的权重分别为0.3，0.4，0.3,在单位时间内提供的资源量分别为6、6、6，且在T天内这3种资源总量分别为120、120、120.现需要求寻找一种多项目选择调度的计划方案，使得上述各资源在时间段T天内分配尽可能均衡且得到最大利用，经过模型的分析求解所获得的数据如下表：7\n表1各项目每种模式所需的单位资源量项目编号模式一（对应需要三种的资源量）模式二（对应需要三种的资源量）模式三（对应需要三种的资源量）12312312312223331112322333122335224244445436553435522322121641431341675544444418352453554924413333310322432434表2各项目每种模式所需的持续时间项目编号持续时间（模式一）持续时间（模式二）持续时间（模式三）12132324356445365346645371248654924310654表3算法比较结果算法工期目标值7\nLongT290.531026MaxR250.469501表4LongT算法的决策方案项目序列执行模式开始时间执行时间121110116817653136621353318442223912522227271291表5MaxR算法的决策方案项目序列执行模式开始时间执行时间12111011691228275711216113453136411753322423224由表4和表5可知，基于7\n最大资源需要量准则的启发式算法和基于最长的活动时间准则的启发式算法都获得了问题的可行解，说明本文所建立的模型是合理的，所用算法是有效的。另外，由表3还可知，虽然两种算法都得到了问题的解，但是每种算法得到的结果不一样，即工期和目标函数值都不一样，基于最大资源需要量准则的启发式算法所获结果明显好于基于最长的活动时间准则的启发式算法所获结果，根本原因在于每种算法的优先规则不同。4．结论本文针对多模式下的多项目资源均衡问题，建立了与之相对应的数学优化模型，在预定工期内以达到项目的资源利用合理均衡的目的，并运用基于优先规则的启发式算法对其求解。所获得的数据试验数据和结果表明所建立的数学模型是合理的，对模型的处理方法是可行和有效的。同时，由于多模式多项目资源均衡问题较为复杂，需要考虑的因素较多，本文仅仅只考虑了项目的权重、资源的限制因素，项目相互间的逻辑关系及企业之间的合同等因素都还没有考虑。因此，不管是模型还是优化方法的探讨，本文仅是一次尝试，很多详细具体的工作还需进一步改进和完善。5．参考文献[1]王宏.求解资源受限项目调度问题算法的研究[J].天津大学博士学位论文，2005.12.1[2]夏林丽,张著洪.多模式项目资源配置及其免疫与优化决策[J].贵州大学学报（自然科学版）2010.4（27）：57-61.[3]刘国靖.现代项目管理教程[M].中国人民大学出版社2004年2月第1版.[4]姜启源,谢金星,叶俊.数学建模（第三版）[M].高等教育出版社2003年8月第3版.[5]EvelynStilleCathieLeblanc著基于项目的软件工程（面向研究方法）机械工业出版社2002年6月第1版.[6]庞南生,纪昌明,张艺.活动多种执行模式下网络计划资源均衡优化模型[J]系统工程报2009年09期.[7]张艺.考虑资源均衡的多模式项目支付进度问题研究《华北电力大学（北京）》2011年[8]周树发，刘莉.工程网络计划中的多目标优化问题[J].华东交通大学学报.2004.21（2）[9]刁在筠,刘桂真,宿洁,马建华.运筹学（第三版）[M].高等教育出版社2007年1月第3版.6．致谢7\n在论文的写作过程中，遇到了许多困难，特别是对数学模型的修改和对文章总体的把握，在指导老师的指导下和同学们的帮助下我最终得以克服这些难关，论文才得以按时完成.在这里我特别对我的指导老师和同学们表示深深的感谢，也感谢为我的论文提供文献的作者们。愿你们身体健康，万事如意！7