分布式系统中计算作业流的均衡调度算法

分布式系统中计算作业流被映射到节点后无法进行动态调整,使关键作业无法及时执行而造成作业间等待。针对该问题,提出一种计算作业流均衡调度算法。算法对映射到分布式节点的作业根据其依赖关系得出阶位值,依据该值在分布式节点上进行动态优先值调整,使关键作业尽早完成,减少作业之间的等待,缩短计算作业流执行时间。实际系统应用表明,该算法对作业管理系统中投入的计算作业流的快速执行有较强优越性。     

作业流的结构化定义方法

作业流，也称作业网络，是相互关联的作业形成的一个偏序集。由于作业间存在着顺序、分支、循环、并行、同步、异步等依赖关系，因此作业流可能非常复杂。如果没有一个良好的定义准则，那么生成的作业流将结构混乱，不利于查错、解析，也不利于可视化显示。该文归纳了作业间的依赖关系，提出了作业流的结构化定义方法。这种方法简单地表达了作业间的多种依赖关系，它也能表达作业流间的层次和嵌套关系。     

基于Web机制的作业管理系统的设计与实现

传统的作业管理系统一般局限在局域网范围内，用户量有限，作业的执行状态和结果不能通过Internet网远程监控和查询。文章在考察Web技术的基础上设计并实现了一种基于Web机制的作业管理系统，文中阐述了系统的应用模式和体系结构，以及系统中各个子系统的功能及相互关系，引入了作业网络的概念，描述了作业间复杂的逻辑依赖关系，也可表达作业网络间的层次和嵌套关系，这进一步扩大了系统的应用领域。     

一种基于Workflow的作业流管理系统研究

将工作流技术应用于作业管理系统,提出了基于Workflow的作业流管理系统,首先给出了系统的体系结构,然后从作业流的定义与描述,作业流的调度与执行等方面具体分析了作业流管理模型,该系统是对现有作业管理系统和工作流管理系统的动态扩充,有着非常广阔的应用前景。     

面向信息服务的网格资源管理器的设计

设计一个面向信息服务的网格资源管理器的架构，该架构分为全局和局部管理器。介绍一个新的作业调度算法，该算法的特点是根据历史作业执行时间来预测当前作业的执行时间，在调度时考虑作业执行时间和截止时间2个要素。试验证明该算法比目前常用的Max-Min和Min-Min算法具有更好的性能。     

基于混合GA算法的工作流作业调度队列优化

工作流作业的调度效率是评价工作流管理系统整体表现的重要指标。众所周知,工作流作业的调度问题是一个NP-hard问题,而异构的计算环境使得问题更加棘手。分层基因算法LGA将启发式算法与GA算法相结合,利用GA算法来优化经过正向分层之后的工作流作业调度队列,显著地减少了工作流作业的执行时间。该算法根据作业的分层优先级来产生作业队列,把队列中的同层作业从整体上看作是一位基因来处理,有效地对算法的进化方向进行规划,并通过对杂交和变异流程的改进,增强算法的搜索深度和广度。实验表明,相比于其他混合GA算法,经LGA算法优化之后的工作流作业调度队列,所需的执行时间更少。     

基于频繁序列模式压缩技术的网站结构优化

基于频繁序列模式压缩技术的网站结构优化算法旨在发现用户在浏览过程中频繁访问的序列关联,为优化站点结构提供有力的依据。分析了现有频繁模式聚类算法的不足,提出了在模式聚类函数的基础上生成一个压缩的偏序（Partial Order）的算法,实验结果显示该算法可以对频繁序列模式进行高效、高质量的压缩,可以得到数量更少、信息量更大的模式,从而提高发现的频繁访问序列的兴趣性。     

基于蚁群优化算法的服务网格的作业调度

提出了利用蚁群算法来优化服务网格的作业调度系统的方法和一个两层的作业调度模型，该模型可以在网格的动态和异构环境下实现对作业执行时间的预测，然后根据作业的预测执行时间并利用蚁群优化算法使适应函数取得最小值，从而得到最优化的作业调度。基于开发的校园网格实验床，通过实验显示该方法可以优化服务网格的性能，减少作业的平均执行时问，提高系统的吞吐率。     

SQL Server定时作业在管理系统中的应用

