基于多目标冲突度网格任务调度策略

针对网格计算中多目标之间存在冲突的独立任务调度问题,应用多目标线性规划为系统建模,通过求解多目标线性规划的梯度向量来确定多目标之间的冲突度,形成多目标冲突度网格独立任务调度模型。提出该模型预处理算法和多目标冲突度遗传算法,这两个算法确保网格用户在多目标维度下的效用值最大化。实验结果表明,在时间、安全性、可靠性维度和丢弃任务数等指标方面,该算法的综合性能优于Max-min和T-Sufferage算法。     

云计算环境下基于时间期限和预算的调度算法

现有的云计算作业调度算法研究较少考虑时间期限和预算对作业调度策略的影响.针对动态变化的云计算环境下,具有时间期限和预算双重约束的用户需求优化问题,提出一种改进的云计算调度算法,设计权值计算模型、预算评价模型和权值更新模型,通过动态调节作业权值和最小资源槽数来控制集群对资源的分配.在Hadoop平台上进行实验,结果表明,该算法能减少作业响应时间,并且可在满足用户对时间期限和预算的需求基础上,最大化云计算集群中运行的作业数,提高不同用户在时间和预算需求上的公平性.     

提高用户满意率的服务器主动调度算法

在集群环境中,为了实现多台计算机协同工作,充分利用服务器的计算能力,需要选用恰当的负载均衡策略.目前常用的服务器调度策略只是从服务器角度出发,实现硬件负载的均衡,而忽略了服务质量.本文算法定义了用户满意率(即“用户期望的任务完成时间“与“任务实际完成时间”的比值)指标来评价服务质量.算法综合用户权值,任务所属类别历史平均计算时间,用户期望计算时问,任务添加时间等四个因子,计算任务权值,然后由服务器主动按照任务权值高低进行调度.试验结果表明,该算法能够有效提高用户的满意率,充分利用服务器的计算资源.     

云环境下的基于Min-Max的节能资源调度算法的研究

针对云计算环境下的高能耗问题,从系统节能的角度提出一种节能资源调度算法(energy-saving scheduling algorithm based on min-max,ESSAMM)。在Min-Max算法的基础上综合考虑了用户对于任务期望的完成时间和能量消耗两个因素,以节省任务执行过程中产生的能量消耗,并提高用户的时间QoS满意度,实现负载均衡。将任务集合中各任务按照长度从小到大排序,并根据时间QoS为该集合中长度最大和最小的任务选出符合用户期望的物理资源;根据能量估算模型,计算出这两个任务在各物理机上的执行能耗;选择最小能耗对应的物理机来执行该任务;将这两个任务在任务集合中删除,并重复上述过程,直到任务集合为空。仿真结果表明,相比于Min-Max和Min-Min资源调度算法,该算法能够有效降低系统执行任务产生的总能耗,提高用户时间服务质量,并实现调度系统负载均衡。     

IaaS云满足预算约束的工作流应用调度算法

为了解决IaaS(Infrastructure as a Service)云的工作流调度优化问题，提出基于预算约束的工作流调度算法。以最小化工作流调度时长为目标，算法分调度任务选择和虚拟机实例选择两阶段进行。第一阶段将工作流任务依据依赖关系作层次划分，同层次组成包任务，以Min-Max方法对层次任务估算时间作标准化处理，定义最迟完成时间与最早完成时间差值最大者为调度任务；第二阶段在期望预算下以最早完成时间最小为标准选择资源，实现任务与资源间的映射。利用算例阐述了算法实现过程，并通过仿真实验测试了算法性能。结果证实，改进算法执行效率与调度成功率优于同类算法。     

Hadoop平台下的动态调度算法

目前,云计算环境具有动态、异构和海量多类型任务并发等特征,随着集群规模不断增大、用户QoS不断增多,现有调度算法越来越难以适应动态变化的环境及满足用户的需求。针对Hadoop平台下现有调度器不能根据作业运行状态和资源使用情况进行动态调整的问题,提出了Hadoop下基于作业分类的动态调度算法。该算法在使用朴素贝叶斯分类算法对队列中作业进行分类的过程中,根据各个作业的类型,预先设定类别权值,将队列中的作业分类,并引入效用函数,根据用户提交时的预期完成时间QoS和作业完成情况估算其作业完成时间,实现动态设置作业优先级。实验表明,使用提出的算法不仅能有效减少 作业的分类时间,而且能明显提高 动态性和用户QoS。     

