论文部分内容阅读
化学反应启发式优化算法(Chemical Reaction Optimization，CRO)是近年来提出的一种新型演化算法。其已在诸多领域展示了解决NP完全问题的强大能力。本文以化学反应优化算法这一元启发式方法作为研究主线，立足于当前计算机科学基础研究与领域交叉研究的前瞻性与实用性需要，对算法进行改进与创新，以实现异构环境下调度的优化。其所面向的调度优化问题的应用背景又包括了计算机科学的异构计算系统任务调度，以及建筑科学与计算机科学交叉的BIM-4D两大领域。 在计算机科学异构计算系统任务并行调度领域，作为一种元启发式算法，现有的用于优化并行调度的CRO算法仍具有较大时间开销且收敛效率上仍显不足，且其反应算子对目标问题解空间内两个子空间的搜索缺乏兼顾，局部搜索与全局搜索不平衡。而在建筑科学与计算机科学交叉的建筑信息模型(building information modeling，BIM)4D领域，现有研究工作中缺乏有效方法融合结构化数据与非结构化数据以构建施工进度分包与调度数学模型，且大多忽略了施工任务分包资源系统存在异构这一实际情况，缺少有效的施工进度计划任务分包与调度优化方法。因此，针对上述两大领域在异构环境调度优化方向上存在的问题与不足，本文在以下方面展开了研究工作: (1)提出一种元组分子结构化学反应优化算法(tuple molecular structure-basedchemical reaction optimization，TMSCRO)用于异构计算系统下并行调度，为强化整体优化能力，设计了相比同领域CRO优化算法更合理的分子结构，以及兼顾局部搜索与全局搜索平衡基本反应算子。为有效提高算法收敛速率，应用约束最早时间算法(constrained earliest finish time，CEFT)与约束关键路径有向无环图(constrained-critical-path directed acyclic graph，CCPDAG)于算法数据预处理阶段，并利用约束关键路径(constrained critical path，CCP)这一概念于算法初始化阶段，同时在整个算法执行过程中加入了超级分子以进一步实现对收敛速率的优化。 (2)基于TMSCRO算法，提出双反应结构化学反应优化算法(double-reaction-structured chemical reaction optimization，DRSCRO)，该算法包括超级分子选择阶段与整体优化阶段。DRSCRO相比同领域CRO优化算法，能利用元启发式方法构造超级分子;在算法框架上嵌入变邻域搜索(variableneighborhood search，VNS)方法来提高算法的局部优化搜索能力，该VNS方法也应同时兼顾了任务序列与处理器分配的优化;同时VNS方法邻域结构还包含一个改进的处理器选择模型，以提高优化性能。 (3)基于知识图谱技术在数据结构化融合处理上具有强大能力，设计一种基于知识图谱技术的BIM-4D信息库构建通用流程框架，并以之来进一步构建数学模型;同时提出一种新的工程任务分包与调度数学模型，包括施工进度计划DAG模型与异构资源系统模型以便于利用（元）启发式方法进行进度优化。 (4)在所构造的数学模型基础上，提出一个改进的VNSCRO算法，实现了对异构资源环境下道路施工进度计划任务分包与调度的优化。VNSCRO算法融合了CCP重排序策略，并在初始化与优化构造超级分子阶段，设计应用了一种平衡邻域结构的变邻域搜索方法，强化了算法的整体优化能力。 本文采用了实际应用场景中数据，分别对所提出的三种CRO类算法进行了模拟实验，模拟实验结果验证了所提出算法的有效性、鲁棒性与相对优势。本文的研究成果可以有效实现目标问题的优化并可推广性的处理大量实际应用问题。