基于分布估计算法的资源受限项目调度方法

《基于分布估计算法的资源受限项目调度方法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要摘要在项目调度问题中，一个项目往往包含多个任务，每一个任务的完成都需要消耗一定的时间，占用一定的资源。项目调度的目标是安排各个任务的执行时间来满足高效、低消耗的工程要求。资源受限项目调度问题（Resource-ConstrainedProjectSchedulingProblems，RCPSPs）是在项目调度的基础上，规定资源上限约束以及由于技术上或其它一些因素导致的任务之间的时序约束，在约束范围内优化某个项目调度目标。这一重要的问题模型在众多领域得到了广泛的应用，拥有较大的工程应用背景，主要包括规划、管理、设备机器制造维护以及开发与研究中遇到的与调度相关的工作。求解RCPSPs

2、的算法研究是调度领域的一个重要研究方向。近年来，考虑到该问题的复杂性以及RCPSPs模型的多样性，算法研究方向主要集中在启发式方法上。作为进化算法的一个重要分支，待解决问题的复杂性以及大规模的变量促进了分布估计算法（EstimationofDistributionAlgorithm，EDA）的发展，这类算法也被称为基于模型构建的遗传算法或迭代密度估计进化算法，其通过不断更新概率模型实现优化过程，从无偏差分布开始，逐步优化收敛到只生成最优解的模型。本论文主要研究如何将EDA应用到RCPSPs上，主要工作可总结为如下三个方面：（1）首先对RCPSPs的特性进行了研究，提出了一种新的方法来

3、分析单模RCPSPs的解空间组态。通常在多数求解单模RCPSPs的算法中，RCPSPs有三种解码方式，分别是前向解码、后向解码和混合解码。我们通过比较这三种解码方式构建的解空间网络特性，分别评价这三种解码方式。主要工作分为两个方面：第一，构建单模RCPSPs的局部最优解网络（LocalOptimaNetwork，LON），LON中的节点表示局部最优解，节点之间的边表示局部最优解之间的转化方向及概率；第二，分析了三种RCPSPs-LON的不同网络特性。分析表明RCPSPs-LON结构大致分为三种类型，混合解码方式构建的RCPSPs-LON相比于其它两种解码方式具有较好的网络特性。（2）

4、基于以上关于单模RCPSPs解空间的分析，接下来我们提出了求解资源受限项目调度问题的松散约束分布估计算法（EDALCS-RCPSPs）。在该算法中，每一个个体为一个满足时序约束的活动列表，新的个体由概率模型产生并且从每一次迭代中选取较好的解进行特征采样来更新概率模型。算法采用传统的前向-后向-前向局部搜索方法（Forward-Backward-ForwardIteration，FBI），除此之外，我们提出了一个新的局部搜索算子，即松散约束搜索（LoosingConstraintSearch，LCS）来增强算法的优化强度。通过EDALCS-RCPSPs与已有EDA的对比实验，说明了LC

5、S的局部搜索能力以及EDA模型的全局搜索能力，表明EDALCS-RCPSPs的性能优势。I西安电子科技大学硕士学位论文（3）基于以上对单模RCPSPs分布估计算法的研究，进而提出了一种新的RCPSPs模型——带时间窗的资源受限项目调度问题（Resource-ConstrainedProjectSchedulingProblemswithTimeWindows，RCPSPs-TW），并设计EDA解决该问题。在RCPSPs-TW中，首先构建一个松散的基准调度方案，然后通过向该方案中每个活动添加时间窗的方式，来产生基准的时间窗约束。RCPSPs-TW模型的有效解必须满足以下三种约束：时序约

6、束、资源约束、时间窗约束。针对于这一模型，我们提出了一种新的松散调度解码方式（SparseDecoding，SD）。我们采用Patterson、J30、J60、J90、J120标准数据集对算法性能进行了验证，实验结果表明这一模型的解的优劣与所加时间窗的长短有很大的关系，较短的时间窗约束下所得的解更优。关键词：资源受限项目调度问题，分布估计算法，时间窗模型，松散约束搜索，稀疏解码IIABSTRACTABSTRACTResource-constrainedschedulingproblems(RCPSPs)areanimportantbranchofschedulingproblems,

7、whoseobjectiveistominimizethemakespanofprojectsoverreasonableusageofresourcesandschedulingofactivities.RCPSPshaveawideengineeringbackgroundandmanyalgorithmshavebeenproposed.Duetothecomplexityanddiversityofthisproblem,mostexistinga