研究了定时作业机制在大型SQL Server2005数据库系统中的应用问题。阐述了定时作业在系统应用中的优势，讨论了数据库系统中定时作业机制的实现方法，研究了系统的结构及硬件配置方法，给出了用户的窗口界面的实现结果。工程应用证明定时作业可以有效地解决数据冗余问题，提高了系统响应速率，方案切实可行。     

基于分布式工作流日志挖掘的流程识别算法

为了识别出分布式环境下工作流的执行流程,对分布式工作流管理系统进行了研究,通过对分布式工作流执行站点中XML格式的系统运行日志进行分析,提出了一种增量式工作流挖掘算法。该算法通过对大量工作流执行站点中的活动执行时间序列进行分析与合并,从而重构出分布式环境下的工作流模型。该算法主要由两个重要部分组成:一个是时间序列挖掘算法,用于从工作流执行日志中挖掘出活动间的执行时间序列;另一个是工作流程识别算法,在时间序列挖掘算法得出的活动执行时间序列基础上,识别出结构化的工作流模型。通过实例结果表明了该算法的有效性。     

使用内存缓存的迭代应用编程框架

迭代式计算是一类重要的大数据分析应用.在分布式计算框架MapReduce上实现迭代计算时,计算会被分解成多个作业并按作业依存关系顺序运行,这使得程序与分布式文件系统(DFS)有多次交互而影响程序执行时间.对这些交互相关数据的缓存会降低与DFS的交互时间,进而提升程序总体的性能.考虑到集群中的大量内存在多数情况下会处于空闲状态,提出了一种使用内存缓存的迭代式应用编程框架MemLoop.该系统从作业提交API、调度算法、缓存管理模块实现缓存管理以充分利用内存缓存迭代间可驻留数据与迭代内依存数据.我们将此框架与已有相关框架进行了比较,实验结果表明该框架能够提升迭代程序的性能.     

单位处理时间的多处理机任务调度近似算法

研究多处理机任务调度模型P_m|fix,p_j=1|C_max,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。其更一般的问题是P_m|fix|C_max,在网络并行计算、多播系统及工程规划等领域都有广泛的应用。该问题早已证明为NP难问题,而且也不存在常数近似算法。基于部分调度和宽度优先原则构造了该问题的一个多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为2m+1,优于已有文献中2m的目前最好结果。     

基于层次化调度策略和动态数据复制的网格调度方法

针对在网格中如何有效地进行任务调度和数据复制, 以便减少任务执行时间等问题, 提出了任务调度算法（ISS）和优化动态数据复制算法（ODHRA）, 并构建一个方案将两种算法进行了有效结合。该方案采用ISS算法综合考虑任务等待队列的数量、任务需求数据的位置和站点的计算容量, 采用网络结构分级调度的方式, 配以适当的权重系数计算综合任务成本, 搜索出最佳计算节点区域; 采用ODHRA算法分析数据传输时间、存储访问延迟、等待在存储队列中的副本请求和节点间的距离, 在众多的副本中选取出最佳副本位置, 再结合副本放置和副本管理, 从而降低了文件访问时间。仿真结果表明, 提出的方案在平均任务执行时间方面, 与其他算法相比表现出了更好的性能。     

Hadoop下资源匹配最大集作业调度算法

针对目前层级队列作业调度算法中资源占比高的作业执行效率低的问题,提出一种资源匹配最大集算法。该算法分析作业特征,引入完成度、等待时间、优先级、重调度次数为紧迫值因子,优先考虑资源占比高或等待时间长的作业,以改善作业公平性;采用双队列结构在可用资源总量内优先选择高紧迫值作业,在不同资源占比作业集比较中选择作业数最大集,以实现调度平衡。在与最大最小公平(Max-min fairness)算法的实例对比中发现,该算法可降低作业集平均等待时间、提高资源利用率。实验对比结果表明,该算法可将不同资源占比的单一类型作业集执行时间缩短18.73%,其中资源占比高的作业执行时间缩短27.26%;在混合型作业集中对应的执行时间可分别缩短22.36%与30.28%。所提算法能有效减少资源占比高作业的等待,提高作业整体执行效率。     

基于Hadoop的三队列作业调度算法

