基于云遗传算法的软件项目资源调度研究

《基于云遗传算法的软件项目资源调度研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第2页武汉科技大学硕士学位论文顺序，以及各项任务的开始、结束和持续时间。虽然这种方法比较形象直观，容易掌握，但是不能完全体现工作间的相互依赖关系，如果工作过早开始或者过晚开始，则不能体现其所造成的后果。在20世纪50年代中期，随着网络计划技术发展，这种技术迅速渗透到项目调度领域中，以网络图的形式来展示项目的进度计划。它能比较明确的反映各活动时间的先后顺序以及相互制约的逻辑关系，通过计算项目各项任务的时间参数，可找出整个计划中的关键活动以及关键路线，反映出各活动的时差。这种方法的思想是通过缩短关键工作路线的持续时间，从而达到使工程的工期和费用优化的效果。在实际的项

2、目执行过程中一般都包含有大量不同的活动和各种人力、物力资源，在项目各项活动的组织安排中，有的活动是可以并发进行的，有些活动则是必须在等待其他若干活动完成之后才能进行的，这就构成了资源受限项目调度问题。资源受限项目调度问题的研究初期，学者们主要集中于用数学规划方法对这类优化调度问题进行建立模型和求解，并采用整数规划手段来求解这一类优化调度问题的精确解。在这之后提出了分支定界方法，这种方法能在较低计算成本的情况下获得规模比较小的问题的精确解。在经过很多学者的不断努力和计算机技术快速发展的基础上，分支定界法的求解能力和求解速度都得到了较大幅度的提高。Christofi

3、des等人引入冲突工作集和替代集概念，并提供了新的分支定界算[6]法研究方向。Demeulemeester等人发展了替代集的思想，提出基于最小延迟替代集概念的分支定界算法，并结合先进的计算机技术对算法进行了改进，取得了[7]很好的效果。Patterson等人提出了基于紧前关系树概念的分支定界算法，Sprecher等人针对对这种分支定界的方法又提出了多种定界的算法，他们采用PSPLIB中单目标资源受限项目调度问题的480个问题进行的求解实验表明了该[8]算法是最好的精确算法之一。启发式算法主要包括传统的基于优先规则的启发式算法、采样算法和智能算法等。Kelly提出

4、了串行调度方案和并行调度方案，并指出了重要的研究方向。随后陆续有学者在这个基础上提出了采用不同优先规则的调度算法。采样算法采用了与传统基于优先规则的算法不同的优先权系数利用方式，并且引入了概率式选择的方式。许多学者都在这方面进行了研究，先后提出了随机采样算法(RandomSampling，RS)、带有偏好的随机采样算法(BiasedRandomSampling，BRS)、基于后悔值的随机采样算法(Regret-basedRandomSampling，RBRS)，等等。在求解RCPSP时所用的智能优化算法主要有模拟退火(SimulatedAnnealing，SA)

5、、禁忌搜索(TabuSearch，TS)和遗传算法(GeneticAlgorithm，GA)等方法。另外，以色列学者高德拉特将约束理论(TheoryofConstraints，TOC)应用于项目管理的领域，提出了基于关键链的项目管理理论，并由此发展出了一种新型项目调武汉科技大学硕士学位论文第3页[9]度理论：基于关键链的项目调度理论。1.2.2国内研究现状项目资源调度优化问题作为一个具有一定实践意义的研究课题，很早就获得国内学者的广泛关注，并开始不断的在进行各项研究工作。在使用早期的数学模型方法处理比较复杂的项目问题时，经常很难入手。后来发展的一种直观推断法，即

6、线性规划方法和网络计划技术，是现在应用最广的技术，但是这种方法过度依赖于问题本身，在应用时针对“工期固定，资源平衡”和“资源有限，工期最短”这两方面的问题，必须采取不同的方法来解决。并且，虽然在多数情况下这些方法可以产生出十分可靠的可行解，但是根据这种方法来获得解的最优性不容易判定。目前，项目管理资源优化问题仍然主要集中于单目标资源优化，即在一些既定约束条件下，按照某一个目标，通过不断对进度计划进行改进来寻求满意的方案。在对工期固定，资源均衡的进行优化调整的过程中，通常采用资源方差来判断资源的均衡性，如果方差越小则资源均衡性越好，但是这种调整的过程通常要经过一系

7、列非常繁琐的推断过程。自从资源受限项目调度问题被提出来之后，出现了非常多种类的资源受限项目调度问题。其中辛润勤通过以下几个方面对资源受限项目调度问题进行了分类。(1)根据项目调度的目标分类可以分为：项目工期的最小化；项目净现值的最大化；资源均衡问题。(2)根据项目中资源的类型可以分为：非可再生资源，即资源的总量在整个项目工期内具有一定约束条件，资源被消耗完后就不能再生；可再生资源，即这类资源的可使用量只在项目进行的每个阶段受到约束，比如某个阶段的数量有限，但这个阶段的任务一旦结束，资源使用完被释放就可以再生；双重资源约束：资源的可使用量除了在整个项目整个工期内具

8、有约束，并且在项目工期中