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

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

气象环境下的云计算调度算法

针对气象计算的特点,提出气象计算的云模型,在这个模型之上,提出气象云计算（Weather Cloud）的启发式调度算法。调度算法对气象作业按照时间紧迫型、CPU紧迫型、内存紧迫型和硬盘空间紧迫型进行分类,计算资源综合紧迫指数,相应地赋予不同调度优先权限。与CMMS（Cloud Min min Scheduling）、AFCFS（Adaptive First Come First Service）、Fair的调度算法对比表明,Weather Cloud的调度算法不但减少了计算的等待时间,而且增加了完成的指令数量。     

基于信任模型的数据密集型网格任务调度算法研究

针对数据密集型应用的调度问题，提出一种新的调度算法，在选择文件传输节点的同时考虑网络带宽和节点的信任度．针对传输文件时带来的传输节点负载不均的现象，采用基于sufferage思想的算法均衡负载．最后，通过实验证明该算法优于传统的Min Min算法．     

数据和计算密集混合元任务的网格调度算法

网格计算技术是继Internet计算之后出现的新兴研究领域。网格系统由异构的资源组成，一个好的任务调度方法可以充分利用网格系统的处理能力，减少任务的完成时间。根据目前网格系统的使用模式，提出了符合实际的用户任务形式，即任务由数据传输和计算两部分组成，计算在获得所有输入之后开始执行。多个这样的独立任务组成元任务，作为调度程序的最小执行单位。在实际应用中，元任务应该由数据密集型和计算密集型任务混合组成。考虑到数据传输和计算的比例关系对元任务完成的影响，提出一种新的调度算法TCR，通过提高计算资源的利用率以及任务间的并行度，减少元任务的完成时间。详细介绍了该算法，并通过模拟结果的对比验证了该算法的良好性能。     

网格计算中的调度算法研究

主要研究了在网格环境中,基于大规模分布式资源集合上并行应用程序的调度算法,提出了一个新的调度算法——Segment Qos Min—Min P．R。该算法结合了Min-Min调度算法、RR调度算法、Qos Guided Min—Min Heuristic调度算法、Segmented Min—Min调度算法的优点于一身,并用GridSim模拟器对该算法的性能进行了仿真。     

信任驱动机制下的网格负载调度算法

利用网格信任模型与效益函数,结合资源当前负载状况,提出一种基于负载均衡的任务调度算法——Trust-Driven_Load（TD_Load）,在满足最大信任效益值的条件下,采用预计最短完成时间对多个资源进行选择。实验结果表明,在相同的条件设置下,TD_Load算法在资源负载、makespan和任务平均等待时间上优于基于信任效益值的传统算法,而且算法时间花费小,当任务数量增多时,综合调度性能更优。     

多机器总完成时间和makespan近似最优的开放式车间调度方法

研究了多机器开放式车间调度问题,采用离散事件系统调度使makespan最小化和总完成时间最小.给出了在确定处理机器的条件下,不同批次的作业总完成时间最优的排序定理,以及选择机器处理作业的指标优化定理,利用给出的若干定理建立了总完成时间最优的调度方法.作者利用加权总完成时间最优算法来近似求解makespan最小化和总完成时间最优的调度问题.作者也利用论文的理论结果给出了一个三机器开放式车间情况的实际算例.     

基于GridSim模拟器的网格资源调度算法的研究

网格资源调度策略是网格计算领域中的关键研究方向之一,网格模拟器是资源调度策略优化和改进研究的重要平台,本文研究了GridSim模拟器．对此模拟器的整个框架结构和运行机制作了阐述,本文对基础的Minmin算法和QoS Guided Min—min算法进行研究和改进,并通过基于GridSim包设计了应用程序对改进后的算法进行了相应的模拟。模拟研究结果表明,改进后的算法在任务平均完成时间上优于以前的算法。     

可靠的网格作业调度机制

针对网格环境的动态性特征,提出了一种可靠的网格作业调度机制(DGJS)。按照作业完成时间期限,DGJS将作业分为：高QoS级、低QoS级和无QoS级,不同QoS级作业有不同的调度优先权;基于资源可用性预测,DGJS采用基于可靠性代价的作业调度策略,将作业尽可能调度到可靠性高的资源节点;另外,DGJS对不同QoS级作业采用不同的容错策略,在保证故障容错的同时,节省网格资源。实验表明：在动态的网格环境下,较之传统的网格作业调度算法,DGJS提高了作业成功率,减少了作业完成时间。     

