改进的Min-Min网格任务调度算法

在网格环境中,如何对任务进行高效调度是当前研究的热点问题。目前Min—Min调度算法是一个简单、快速、有效的算法。但它很难满足网格任务对服务质量的要求。在独立型的任务调度模型的基础上,提出了一种基于权值的改进Min—Min调度算法。改进后的算法通过量化网格任务的优先级和等待时间,解决了原有算法存在的高质量任务和大任务等待时间过长的问题。仿真实验结果表明,改进后的算法满足了网格任务对优先级和等待时间的服务质量要求．是一种网格环境下有效的任务调度算法。     

网格环境下基于惩罚策略的任务调度模型及动态算法

文中结合克隆选择算法,模拟退火算法和遗传算法的优点,提出了一种改进的混合克隆退火遗传算法,并将该算法应用于网格计算任务调度问题的求解之中.该算法先通过克隆,退火交叉和高斯变异等操作来产生一组新的抗体,然后再对所产生的抗体进行模拟退火,直到退火温度不能再降低为止,从而求得问题的最优解.理论分析和实验结果表明这种任务调度算法优于其他调度算法,并可以成功地应用于网格环境下的任务调度问题.     

网格工作流动态调度研究

现有的网格工作流调度算法大都利用遗传算法所具有的并行性和全局解空间搜索的特点来解决工作流调度问题.但是,现有的调度算法没有对动态调度问题进行处理.文中针对网格服务的动态性,提出了服务资源信息中心的概念并给出了网格工作流管理系统的体系结构.在现有的基于遗传算法的网格工作流调度算法的基础上提出了网格服务工作流动态调度算法,补充了不同工作流过程模型的适应度函数的计算.     

基于改进遗传算法的异构环境混合调度策略研究

异构环境下任务调度是NP问题,它关注大规模的资源和任务调度,要求采用的调度算法能够具有高效性.随着任务数和资源数的增加,遗传算法表现出慢速收敛的缺点.为了克服其缺点,在改进的遗传算法的基础上,增加了分组和负载平衡处理策略,提出了一种混合遗传调度策略.仿真实验表明,基于改进遗传算法的混合调度策略比传统的调度策略性能更优,其算法更符合复杂的异构环境,能更好满足系统的时间特性和最小化资源开销的问题.     

网格调度的算法研究及改进

优化网格资源调度算法可以提高网格系统执行效率,给任务安排合理的执行顺序和合适的处理器是优化网格资源调度算法需突破的关键技术.文中研究并实现了（Heterogeneous-Earliest-Finish） HEFT[1]算法和新的（Hierarchical Reliability-Driven Scheduling）HRDS算法.采用DAG[2]任务图生成函数,通过对已有HEFT算法进行研究,采用SimGrid为在分布计算环境下进行分布并行应用调度研究提供一个仿真环境,对HRDS算法进行了改进和验证.验证过程中在HRDS算法中加入了可靠性开销作为调度依据,并把算法分为两层调度,本地可靠性驱动调度和全局可靠性驱动调度.两算法的调度结果在SimGrid网格模拟器中仿真调度,仿真成功并且调度结果在可靠性和性能方面HRDS都比HEFT算法要好.     

军用网格环境下基于优先权的Min-Min任务调度算法

军用网格环境下的资源调度与一般网格环境下的资源调度相比较，一个明显的特点就是必须考虑一些特别任务的优先级。在给出网格独立任务调度模型基础上，提出了一种基于优先权的Min—Min资源调度算法，该算法首先调度优先级高的任务，其余任务则采用Min—Min算法调度。经过分析，该算法的时间复杂度是O（n^2m），与Min—Min相比，该算法的Makespan可能略大，但可以满足军用网格环境下特殊任务优先执行的需求。     

多目标约束的网格任务安全调度模型及算法研究

异构网格环境的特点决定了其任务调度是受调度长度、安全性能及调度费用等多个因素制约的。该文根据网格资源调度的特点构造了一个安全效益函数和节点信誉度动态评估模型,并以此为基础建立了一个多目标约束的网格任务调度模型。利用隶属度函数将多目标函数转化为单目标模型,通过设计新的进化算子,从而提出一种遗传算法MUGA(Mode Crossover and Even Mutation Genetic Algorithm)进行求解,并对算法的收敛性进行了理论分析。仿真实验表明,在同等条件下该算法与同类算法相比,在任务调度长度、安全效益值、可信度及调度费用指标优化方面具有较好的综合性能。     