Hadoop集群单队列作业调度会产生短作业等待、资源利用率低的问题;采用多队列调度可兼顾公平、提高执行效率,但会带来手工配置参数、资源互占、算法复杂等问题。针对上述问题,提出三队列作业调度算法,利用区分作业类型、动态调整作业优先级、配置共享资源池、作业抢占等设计,达到平衡作业需求、简化一般作业调度流程、提升并行执行能力的目的。对短作业占比高,各作业占比均衡以及一般作业为主,偶尔出现长、短作业三种情况与先进先出(FIFO)算法进行了对比实验,结果三队列算法的运行时间均比FIFO算法要少。实验结果表明,在短作业聚集时,三队列算法的执行效率提升并不显著;但当各种作业并存且分布均衡时,效果很明显,这符合了算法设计时短作业优先、一般作业简化流程、兼顾长作业的初衷,提高了作业整体执行效率。     

基于LSTM的集群用户作业执行时间预测模型

为提升服务质量,数据中心需要确保在规定的截止时间前完成用户作业,因此必须根据实时的系统资源对作业进行有效的调度。提出了一种作业调度算法,根据预测的作业执行时间进行批作业调度,以最小化批作业的完成时间。作业执行时间预测模型基于长短期记忆LSTM网络,根据用户作业类型、作业量、作业需要的CPU核数和内存数量,以及作业需要的资源在系统总资源中的占比,对用户作业的执行时间进行预测。预测结果用于判断集群是否有能力按时完成用户作业,同时为合理安排各作业的执行顺序提供依据。通过实验确定了影响LSTM时间预测模型性能的各超参数取值,如迭代次数、学习率和网络层数等。实验表明,与SVR模型、ARIMA模型和BP模型相比,基于LSTM的作业执行时间预测模型的决定系数R²分别有2.97%,2.34%和5.66%的提升效果,且预测的平均误差仅为0.78%。     

一种基于流作业的网格作业调度研究

在基于网格环境的一些网格应用中,用户需要提交一种作业类型,该作业可以被分解为逻辑上独立的元作业,这些元作业不存在依赖和通讯关系,并且它们的执行需要大量的数据移动。针对这种作业类型,本文提出了一种基于流作业的网格调度模型。在该模型中,这些独立的元作业像"流"一样自主地流向各个计算节点去执行,各计算节点接收的流量取决于其计算能力,并避免"断流"问题。同时,该模型还分离了作业流和数据流,实现了作业逻辑控制和数据控制的分离,提高了调度的灵活性。本文将该调度模型应用于药物虚拟筛选应用中,该模型能够充分利用计算节点的计算能力。     

Characterization of Bandwidth-Aware Meta-Schedulers for Co-Allocating Jobs Across Multiple Clusters

In this paper, we present a bandwidth-centric job communication model that captures the interaction and impact of simultaneously co-allocating jobs across multiple clusters. We compare our dynamic model with previous research that utilizes a fixed execution time penalty for co-allocated jobs. We explore the interaction of simultaneously co-allocated jobs and the contention they often create in the network infrastructure of a dedicated computational multi-cluster.We also present several bandwidth-aware co-allocating meta-schedulers. These schedulers take inter-cluster network utilization into account as a means by which to mitigate degraded job run-time performance. We make use of a bandwidth-centric parallel job communication model that captures the time-varying utilization of shared inter-cluster network resources. By doing so, we are able to evaluate the performance of multi-cluster scheduling algorithms that focus not only on node resource allocation, but also on shared inter-cluster network bandwidth.     

基于Petri网的JSP动态优化调度

提出一种在柔性制造系统动态优化调度中处理紧急定单的方法。以带有控制器的 Petri 网为建模工具对柔性生产调度中的离散事件建模,对系统的设备维护、各种优先级等特性进行描述,利用遗传算法和模拟退火算法获得调度结果,用于解决作业车间的加工受到机床、操作工人等双资源制约条件下的动态优化调度。当有紧急定单需要加工时,该方法把剩余任务和紧急任务作为两个独立的任务分别处理,然后进行集成,在紧急任务为最优调度的基础上选取剩余任务的最优调度,找到兼顾整体和局部的最优解。仿真结果说明了算法的有效性和鲁棒性。