资源时间窗约束下任务可拆分项目调度的rollout算法研究

《资源时间窗约束下任务可拆分项目调度的rollout算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号学号M201171995学校代码10487密级硕士学位论文资源时间窗约束下任务可拆分项目调度的Rollout算法研究学位申请人:毕阳学科专业:系统工程指导教师:刘振元副教授答辩日期:2014年2月17日万方数据AThesisSubmittedinPartialFulfillmentoftheRequirementsFortheDegreeofMasterofEngineeringRolloutAlgorithmforPreemptiveProjectSchedulingwiththeConstraintsofTimeWindo

2、wsonResourcesCandidate：BiYangMajor：SystemsEngineeringSupervisor：AssociateProf.LiuZhenyuanHuazhongUniversityofScienceandTechnologyWuhan430074Hubei,P.R.ChinaFeb,2014万方数据万方数据华中科技大学硕士学位论文摘要目前资源受限项目调度问题主要对任务不可拆分、资源单技能且全程可得的问题进行研究。随着社会的日益发展，项目工程和资源特性逐渐发生变化，一些关键性资源具有时间窗特性，且具有

3、多技能特征，同时任务的执行允许不连续，可以对任务进行适当拆分。本文分别对单技能和多技能资源时间窗约束下任务可拆分项目调度问题进行研究。首先建立整数规划模型，然后根据模型设计基于优先规则的Rollout算法对问题进行求解，其中在单技能情形下，直接汇总技能提供量和需求量，来判断是否满足资源约束，在多技能情形下，提出贪心策略来判断任务是否满足资源约束，最后使用算例来检验算法的性能，通过设计资源技能矩阵和资源时间窗，将Patterson测试集中110个算例改进为多技能资源时间窗约束下任务可拆分问题，对多组不同的资源技能比例、含时间窗的资源比

4、例和可用时间占比参数下进行实验，来检验参数的灵敏度。实验结果表明在小规模问题上，该算法求取最优解的概率较大，拆分次数比CPLEX软件求解的最优解要少；在中大规模问题上，CPLEX软件无法求解，该算法能在较短时间内得到较优解。同时任务的可拆分性，资源的多技能性均能缩短项目工期。当单技能资源比例较多情形下，参数的灵敏度较大，当单技能资源比例适中或较少时，参数的灵敏度较小。关键词：资源受限项目调度；资源时间窗；多技能；任务可拆分；Rollout算法；贪心策略I万方数据华中科技大学硕士学位论文AbstractResourceConstrai

5、nedProjectSchedulingProblemmainlystudytheproblemthattheactivitycannotbesplitandtheresourcesonlyhaveaskillaswellastheresourcecangetinthewholetime.Withthedevelopmentofsociety,projectandresourcecharacteristicshavegraduallychanging.Someofthekeycharacteristicsofresourceshav

6、etimewindow,theresourcepossessedmulti-skill,andtheactivitiesallowthediscontinuous,theactivitiescanbeproperlybrokenup.Inthispaper,PreemptiveProjectSchedulingProblemwiththeConstraintsofTimeWindowsonResourcesandPreemptiveProjectSchedulingProblemwiththeConstraintsofTimeWin

7、dowsonMulti-SkillResourcesarestudiedseparately.Firstlytheintegerprogrammingmodelisestablished,andthenRolloutalgorithmbasedonpriorityruleisdesignedtosolvetheproblemaccordingtothemodel.Inthecaseofsingleskill,directlyprovidingasummaryofskillsanddemand,todeterminewhetherme

8、ettheresourceconstraint,whileinthecaseofmulti-skill,thegreedystrategyisproposedtodeterminewhethermeettheresourceconst