基于通信代价的网格资源调度算法

针对基于时间和预算限制的资源调度算法在调度数据密集型应用程序时存在的问题,提出一种新的基于通信代价的网格资源调度算法,综合考虑用户的时问限制和预算要求,根据用户作业的计算量与通信量选择具有一定计算能力,且通信代价较小的资源节点作为目标节点,通过减少此类程序提交到目标资源节点的通信代价,达到减少整个应用程序完成时间的目的。实验结果表明,该算法能够获得较好的性能。     

The anatomy study of high performance task scheduling algorithm for Grid computing system

Large-scale computation is frequently limited to the performance of computer hardware or associated cost. However, as the development of information and network technologies thrives, idle computers all over the world can be utilized and organized to enhance overall computation performance; that is, Grid environments that facilitate distributed computation. Hence, the dispatching and scheduling of tasks should be considered as an important issue. Previous studies have demonstrated Grid environments that are composed of idled computers around the globe and are categorized as a type of Heterogeneous Computing (HC). However, scheduling heuristics currently applied to HC focus on the search of minimum makespan, instead of the reduction of cost. In addition, relevant studies usually presume that HC is based on high-speed bandwidth and the communication time is ignored. Further, in response to the call for user-pay policy, as a user dispatches a job to a Grid environment for computation, each execution task would be charged. It is difficult to estimate a job will be dispatched to which and how many computers; it is impossible to predetermine scheduling heuristic which is proposed in previous studies will result in the optimal makespan, and mention actual cost and risk. Therefore, this study proposes ATCS-MCT (Apparent Tardiness Cost Setups-Minimum Completion Time) scheduling algorithm that composes of execution time, weight, due date, and communication time factors to testify that the ATCS-MCT scheduling algorithm not only achieves better makespan than Min–min scheduling heuristics do but also reduces costs.     

网格作业完工时间与作业分割粒度的关系

对可分割的计算密集型大型作业在并行且不间断运行情况下的完工时间与作业分割粒度之间的关系进行研究。首先分析了子作业之间无通信和有通信两种情况下可分割计算密集型大型作业的完工时间和分割粒度的关系,然后对可分割计算密集型大型作业在专用网格资源上的完工时间与分割粒度的关系进行仿真。仿真结果显示,大型作业的完工时间随着分割粒度的增大先减小后增大;当单个子作业的计算时间和通信时间之比增大时,作业的分割粒度可以更细,作业完工时间的最小值减小。因此完工时间最优的作业分割粒度不能过粗或过细。     

带尺寸约束的二机流水车间生产运输协调博弈调度问题

研究二机流水车间生产运输协调调度问题,当工件在第1台机器加工完成后,由1台带有容量限制的运输车分批次运输到第2台机器加工,运输过程考虑工件尺寸约束,目标函数为最小化最大完工时间.考虑到源于不同客户的工件对机器及运输设备的竞争,以工件为博弈方,工件在生产运输过程中等待时间为策略,各工件完工时间为收益,建立非合作博弈模型.通过将问题转化为马尔可夫决策过程,设计线性逼近值函数的Q-learning算法求解纳什均衡调度.实验结果表明Q-learning算法求得的纳什均衡调度具有较好的全局最优性,从而能够在满足客户的利益下,提高企业的生产效率,实现客户与企业的双赢.     

Enhancing list scheduling heuristics for dependent job scheduling in grid computing environments

Job scheduling plays a critical role in resource utilisation in a grid computing environment. The heterogeneity of grid resources adds some challenges to the work of job scheduling especially when jobs have dependencies which can be represented as Direct Acyclic Graphs (DAGs). Heuristics have been developed for job scheduling optimisation. This paper presents six heuristic enhancements—MMSTFT for minimising both makespan and task finish time, levelU for upward DAG levelling, TMWD for matching tasks with data, Slack for prioritising task scheduling based on slack time, LSlack for levelling the Slack heuristic, and NLPETS for non-levelling of performance effective task scheduling (PETS). The performance of LSlack is amongst the best heuristics evaluated (with BL and LMT). Additionally, heuristic enhancements MMSTS and TMWD can significantly improve the makespan of generated schedules. To facilitate performance evaluation, a DAG simulator is implemented which provides a set of tools for DAG job configuration, execution and monitoring. The components of the DAG simulator are also presented in this paper.     

An integrated security-aware job scheduling strategy for large-scale computational grids