基于蚂蚁算法的网格作业调度研究

网格环境下的作业调度是一个NP难问题,蚂蚁算法内在的并行性和可扩充性使其非常适合网格作业调度。将蚂蚁算法应用于网格环境作业调度,提出一种通过作业代理的移动进行网格作业调度的方案,该蚂蚁算法不仅在分配网格计算资源时进行信息素的局部更新,还在网格计算资源完成作业后进行信息素的整体更新。通过模拟实验测试和选取蚂蚁算法的各种影响参数,取得了比较理想的实验结果。实验证明该算法能够有效地实现作业的合理调度和网格系统的负载平衡。     

云计算环境中优化遗传算法的资源调度策略

资源调度是云计算的核心问题,传统的遗传算法虽然可以用于云计算环境中的资源调度,但是由于传统遗传算法存在收敛慢、易早熟等特点,所以这种算法并不适应于多聚类环境下的密集型任务调度。基于此,我们提出了云计算环境中优化遗传算法的资源调度策略以弥补传统遗传算法的不足。本文主要通过对云计算概念的介绍以及如何优化遗传算法的资源调度策略来展开讨论。     

基于改进遗传算法的网格任务调度

为了充分利用网格的大规模计算能力,提高其计算效率,提出了一种改进的遗传算法来解决网格任务调度问题。由于任务之间具有依赖关系,将任务按高度值进行划分,高度值小的任务优先进行处理,从而可以提高种群的初始质量,减少遗传算法的执行时间。实验结果表明,此算法提高了种群的初始质量,获得了较优的调度效果。     

Efficient algorithms for scheduling data broadcast

With the increasing acceptance of wireless technology, mechanisms to efficiently transmit information to wireless clients are of interest. The environment under consideration is asymmetric in that the information server has much more bandwidth available, as compared to the clients. It has been proposed that in such systems the server should broadcast the information periodically. A broadcast schedule determines what is broadcast by the server and when. This paper makes the simple, yet useful, observation that the problem of broadcast scheduling is related to the problem of fair queueing. Based on this observation, we present a log‐time algorithm for scheduling broadcast, derived from an existing fair queueing algorithm. This algorithm significantly improves the time‐complexity over previously proposed broadcast scheduling algorithms. Modification of this algorithm for transmissions that are subject to errors is considered. Also, for environments where different users may be listening to different number of broadcast channels, we present an algorithm to coordinate broadcasts over different channels. Simulation results are presented for proposed algorithms.     

基于并行遗传算法的对称多处理器任务调度策略研究

任务分配问题是公认的NP难问题。文章在以往有关多处理机任务分配算法的基础上，提出了一种适用于SMP系统结构的并行遗传调度算法。仿真结果表明。该算法具有较好的效果和收敛性。     

异构计算环境下任务调度模型的启发式算法研究

针对一种具有普遍意义的任务调度模型,从算法特点出发讨论和分析各种启发式调度算法,得出min-min启发式算法和遗传算法在异构计算环境下有较好的性能表现.     

并行多机调度问题的一种基于组合规则的遗传算法

本文对最小化完工时间并行多机调度问题提出了一种基于组合规则的遗传算法.用遗传算法来优化调度策略,使得在不同的调度阶段,可采用不同的调度规则以提高算法性能,并用计算实例表明了该遗传算法优于基于机器编码的模拟退火算法和遗传算法,并能适用于大规模并行多机调度问题,算法计算量小,鲁棒性强.     

The Maximum Throughput of A Wireless Multi-Hop Path

