一种适于异构环境的任务调度算法

针对异构环境独立任务调度问题提出两个调度原则,并基于Min-min算法提出优先级最小最早完成时间算法(Priority min-min,PMM).该算法将任务在各处理机上执行时间的标准误差作为任务的优先级.选取最早完成时间较小的k个任务,优先调度其中优先级最高的一个.在实验基础上分析了参数$k$对PMM算法性能的影响. PMM算法克服了min-min算法单纯追求局部最优的局限性,更适合于异构环境.实验数据表明PMM算法能有效地降低调度跨度,其性能比min-min算法有明显提高.     

异构环境下独立任务调度算法的研究

本文基于Min-min算法和Sufferage算法提出了基于任务调度损失的最小最早完成时间算法(Sufferage Min-min,SMM).该算法将任务调度损失引入Min-min算法,选取最早完成时间较小的k个任务,再优先对其中任务调度损失最大的一个进行调度.SMM算法克服了Min-min算法单纯追求局部最优而缺少全局意识的缺点.测试表明,SMM算法可以做到调度跨度低与平均等待时间小的统一,在综合性能上较Min-min算法有所提高.     

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

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

基于多处理机的混合实时任务容错调度

提出了一种混合实时任务容错调度算法．该算法采用Rate Monotonic(RM)算法完成周期任务的静态调度；采用预订处理机时间方法和Earlier Deadline First(EDF)算法动态调度非周期任务；采用主／副版本备份技术确保系统的容错能力．通过充分利用周期任务的剩余处理机时间调度非周期任务和主动备份与被动备份相结合的方法有效地减少了处理机数．仿真结果证明了算法的有效性．     

基于多QoS约束的数据网格任务调度算法研究

针对数据网格环境下的多QoS约束任务调度问题,提出了一种基于最早完成时间与QoS相识度的数据网格任务调度算法(data grid task scheduling algorithm based on Min-min and QoS similarity,MS-GTSA).该算法将最早完成时间与S-GTSA算法相结合,在任务调度过程中,选取任务QoS约束与资源QoS匹配最佳,且完成时间最早的一项优先进行调度.在满足任务最佳QoS匹配的同时,时间跨度得到了较大的改善.仿真结果表明,该算法有效降低了任务调度的时间跨度,在综合性能上较S-GTSA算法有所提高.     

考虑通信竞争的任意处理机网络表调度算法

任务调度是高性能计算系统中的基本问题之一。解决此类NP难问题的经典启发式算法都假定目标处理机全互连,调度任务时可忽略节点间通信,这显然与实际计算环境不符。为此,文中提出一种在调度任务时同时考虑通信边调度的表调度算法。在边调度时,提出了一种基于最短路径搜索算法的最早通信完成路径查找算法(EFCS),并采用插入式链路策略实现通信边的动态调度,而对处理机网络异构环境下的任务优先级计算问题,受HEFT算法启发,提出异构系统递归优先权计算方法,按非升序排列获得各任务优先级。为了降低算法的执行时间,文中还提出了理论加速比为O(PPE)的并行算法。以随机产生程序任务图和DSP应用程序实例为数据源,在两类不同任意处理机网络目标系统上进行的模拟实验结果表明:本算法明显优于考虑通信竞争的静态表调度算法和不考虑通信竞争的表调度算法,特别是在高通信率应用程序中优势更明显。     

端到端时间约束的实时任务动态调度算法

在单处理机系统中,由于计算高优先级任务抢占的时间相对比较简单,所以单处理机调度理论取得了长足的进步.提出一个端到端时间约束的实时任务调度算法,当实时任务到达系统时,算法为任务的每个子任务在相应的处理机上预约一定的计算资源,把端到端的多处理机调度问题转换成单处理机调度问题,从而可以利用单处理机调度理论判定实时任务的可调度性.实验表明,该算法明显地提高了CPU利用率和任务接收率.     

异构多核处理器的任务调度算法