All existing fault-tolerance job scheduling algorithms for computational grids were proposed under the assumption that all sites apply the same fault-tolerance strategy. They all ignored that each grid site may have its own fault-tolerance strategy because each site is itself an autonomous domain. In fact, it is very common that there are multiple fault-tolerance strategies adopted at the same time in a large-scale computational grid. Various fault-tolerance strategies may have different hardware and software requirements. For instance, if a grid site employs the job checkpointing mechanism, each computation node must have the following ability. Periodically, the computational node transmits the transient state of the job execution to the server. If a job fails, it will migrate to another computational node and resume from the last stored checkpoint. Therefore, in this paper we propose a genetic algorithm for job scheduling to address the heterogeneity of fault-tolerance mechanisms problem in a computational grid. We assume that the system supports four kinds fault-tolerance mechanisms, including the job retry, the job migration without checkpointing, the job migration with checkpointing, and the job replication mechanisms. Because each fault-tolerance mechanism has different requirements for gene encoding, we also propose a new chromosome encoding approach to integrate the four kinds of mechanisms in a chromosome. The risk nature of the grid environment is also taken into account in the algorithm. The risk relationship between jobs and nodes are defined by the security demand and the trust level. Simulation results show that our algorithm has shorter makespan and more excellent efficiencies on improving the job failure rate than the Min–Min and sufferage algorithms.     

Scheduling in a manufacturing shop with sequence-dependent setups

In this paper, the problem of scheduling multiple jobs in a flexible manufacturing cell with multiple machine stations is addressed. Due to the large capital investments that usually characterize flexible manufacturing systems (FMS), an area of control of great interest to system users is that of maximizing the system performance through the minimization of machine idle and setup times. The magnitude of total time spent on machine setups and idle times is influenced by the availability of jobs, job mix, similarities of jobs and job scheduling procedure used. Similar jobs on the same machine require less setup times. Similarly, the use of an adequate scheduling method also reduces total idle and setup times. Such reduction improves the flow times of jobs. In this paper, a heuristic algoritm for scheduling jobs with sequence dependent setup times in a FMS is presented. The measure of performance for evaluating schedule adequacy is the production makespan.     

Designing a MapReduce performance model in distributed heterogeneous platforms based on benchmarking approach

MapReduce framework is an effective method for big data parallel processing. Enhancing the performance of MapReduce clusters, along with reducing their job execution time, is a fundamental challenge to this approach. In fact, one is faced with two challenges here: how to maximize the execution overlap between jobs and how to create an optimum job scheduling. Accordingly, one of the most critical challenges to achieving these goals is developing a precise model to estimate the job execution time due to the large number and high volume of the submitted jobs, limited consumable resources, and the need for proper Hadoop configuration. This paper presents a model based on MapReduce phases for predicting the execution time of jobs in a heterogeneous cluster. Moreover, a novel heuristic method is designed, which significantly reduces the makespan of the jobs. In this method, first by providing the job profiling tool, we obtain the execution details of the MapReduce phases through log analysis. Then, using machine learning methods and statistical analysis, we propose a relevant model to predict runtime. Finally, another tool called job submission and monitoring tool is used for calculating makespan. Different experiments were conducted on the benchmarks under identical conditions for all jobs. The results show that the average makespan speedup for the proposed method was higher than an unoptimized case.

     

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

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

A new window-based job scheduling scheme for 2D mesh multicomputers

Allocating submeshes to jobs in mesh-connected multicomputers in a FCFS fashion can lead to poor system performance (e.g., long job waiting delays) because the job at the head of the waiting queue can prevent the allocation of free submeshes to other waiting jobs with smaller submesh requirements. However, serving jobs aggressively out-of-order can lead to excessive waiting delays for jobs with large allocation requests. In this paper, we propose a scheduling scheme that uses a window of consecutive jobs from which it selects jobs for allocation and execution. This window starts with the current oldest waiting job and corresponds to the lookahead of the scheduler. The performance of the proposed window-based scheme has been compared to that of FCFS and other previous job scheduling schemes. Extensive simulation results based on synthetic workloads and real workload traces indicate that the new scheduling strategy exhibits good performance when the scheduling window size is large. In particular, it is substantially superior to FCFS in terms of system utilization, average job turnaround times, and maximum waiting delays under medium to heavy system loads. Also, it is superior to aggressive out-of-order scheduling in terms of maximum job waiting delays. Window-based job scheduling can improve both overall system performance and fairness (i.e., maximum job waiting delays) by adopting large lookahead job scheduling windows.