论文部分内容阅读
资源受限项目调度问题是一类在满足项目的资源约束和时序约束的条件下,合理安排项目中每个任务的开始时间,以实现项目既定目标最优化的调度问题。该问题理属于NP-hard问题,具有丰富的问题模型,广泛的存在于生产制造、建筑工程、软件开发等实际问题中,其中车间调度问题是该问题的特殊形式。因此研究资源受限项目调度问题具有重要的理论和现实意义。 当前对于资源受限项目调度问题的研究主要集中在问题分析、模型建立、算法设计、实际应用等方面,尤其对该问题的求解算法研究,迄今为止已提出了精确算法、启发式算法和智能算法等众多算法。尽管目前的各种算法对于问题的求解具有一定的合理性、适用性,但该问题模型丰富、考虑因素较多、求解难度大,需要更加高效、更加完善的算法对该问题进行求解。因此,本文主要对单模式单目标、单模式多目标和多模式多目标等三类资源受限项目调度问题研究智能求解算法,本文主要工作如下: 1)针对单模式单目标的资源受限项目调度问题,提出了UCT-RCPSPs算法。针对问题特点,该算法利用UCT算法的框架将其优化成项目搜索树结构,并利用每次搜索的返回值来更新项目搜索树中的信息,为后续的搜索提供依据。其中项目搜索树在搜索之初为空,随着搜索的进行,项目搜索树将逐渐增长,直至搜索到最优解或达到一定搜索次数。实验表明,该算法不但具有很好的搜索性能,而且对于任务数较多的项目也表现出了很好性能。 2)针对多目标资源受限项目调度问题提出了一种多智能体进化算法。在该算法中,将每个调度方案作为一个独立的智能体,并利用智能体系统中智能体之间的关系,对每个智能体进行邻域交叉、变异、自学习等操作,以实现智能体的进化,并最终获得问题的Pareto解集。经实验证明该算法能够有效的求解此类问题,并具有很好的稳定性。 3)针对多模式资源受限项目调度问题提出了一种共生进化算法。该算法利用共生进化的原理,将调度问题中的模式序列和任务序列作为两个共生体,分别展开进化,从而找到问题的最优解。经实验证明,该算法能够很好的求解多目标多模式资源受限项目调度问题,并且模式序列和任务序列的种群规模可根据问题难度的不同随时调整,充分证明了该算法具有较大的应用范围和很强的实用性。