共享单车维护任务完成概率防策略机制设计

共享单车作为一种绿色低碳的出行方式,给人们的出行带来便利。然而,人们自由使用单车给共享单车的维护带来许多问题(例如需要将某个区域无序放置的单车送到某个指定位置),因此,共享单车平台可能需要雇佣用户去完成单车维护任务,同时平台需要给予用户合理的报酬以激励用户完成任务。当存在多个用户竞争时,用户可能谎报任务完成概率来获得更高的报酬,从而导致平台最终不能完成所有的维护任务。考虑用户在任务完成概率方面的策略行为,在满足一定任务完成概率的情况下,设计防策略性机制,实现完成维护任务完成成本最小化。该机制包括任务分发算法和用户定价算法,其中任务分发机制采用贪心算法思想进行设计,而用户定价算法则通过迈尔森定理来设计。理论证明该机制满足激励相容性和个体理性,接着进一步基于摩拜单车数据集来评估该机制的性能,主要包括任务完成成本、用户平均期望效用、用户期望效用概率密度等评价指标。通过与VCG机制相比较,该机制能够达到常数倍的近似比,任务完成成本更低,用户平均期望效用更高,并且能够防止用户在任务完成概率方面的策略行为。     

网格计算中费用约束的最优时间调度算法

在网格资源处理速度和资源价格异构的网格环境下,讨论基于用户费用约束的最优时间调度问题,提出一种相应的调度算法,将该任务调度问题转化为线性规划问题,采用单纯形算法获得近似最优解,从而获得费用约束下资源的最优执行时间以及该任务的最小完成时间。仿真结果表明,该算法的性能优于其他同类算法。     

基于任务复制的多维QoS云计算任务调度

为了满足云计算环境下用户服务质量(QoS)需求和提高虚拟资源空闲时间段的利用率,提出了一种基于任务复制的多维QoS任务调度策略。首先,构建云资源模型和用户QoS模型,然后根据虚拟资源的利用情况和QoS的满意度对虚拟机进行性能测评,选择综合性能更高的虚拟资源进行任务的分配;在任务执行时为了缩短任务的完成时间,在调度过程中引入了在空闲时间段复制父任务的方式。通过仿真实验将该算法与HEFT、CPOP进行比较,实验结果显示：当用户偏好可靠性执行时,该算法平均可靠性比HEFT和CPOP高;当用户偏好完成时间和费用花费执行时,该算法平均完成时间比HEFT和CPOP少;当用户无偏好执行时,该算法平均完成时间和平均花费均比HEFT和CPOP少。结果表明该算法能有效提高资源利用率和用户的满意度。     

云环境中面向随机任务的用户效用优化模型

资源分配方法和技术一直是云计算领域中的热点问题,现有的解决方案在资源分配与调度方面未能充分考虑用户的实际需要,首先通过引入用户效用的概念,建立了云环境中用户效用的描述模型,给出了用户对任务执行时间和费用满意程度的量化方法,并针对用户任务到达时间和任务类型的随机性,基于线性规划理论提出了云环境中面向用户效用的任务调度优化模型.该模型以任务完成的总效用值为目标,以用户任务的预期时间、费用和并行加速比为约束条件,能真实描述用户任务的随机性,面向时间和费用两个现实目标,求解出最合适的计算资源和排队秩序.最后通过实验表明,这种云环境中的任务调度方法能有效地满足用户对任务执行时间和费用的需求.     

物联网环境下具有顺序约束关系的静态任务表调度算法

