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

发布时间：2017-11-06 05:04

  本文关键词：资源时间窗约束下任务可拆分项目调度的Rollout算法研究

  更多相关文章： 资源受限项目调度 资源时间窗 多技能 任务可拆分 Rollout算法 贪心策略

【摘要】：目前资源受限项目调度问题主要对任务不可拆分、资源单技能且全程可得的问题进行研究。随着社会的日益发展，项目工程和资源特性逐渐发生变化，一些关键性资源具有时间窗特性，且具有多技能特征，同时任务的执行允许不连续，可以对任务进行适当拆分。 本文分别对单技能和多技能资源时间窗约束下任务可拆分项目调度问题进行研究。首先建立整数规划模型，然后根据模型设计基于优先规则的Rollout算法对问题进行求解，其中在单技能情形下，直接汇总技能提供量和需求量，来判断是否满足资源约束，在多技能情形下，提出贪心策略来判断任务是否满足资源约束，最后使用算例来检验算法的性能，通过设计资源技能矩阵和资源时间窗，将Patterson测试集中110个算例改进为多技能资源时间窗约束下任务可拆分问题，对多组不同的资源技能比例、含时间窗的资源比例和可用时间占比参数下进行实验，来检验参数的灵敏度。 实验结果表明在小规模问题上，该算法求取最优解的概率较大，拆分次数比CPLEX软件求解的最优解要少；在中大规模问题上，CPLEX软件无法求解，，该算法能在较短时间内得到较优解。同时任务的可拆分性，资源的多技能性均能缩短项目工期。当单技能资源比例较多情形下，参数的灵敏度较大，当单技能资源比例适中或较少时，参数的灵敏度较小。
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：F224;F062.4

【参考文献】

中国期刊全文数据库 前1条

1 刘士新,王梦光,唐加福;求解项目调度中资源水平问题的近似算法[J];系统工程学报;2002年04期

本文编号：1147431