云计算环境下多级映射作业调度算法的研究

云计算是一种新兴的资源使用和计算交互模式,是目前商业机构和科研机构的研究热点之一.在云计算环境中用户需求和资源的分布对该环境中作业调度的影响很大,虚拟技术的使用使云计算环境中的作业调度与传统的作业调度存在很大的差别.针对云计算环境特点,根据用户的需求将作业进行分类,同时将资源分类,引入中间代理节点进行任务调度,形成多级映射作业调度算法,提高作业的并发度,使总任务完成时间缩短.通过实验验证多级映射作业调度算法是一种可行的作业调度算法.     

云环境下基于双重公平性约束并行调度算法的研究与实现

目前并行调度和资源分配一般只注重效率,但是云计算需要给各用户提供多种不同服务,所以需要高度关注用户需求满足度.提出一种基于云计算环境下的并行作业调度算法,该算法对传统并行作业调度算法仅仅注重效率的特点进行了改进,关注资源分配的公平性、任务的完成效率和用户服务质量以及系统的负载均衡性,能够适应云计算的虚拟化和商业化特性,并实现在云计算环境下的并行作业调度中形成双重公平性约束.在注重效率的同时,突出资源分配的公平性.     

一种短作业环境下的延迟调度算法

针对短作业场景下YARN平台中延迟调度算法基于静态时间等待阈值,不能进行合理等待的问题,提出了一种云计算环境中基于本地性资源预测的延迟调度算法(locality resource forecast delay scheduling,LRFD)。该算法综合考虑短作业和资源可用性动态变化的特点进行任务调度,根据节点上任务的完成进度和作业未处理数据在集群中的分布状况预估作业的本地性资源信息,从而判断是否需要进行等待以提高系统性能,实现了对本地性资源的合理等待。实验结果表明:在短作业场景下,LRFD算法的性能和稳定性均优于已有的延迟算法,作业性能平均提升约10%,最大加速比可达3倍以上。     

基于并行遗传算法的车间作业调度

研究了并行遗传算法在车间作业调度问题中的应用,通过对传统的迁移策略进行改进,给出了运用该算法求解车间作业调度的具体过程。最后给出了计算机仿真结果,与普通遗传算法求得的结果的比较,证明了该算法的有效性和先进性。     

云计算环境中三层架构的资源负载均衡研究简

为了使云环境中资源能更加高效、合理地运转,该文探求使用新的调度策略来使系统达到负载均衡,提出了一个在三层架构云计算网络环境中的两阶段调度算法.该算法结合了随机负载均衡算法和Min-Min负载均衡调度算法的特性,从而能更高效率地执行任务并使系统达到负载均衡.     

异常网络环境下云计算资源需求策略

针对常规云计算资源预测算法不能在异常网络环境下做到精准预测的难题,提出一种基于改进蚁群算法的调度策略.该策略融入了信息数的概念,既能快速均衡负载,又能保障用户在多条件下云计算的需要,合理降低能耗,提高云计算性能.实验结果表明,基于改进的蚁群调度算法提高了云计算资源利用率,降低了能量消耗,使单节点处理任务量有较大提升,极大提高了云计算的性能和服务质量.     

基于过滤定向搜索的柔性制造系统动态调度优化

针对柔性制造环境中内外扰动的动态随机发生和快速、高效的重调度需求,构建了动态调度决策系统结构模型,提出了一种基于过滤定向搜索的启发式算法作为模型的核心算法.为了更好地搜索调度解空间和更好地集成作业的交货期、优先权重和资源负载平衡,算法改进了节点分枝策略和局部、全局评价函数.以作业交货延迟时间加权平方和最小为性能指标,通过实例仿真,对算法性能进行了分析评价和比较,结果表明了该算法对实现柔性制造系统动态调度的有效性和实用性.     

面向异构集群的作业调度与资源分配研究