针对物联网异构调度环境下并行计算的静态任务调度问题,提出了一种基于最早完成时间策略改变调度顺序的表调度算法HDPTS。该算法针对现有表调度算法在调度前不能准确地确定调度顺序的问题,在IHEFT算法的基础上添加了一个动态优先级调度策略,当节点的前驱任务都已经完成调度任务时,就改变该节点的调度优先级。任务优先级的计算在所有前驱任务到达这个任务的最晚完成时间与所有资源上最大可以使用时间之间取最大值的基础上,同时考虑到分配到各个资源上的任务对后继任务的影响和资源上的负载情况,以及上行权重的计算值和对出口任务的影响,使得优先级计算更加合理,能够根据任务分配动态合理改变任务调度顺序。通过随机生成一个算例进行测试,结果表明HDPTS比IHEFT、HEFT在调度长度方面减少14.29%;对大量随机产生的特定结构的有向无环图(DAG)进行测试,测试结果显示HDPTS算法比IHEFT、HEFT和LDCP算法更有效。     

异构计算环境下基于优先队列划分的调度算法

人工智能的飞速发展对高性能计算提出了更高的要求,异构计算环境下任务调度问题一直是高性能计算中的关键问题.本文提出一种基于优先队列划分的调度算法(PQDSA),该算法根据DAG(有向无循环图)任务集的入口节点数量确定优先队列数,通过任务的通信开销和计算开销划分任务队列,进而将关键节点任务分配给合适的队列,以产生效果较佳的任务调度队列,从而提高任务间的并行性,降低任务集的完工时间.与此同时,进一步基于插入策略将任务调度到处理器上,使任务调度更加高效地执行.PQDSA算法可以减少任务间的时间消耗,提高处理器的调度效率.通过与两个经典算法的性能对比,实验结果表明本文提出的PQDSA算法在任务完工时间和调度效率方面都要明显优于对比的算法.     

Workload-based multi-task scheduling in cloud manufacturing

Cloud manufacturing is an emerging service-oriented business model that integrates distributed manufacturing resources, transforms them into manufacturing services, and manages the services centrally. Cloud manufacturing allows multiple users to request services at the same time by submitting their requirement tasks to a cloud manufacturing platform. The centralized management and operation of manufacturing services enable cloud manufacturing to deal with multiple manufacturing tasks in parallel. An important issue with cloud manufacturing is therefore how to optimally schedule multiple manufacturing tasks to achieve better performance of a cloud manufacturing system. Task workload provides an important basis for task scheduling in cloud manufacturing. Based on this idea, we present a cloud manufacturing multi-task scheduling model that incorporates task workload modelling and a number of other essential ingredients regarding services such as service efficiency coefficient and service quantity. Then we investigate the effects of different workload-based task scheduling methods on system performance such as total completion time and service utilization. Scenarios with or without time constraints are separately investigated in detail. Results from simulation experiments indicate that scheduling larger workload tasks with a higher priority can shorten the makespan and increase service utilization without decreasing task fulfilment quality when there is no time constraint. When time constraint is involved, the above strategy enables more tasks to be successfully fulfilled within the time constraint, and task fulfilment quality also does not deteriorate.     

面向依赖关系约束的移动群智感知任务协作

现有移动群智感知中,大多研究将每个任务作为独立个体进行处理,对任务间约束关系缺乏研究,为此,提出了基于感知质量优先级的在线任务协作方法（online task collaboration method based on sensing quality priority,TCSP）。该方法首先使用贪婪算法计算感知质量优先级,对全部任务进行筛选以保证任务完成率;然后将选出任务中存在时间先后或执行逻辑前后关系的多个子任务构建为任务协作图,并将其协作过程建模为有约束的马尔可夫决策过程,通过强化学习算法求出最优协作策略。实验结果表明,与现有基线方法相比,所提出的任务协作方法能够减少依赖任务的平均完成时间,有效降低平台的平均感知成本。     

改进的最小空闲时间优先调度算法

最小空闲时间优先(least slack first,简称LSF)算法结合任务执行的缓急程度来给任务分配优先级.任务所剩的空闲时间越少,就越需要尽快执行.然而,LSF算法造成任务之间的频繁切换或严重的颠簸现象,增大了系统开销,并限制了其应用.在调度策略中设置抢占阈值可以减少任务之间的切换,但现有的抢占阈值设置方法因受到固定优先级的限制而不适用于LSF算法.为了减轻LSF算法的颠簸现象,基于抢占阈值的思想,提出适用于LSF算法的抢占阈值分配方法,动态地给每个任务配置抢占阈值.任务的抢占阈值是随着任务执行的缓急程度不同而动态地变化的,而且不受任务个数的限制.仿真结果表明,通过对LSF算法的改进,任务之间的切换大大减少,同时降低了任务截止期错失率.该改进型算法对设计和实现实时操作系统具有一定的参考价值.     