在研究Min-min、Max-min算法和Sufferage算法基础上,针对异构多核处理器的特点,提出一种任务静态调度算法——自适应分段Sufferage算法（Adaptive Segmented Sufferage,ASS）。该算法以最早完成时间和负载均衡为目标进行任务分配,先将任务分配分成两个阶段：在第一个阶段以最少完成时间作为分配原则进行分配,选择单位时间内节省时间最多的任务先分配;在第二个阶段以负载均衡为分配原则进行分配,选择执行时间大的任务先分配。然后选取不同调节参数,对任务进行多次重新分配,以最小的最大完成时间为最后分配结果,实现自适应调节。通过实验验证,该算法在实现最少完成时间的前提下能很好地达到负载均衡。     

一种成本和时间均衡的网格资源分类优化调度策略

针对时间和成本约束的网格资源调度问题,提出一种基于MinCTT算法的时间和成本均衡的网格资源分类优化调度算法.该算法综合考虑任务完成时间和执行成本两个QoS因素,由一个成本比值和时间比值的联合均衡值来综合衡量任务在资源上的完成时间和执行成本开销,根据任务估计平均价格,对资源进行分类调度.实验结果表明,该调度算法具有较好的调度性能,能有效的减少任务总的完成时间和执行成本,均衡因子的改变对该算法的调度性能影响较小,选择合适的均衡因子能实现优的调度.     

一种高回报的最小空闲时间优先实时调度改进算法

信号任务调度算法是提高信息物理系统执行效能的关键,而最小空闲时间优先算法(LSF)、最早截止时间优先算法(EDF)和最大价值优先算法(HVF)在系统满载的情况下无法很好地完成任务调度并且系统能耗很高。为此,提出一种改进型调度算法。将任务能耗、任务完成价值和任务紧迫程度相结合,通过引入任务调度优先级和任务实际调度优先级的形式,实现任务的动态调度。实验结果表明,对于同一个任务集,在完成相同调度任务数量的情况下,改进算法的系统能耗小于采用LSF算法和EDF算法的系统能耗。系统满载时,在完成任务总价值相同的情况下,采用改进算法的系统所需要的能耗比HVF算法更少。     

基于优先级和优化完成时间的网格调度算法

网格由大量的异构资源组成，具有复杂性、动态性和自治性特点。高效的网格调度算法可以充分利用网格系统资源，提高网格处理应用程序的能力。Min min算法是一个简单、快速、有效的调度算法，但由于总是先分配小任务而不能确保负载平衡。文中首先对网格系统中任务的数据传输和执行进行分析，计算并优化Min min算法的任务完成时间，再根据任务需求赋予任务优先级，通过优先级安排任务调度，提高算法负载平衡能力，最后在上述分析基础上提出POTE Min min(Priority and Overlap Transmission and Execution Min min)调度算法。     

处理顺序约束的信息物理融合系统静态任务表调度算法

针对异构环境并行计算的静态任务调度问题,以最小化有向无环图 (Directed acyclic graph, DAG)的执行跨度为目标,改变HEFT (Heterogeneous earliest finish time)算法中任务上行权重的计算方法, 获得更加合理的任务顺序排列,提出了一种最早完成时间优先的表调度算法IHEFT (Improvement heterogeneous earliest finish time).该算法在计算任务的上行权重时, 分别计算该任务分配给不同资源的上行权重,取其最小值,比使用所有资源对该任务的平均处理时间进行计算的HEFT算法更为准确. 确定任务的处理顺序后采用最早完成时间越小越优先的策略将任务分配给最优资源,并使得任务的开始执行时间和结束时间满足DAG中有向边的通讯时间约束.通过使用部分文献中的算例数据以及随机生成满足一定结构要求的DAG进行算法测试,将IHEFT与HEFT, CPOP (Critical-path-on-a-processor)和LDCP (Longest dynamic critical path)进行了比较,结果显示IHEFT算法更有效,而且时间复杂度较低.     

A group priority earliest deadline first scheduling algorithm

