基于演化多任务的实时云工作流调度算法研究

The rapid growth of both scale and amount of the workflow computing task on the cloud computing platform is bringing a big challenge to the workflow scheduling system in terms of efficiency and throughput rate. To address this bottleneck problem, we plan to develop a new workflow scheduling algorithm which solves a set of optimization tasks in batch mode by utilizing the scheduling system’s historical data and the unstructured domain knowledge in the evolutionary multitasking paradigm. 1) A relationship of positive correlation between workflow scheduling problem instances and its measurement will be defined to measure the degree that two scheduling problem instances promote each other's search process when they are optimized together. 2) We will illustrate the influence of the number of simultaneously optimized scheduling problem instances and their positive correlation degrees on the performance of the evolutionary multitasking algorithm. 3) We will recover the implicit mechanisms of domain knowledge minding, inheriting and transfer in the evolutionary multitasking algorithm. 4) By extracting the domain knowledge emerged during the search process of the evolutionary multitasking algorithm, an unstructured domain knowledge base will be built. 5) Based on the historical data and the domain knowledge base, a real-time workflow scheduling algorithm with self-learning ability will be developed by following the evolutionary multitasking paradigm. The study work in this project is expected to help significantly promoting the throughput rate of existing workflow scheduling systems. It will provide an innovative and efficient solution to the large-scale and real-time workflow scheduling problem in the cloud computing environment.

面对云计算环境下规模和数量与日剧增的工作流计算任务，现有云工作流调度算法的优化性能和吞吐率已无法满足实际应用需求。针对这一瓶颈问题，本课题拟在演化多任务算法框架下，利用调度系统的历史数据和非结构化的领域知识，设计以批处理方式同时优化多个问题实例的实时云工作流调度算法。1）定义云工作流调度问题实例集合上的正相关关系和正相关度，用以衡量问题实例在同时优化时搜索过程相互促进的程度。2）揭示同时优化的问题实例数量、正相关度与演化多任务算法性能之间的关系。3）阐明演化多任务算法中隐式的知识发现、继承和迁移机理。4）提取在演化多任务算法优化过程中涌现出的隐式表达的领域知识，建立非结构化的领域知识库。5）基于历史数据和领域知识库，在演化多任务框架下设计具有自学习能力的实时云工作流调度算法。本课题的研究有望显著提升现有云工作流调度系统吞吐率，为云计算环境下大规模工作流的实时调度问题提供新颖有效的解决方案。

云工作流调度问题的复杂性、动态性和实时性求解需求给工作流调度算法的求解能力提出了更高的要求。面向云平台上大规模的云工作流调度任务，现有工作流调度算法把每个调度任务都看看作一个新的优化任务求解的思路已经无法满足云工作流调度的实际应用需求。因此，如何有效描述问题特性，利用相似历史任务的求解经验提升对新调度任务的求解能力，是本课题的主要研究内容。.本课题在深入分析云工作流调度问题在目标空间和决策空间上特性的基础上，定义了云工作流调度任务之间的相似性度量标准，用于描述两个调度问题实例之间的相关程度。进一步根据历史调度任务与新任务之间的相关程度，提出了可参考历史任务的筛选策略，在演化多任务算法框架下，对相关的云工作流调度任务同时求解。在提出的算法框架下，深入研究了优化任务数量、调度问题实例之间的相关程度、调度问题实例的特征、演化多任务算法参数、问题分解方法等各个因素对算法求解效率的影响。提出了从历史调度任务中抽取优化任务的知识用于加速求解新任务的迁移优化方法，基于子空间对齐方法与显式迁移技术在演化多任务算法上实现了调度任务之间的知识迁移。最后在理论研究成果的基础上，设计并实现了一套云工作流调度软件。.本课题的研究对于如何实时求解大规模云工作流调度问题具有重要的理论意义，提出的云工作流问题分解技术、以及分治等策略对于后续提升演化多任务优化算法对求解云工作流调度问题的求解效率具有重要的意义。与此同时，本课题针对云工作流调度问题设计了专用的数据驱动方法、偏好表示模型以及基于偏好的多目标云工作流调度算法，并利用代理模型构造相关任务通过迁移优化辅助多任务优化模型求解，为云工作流调度问题提供了有效的演化多任务优化求解方案，对于推动多任务优化在实际工程中的应用具有重要的现实意义。