In this paper, the maximum end-to-end throughput that can be achieved on a wireless multi-hop path is investigated analytically. The problem is modeled using the conflict graph, where each link in the multi-hop path is represented uniquely by a vertex in the conflict graph and two vertices are adjacent if and only if the associated links mutually interfere. Using the conflict graph and the linear programming formulations of the problem, we analyzed the maximum end-to-end throughput of a wireless multi-hop path a) in a simple scenario where nodes are optimally placed and each node can only interfere with the transmission of its adjacent nodes along the path, and b) in a more complicated scenario where nodes are randomly placed and each node can interfere with the transmission of any number of nearby nodes along the path in both a) an error free radio environment and b) an erroneous radio environment. The maximum end-to-end throughputs for each of the above four scenarios are obtained analytically. We show that the maximum achievable end-to-end throughput is determined by the throughput of its bottleneck clique, where a clique is a maximal set of mutually adjacent vertices in the associated conflict graph. Further our analysis suggests the optimum scheduling algorithm that can be used to achieve the maximum end-to-end throughput and that it is convenient to use the (maximal) independent sets as the basic blocks for the design of scheduling algorithms. The findings in this paper lay guidelines for the design of optimum scheduling algorithms. They can be used to design computationally efficient algorithms to determine the maximum throughput of a wireless multi-hop path and to design a scheduling algorithm to achieve that throughput.     

基于5G边缘计算的智能电网高性价比任务调度

针对智能电网环境中电力数据量庞大且对处理时效性要求高的问题,将5G边缘计算引入智能电网系统.研究了基于5G边缘计算的智能电网任务调度问题,在满足电网任务完成需求的同时,最大限度地降低成本.基于此提出了一种基于贪心策略的启发式任务调度算法,通过与两种算法在包括输入任务数、传输数据大小和延迟要求等参数下的比较,验证了所提算...     

Burst scheduling algorithms for SS/TDMA systems

Efficient algorithms that generate a detailed operation plan for satellite-switched time-division multiple access (SS/TDMA) systems are proposed. A burst time plan generation problem is analyzed and two algorithms for burst scheduling are presented. The first method is an algorithm based upon a bin pack problem. The other algorithm schedules new bursts while reassigning already scheduled bursts by a single machine scheduling model. These algorithms are shown to be applicable to practical systems operating with transponder hopping and multidestination bursts. Simulation results for a number of example problems are presented     

Hidden Markov model multiarm bandits: a methodology for beamscheduling in multitarget tracking

We derive optimal and suboptimal beam scheduling algorithms for electronically scanned array tracking systems. We formulate the scheduling problem as a multiarm bandit problem involving hidden Markov models (HMMs). A finite-dimensional optimal solution to this multiarm bandit problem is presented. The key to solving any multiarm bandit problem is to compute the Gittins (1989) index. We present a finite-dimensional algorithm that computes the Gittins index. Suboptimal algorithms for computing the Gittins index are also presented. Numerical examples are presented to illustrate the algorithms     

Priority-based grant-aware scheduling for low-latency switching

This paper introduces new scheduling algorithms supporting low-latency switching. The proposed grant-aware (GA) algorithm improves the average delay performance by using the grant information of previous iteration. The simulation result shows that the average delay of GA algorithm is about one-tenth of the existing algorithm in high-load condition. We also introduce two priority-based scheduling algorithms grant-aware and priority-aware (GAPA) algorithm and cyclic scheduling with the longest-queue-first (C-LQF) algorithm. In the priority-based scheduling, the scheduling priority of VoQ is determined based on its queue size. GAPA and C-LQF consider the priority only after the first iteration to prevent the starvation problem. The simulation result shows that GAPA and C-LQF scheduling achieves better performance than GA in terms of average delay, maximum delay, and hotspot throughput.     

Minimizing the Number of Multicast Transmissions in Single-Hop WDM Networks

The problem of minimizing the number of transmissions for a multicast transmission under the condition that the packet delay is minimum in single-hop wavelength division multiplexing (WDM) networks is studied in this paper. This problem is proved to be NP-complete. A heuristic multicast scheduling algorithm is proposed for this problem. Extensive simulations are performed to compare the performance of the proposed heuristic algorithm with two other multicast scheduling algorithms, namely, the greedy and no-partition scheduling algorithms. The greedy algorithm schedules as many destination nodes as possible in the earliest data slot. The no-partition algorithm schedules the destination nodes of a multicast packet to receive the packet in the same data slot without partitioning the multicast transmission into multiple unicast or multicast transmissions. Our simulation results show that (i) an algorithm which partitions a multicast transmission into multiple unicast or multicast transmissions may not always produce lower mean packet delay than the no-partition algorithm when the number of data channels in the system is limited and (ii) the proposed heuristic algorithm always produces lower mean packet delay than the greedy and the no-partition algorithms because this algorithm not only partitions a multicast transmission into multiple unicast or multicast transmissions to keep the packet delay low but also reduces the number of transmissions to conserve resources.