In most priority scheduling algorithms, the number of priority levels is assumed to be unlimited. However, if a task set requires more priority levels than the system can support, several jobs must in practice be assigned the same priority level. To solve this problem, a novel group priority earliest deadline first (GPEDF) scheduling algorithm is presented. In this algorithm, a schedulability test is given to form a job group, in which the jobs can arbitrarily change their order without reducing the schedulability. We consider jobs in the group having the same priority level and use shortest job first (SJF) to schedule the jobs in the group to improve the performance of the system. Compared with earliest deadline first (EDF), best effort (BE), and group-EDF (gEDF), simulation results show that the new algorithm exhibits the least switching, the shortest average response time, and the fewest required priority levels. It also has a higher success ratio than both EDF and gEDF.     

Online deadline scheduling on faster machines

Online deadline scheduling is to determine which jobs are accepted or rejected, where jobs have the deadline by which they must finish their processing and they arrive in the online fashion. The slack of a job is the gap between its arrival time and the last time when it can first be scheduled to meet its deadline. The job instance is given such that the slack of each job is at least κ times its processing time, where κ is called patience. In this paper, online algorithms have faster machines than the adversary. We investigate the speed of machines on which the online algorithms can achieve the optimality and parametrize them by the patience.     

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

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

一种面向作业的快速调度算法

面向作业的调度(job oriented scheduling,简称JOS)在实际作业车间(job shop)调度中得到普遍的应用,它的基本思想是将作业一个个地安排到工作机器上.该文提出了一种基于计算机JOS系统的快速调度算法,该算法指定作业操作的可行调度起始和结束时间以正排工序或逆排工序方式将它们安排到有限能力的工作机器上.通过记录和修改每一机器有效时间槽的办法来减少操作在每一机器上搜索可行时间槽的时间,从而大大提高了计算效率.实际系统应用表明,此算法对于大规模调度具有很强的优越性.     

On the equivalence of single machine earliness/tardiness problems with job rejection

We present optimal algorithms for single-machine scheduling problems with earliness criteria and job rejection and compare them with the algorithms for the corresponding problems with tardiness objectives. We present an optimal O(n log n) algorithm for minimizing the maximum earliness on a single machine with job rejection. Our algorithm also solves the bi-criteria scheduling problem is which the objective is to simultaneously minimize the maximum earliness of the scheduled jobs and the total rejection cost of the rejected jobs. We also show that the optimal pseudo-polynomial time algorithm for the total tardiness problem with job rejection can be used to solve the corresponding total earliness problem with job rejection.     

Preemptive online scheduling with rejection of unit jobs on two uniformly related machines

We consider preemptive online and semi-online scheduling of unit jobs on two uniformly related machines. Jobs are presented one by one to an algorithm, and each job has a rejection penalty associated with it. A new job can either be rejected, in which case the algorithm pays its rejection penalty, or it can be scheduled preemptively on the machines, in which case it may increase the maximum completion time of any machine in the schedule, also known as the makespan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule of all accepted jobs and the total penalty of all rejected jobs. We study two versions of the problem. The first one is the online problem where the jobs arrive unsorted, and the second variant is the semi-online case, where the jobs arrive sorted by a non-increasing order of penalties. We also show that the variant where the jobs arrive sorted by a non-decreasing order of penalties is equivalent to the unsorted one. We design optimal online algorithms for both cases. These algorithms have smaller competitive ratios than the optimal competitive ratio for the more general problem with arbitrary processing times (except for the case of identical machines), but larger competitive ratios than the optimal competitive ratio for preemptive scheduling of unit jobs without rejection.     

利用作业可塑性改进结合回填FCFS策略的性能

结合回填的FCFS策略是超级计算机上使用最为普遍的调度策略,针对该策略在响应时间和系统利用率等方面的不足,提出了改进其性能的DGA方法。该方法利用并行作业的可塑性,通过调度时对作业平均响应时间的预测来选择适合的作业请求规模,并利用遗传算法来解决最优作业资源请求的搜索问题。模拟器上实际作业流的模拟结果表明：该方法可以显著地改进结合回填的FCFS策略的调度效果,也优于已有的可塑性作业调度策略。