提出一种面向异构集群的作业调度与资源分配策略,在异构资源实时监控的基础上,实现了作业的有效调度,进而在作业执行阶段,采用基于二部图的最小权匹配的资源分配算法,实现异构资源到执行任务的合理部署与配置.以医学科学计算为背景,搭建了异构云计算环境,并进行了仿真实验.实验结果显示:提出的算法实现了预期的目标,有效弥补了现有同构作业调度算法的缺陷与不足.     

云计算中基于遗传算法的任务调度算法研究

为解决云计算中的任务调度问题,提出了一种以遗传算法为基础的任务调度模型.在算法初始化种群产生时通过染色体匹配率来使种群个体均匀分布在解空间上,有效地避免了早熟;引入服务质量标准进行建模以改进适应度函数,充分考虑用户对调度结果的满意程度;采用规则约束的交叉和变异操作,提高个体的质量.仿真实验的结果分析表明:该改进算法能更有效地求解云计算环境下作业调度问题.     

云计算环境下的动态反馈作业调度算法

针对现有Hadoop作业调度算法在多用户、异构环境下不具备反馈机制的问题,提出一种云计算环境下具备反馈机制的动态作业调度算法。该算法引入排队论模型,采用单队列多资源池服务窗口的设计思路,将所有作业统一提交到一个支持优先级的排队队列,作业分发控制模块选择优先级最高的作业分发到空闲的资源池窗口执行;Hadoop集群通过自身的心跳机制将作业运行的初始化时间、运行时间等信息传递给参数统计模块进行统计,将获得的平均到达率和平均服务率这两个核心参数的实际值传递给反馈机制模块,根据调度算法模型计算出平均逗留时间和平均队长的理论值并与实际值进行对比,当差值大于阈值时对该调度算法的核心参数进行适当调节使差值收敛于阈值,将具有较大平均逗留时间和平均队长的作业调度到有槽位数的资源池服务窗口执行。实验结果表明:与经典算法相比,该算法具有较高的调度效率和负载平衡能力,作业平均逗留时间比先进先出调度算法和公平调度算法分别减少了57%和19%,平均队长分别减少了50%和37%。     

HowU网格资源管理及调度

讨论了一种基于web的HowU网格系统的实现,以及采用的关键技术．HowU网格系统通过资源请求代理进行网格作业提交,HowU网格系统采用了网格资源的分层管理策略及全局调度思想．根据网格的特性,并针对CPU性能对作业调度的影响,提出了三种全局资源调度算法：资源轮转法;当前最优资源优先调度法;最优资源优先调度法．研究结果表明,当作业数量比较少时,资源轮转法优势最明显,最优资源优先调度法性能最差．但当作业数量增大时,资源轮转法性能明显下降,而最优资源优先调度法比其他两者更有性能优势．     

网络动态调度系统的服务质量性能分析

提出了考虑具有不同输入速率和输出速率的任务队列的网络动态调度系统状态空间模型,描述了网络动态调度系统的清空型调度策略,并在此基础上给出了系统服务质量性能指标包括队列长度、总任务数量、系统吞吐量、响应时间等的分析算法. 数值计算表明,适当的调度策略可以使网络动态调度系统的响应时间处于受控的范围内,系统吞吐量处于稳定的状态.     

加工时间依赖于开工时间的单机排序问题

讨论了加工时间依赖于开工时间的单机排序问题．在这一模型中每个工件具有一个基本加工时间，当工件的开工时间超过某个共同的工期后，工件会有一个时间惩罚．本文就目标函数为极小化最大完工时间和总完工时间的问题进行了讨论，对某些特殊情况给出了多项式算法.     

云计算下均衡负载的差异性资源调度算法优化研究