A Feasibility Decision Algorithm for Rate Monotonic and Deadline Monotonic Scheduling

Rate monotonic and deadline monotonic scheduling are commonly used for periodic real-time task systems. This paper discusses a feasibility decision for a given real-time task system when the system is scheduled by rate monotonic and deadline monotonic scheduling. The time complexity of existing feasibility decision algorithms depends on both the number of tasks and maximum periods or deadlines when the periods and deadlines are integers. This paper presents a new necessary and sufficient condition for a given task system to be feasible and proposes a new feasibility decision algorithm based on that condition. The time complexity of this algorithm depends solely on the number of tasks. This condition can also be applied as a sufficient condition for a task system using priority inheritance protocols to be feasible with rate monotonic and deadline monotonic scheduling.     

Scheduling parallelizable tasks to minimize make-span and weighted response time

This paper presents a generalization to classical scheduling theory by removing the restriction that only one processor can work on a given task at a particular time. Instead, it is assumed that each task can be allocated any number of identical processors from one to the maximum number available, with each task's completion time being a function of the number of processors allocated. Tasks may be started any time, but once started, a task must not have its processor allocation altered or be preempted. Two objective functions are considered: minimizing the overall completion time for the tasks (make-span) and minimizing a weighted sum of the task completion times (weighted response). Both are considered subject to a constraint on the total number of processors available. Suboptimal algorithms are developed for both of these NP-hard problems using Lagrangian relaxation, and their performances are analyzed through extensive simulations. Duality gaps for all problems tested ranged from under 1% to 92%, depending more on the problem size than the specific problem.     

SAGA:一种面向任务的卫星网络资源分配算法

针对现有卫星网络多资源、多任务约束下的资源分配,没有同时考虑任务完成时间和任务优先级导致的任务总体完成时间过长、任务优先级匹配度不高等问题,定义了任务序列优先级逆序数,建立了以任务总体完成时间最短和任务序列优先级逆序数最小为目标的约束模型,提出了一种自适应遗传算法并对模型进行求解.该算法利用精英保留的思想改进了采用轮盘赌策略的选择算子并且给出了一种能够自适应更新自身概率的变异、交叉算子,解决了标准遗传算法容易陷入局部最优的缺陷,避免了最优解的丢失.仿真实验验证表明,本文算法在任务总体完成时间方面降低了15.84%,在优先级逆序数方面降低了24.32%,有效解决了卫星网络多资源、多任务约束下的多目标分配问题.     

A shelf-based Lagrangian relaxation algorithm to scheduleparallelizable tasks

This paper generalizes classical scheduling theory by removing the restriction that only a single processor can work on a given task at a particular time. Instead, it is assumed that each task can be allocated any number of identical processors from one to the maximum number available, and that a task's completion time is a nonincreasing function of the number of processors allocated. Once started, a task must run to completion without altering the number of processors given to it. Furthermore, a task can start only when no task is currently executing. The objective considered is minimization of overall completion time (make-span) for the tasks subject to the constraint of a limited number of available processors. To approximately solve this problem, an algorithm based on Lagrangian relaxation is developed, and its performance is analyzed through extensive simulations. Approximate duality gaps range from 0 to about 60% on average and are strongly a function of problem type and size     

采用配置完成优先策略的可重构任务调度算法

如何隐藏和减少配置时间是相依性可重构任务调度的关键问题.提出一种采用配置完成优先策略的相依性可重构任务调度算法,通过基于预配置优先级的列表调度算法,实现将后续任务的配置时间隐藏于前驱任务的运行时间中,并采用基于配置完成优先策略的配置重用机制,减少了任务调度后的配置过程,从而在总体上缩短了相依性任务集合的运行时间.仿真结果表明,该调度算法能有效避免调度死锁,并可减少相依性可重构任务的整体运行时间.