随着云计算的逐渐发展,云计算下容易出现虚拟机负载不均衡和差异性资源调度时间长的问题,当前调度算法大多无法有效解决均衡负载问题,影响调度性能。为此,提出一种新的云计算下均衡负载的差异性资源调度算法,对云计算下资源调度问题进行描述,针对云计算下虚拟机差异性资源负载问题设定参数。设计蚁群优化算法,蚂蚁爬行的每一步代表指派的一个差异性资源任务,引入挥发因子对信息素更新规则进行改进,获取全局信息素。利用蚁群优化算法对云计算下负载的差异性资源进行均衡调度,给出详细实现过程。实验结果表明,所提算法有较好的收敛性,均衡负载效果好,且时间复杂度低。     

资源短时占用型作业调度算法

对资源短时占用型作业调度的问题给出了一个数学描述模型 ,并讨论了该问题求解的时间复杂性 .基于该模型提出了对不同情况最佳或近似最佳的实用的联机调度算法 ,并讨论了这些算法在其他类似问题上的应用 .     

带有交货期窗口和工件可拒绝的单机排序问题

讨论了带有交货期窗口和工件可拒绝的单机排序问题﹐这一问题是将所有的工件分成两个集合﹐一个是被接受的工件集﹐一个是被拒绝的工件集。假设被接受的每个工件都有一个待定的交货期窗口﹐且所有工件的交货期窗口的大小是相同的﹐如果工件在窗口中完工﹐则不产生任何费用;否则工件提前或延误﹐会产生相应的提前或延误的费用。而对于拒绝工件而言﹐它的费用只与工件有关。这类问题的总费用是2个工件集的费用之和。目标函数是确定被接受工件的最优排序﹐极小化总费用﹐给出了一个动态规划算法﹐并证明了这个问题是多项式时间可解的。     

带有线性退化工件和退化维护时间的单机窗口排序

排序问题是一类重要的组合最优化问题,它的深刻的实际背景和广阔的应用前景,引起了广泛的关注。排序问题的一大特点是模型繁多,适用于某一模型的算法,只要将模型的条件稍加变化,该算法就可能不适用。在经典排序问题中,通常假设工件的加工时间是不变的,然而,在许多实际问题中,工件的加工时间受到加工机器设备、工件本身、加工顺序等许多因素的影响而未必是恒定的。文章提出一类新型的排序问题——带有工期窗口和维护时间的线性退化工件的单机排序问题,目标是寻找:1)最优维护的开始时间;2)工期窗口的位置和大小;3)工件的最优排序使得提前完工、误工、工期窗口开始时间和窗口宽度的总费用最小。文章最后给出了这个问题的最优算法,其时间复杂性是O(n2logn)。     

流水作业由二台柔性机器组成时的极小完工时间之和问题

该文考虑下述由2台机器组成的流水作业问题:n个相同工件需依相同次序在机器1、2上共进行3次加工.工件j的第一次加工在机器1上进行,所需时间为p1;其第二次加工或单独在机器1上或单独在机器2上进行,当工件j的第二次加工在机器1上进行时,所需时间为p12,当工件j的第二次加工在机器2上进行时,所需时间为p21;其第三次加工需在机器2上进行,所需时间为p2.要求适当安排这n个工件的加工方式以使它们的完工时间之和达到极小.对该问题作者对应不同情况给出了不同的最优解法.     

具有预约到达时间的平行机在线排序问题研究

以现代服务业预定系统中的实际问题为背景,研究了一类具有预约到达时间和最迟完工时间的在线排序问题;论证了两台机器时该问题的在线算法竞争比下界为2;在传统在线排序算法的基础上提出了针对该问题的在线贪婪算法,并分析了该算法的竞争比.     

WebitOS中动态优先级调度机制及EDF算法的实现

在实时系统中,相对于静态优先级调度机制而言,动态优先级调度机制因其可以为每个任务的各个作业设置不同的绝对时限而更好地反映了实时系统对于所调度的各个任务的时限要求.基于最早时限优先(earliest-deadline-first EDF)算法的高可调度利用率,在WebitOS实时操作系统中设计并实现了动态优先级调度机制,并且提出了一种早期丢弃规则.实验结果表明,该规则提高了EDF算法在超载情况下的整体调度性能.