基于遗传算法的网格任务调度研究

网格调度是一个典型的NP问题,研究表明遗传算法是解决复杂环境下资源调度的有效方法之一。针对异构环境下的网格任务调度,提出了一种改进的遗传算法,并改进了遗传算法的收敛特性,通过分析实验结果证明该算法优于传统的调度算法。     

树形网格自适应调度模型研究

提出一种基于树形计算网格的自适应调度模型,实现对小粒度独立任务和用户大作业的自适应最优调度.通过对网格环境的实时检测,给出了基于节点负载状况、节点任务执行时间和任务特性的自适应调度算法.实验证明该任务调度模型在负载平衡和容错方面具有良好的性能.     

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

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

基于粒子群的网格任务调度算法研究

为了更好地解决异构动态环境下的资源管理问题,提出了一种网格环境下的任务调度模型。该模型考虑了当前网格虚拟组织下的计算资源、存储资源和带宽资源,模型的最优化目标是实现三者利用率最高和代价最低,即构造min-max函数。与遗传算法相比,利用粒子群优化算法对min-max函数求解提高了资源的利用率和任务的执行效率,同时在随着迭代次数增加的情况下,搜索速度、寻优率和避免早熟方面也有明显的提高。     

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

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

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

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

QIACO:一种多QoS约束网格任务调度算法

网格环境下的任务调度问题属于NP难解,难以得到精确的最优解,适合使用蚁群算法等智能优化算法对最优解进行逼近;同时,服务质量(QoS)也是衡量网格性能的一个重要指标,网格任务调度应该满足用户的QoS需求.为解决具有QoS保证的网格任务调度问题.本文以带有Qos约束的任务为研究对象,结合改进的蚁群算法,提出了一种基于蚁群算...     

一种基于改进蚂蚁算法的网格任务调度策略

网格是分布式高性能计算的一个主要发展方向。任务调度问题的解决是网格得以充分发展的基本前提。提出了一种基于改进蚂蚁算法的网格任务调度策略。不同于传统蚂蚁算法,改进的蚂蚁算法通过在处理任务前后分别调整信息素来准确地反映资源的性能。任务调度将选择由改进蚂蚁算法产生的性能最佳的资源来处理任务。改进蚂蚁算法以及任务调度策略的有效性已被OPNET上的仿真结果所验证。     

计算网格环境下以QoS为指导的启发式任务调度

实现用户的服务质量QoS是网格的一个重要特征．网格环境下以服务质量为指导的任务调度是一个非常复杂且具有挑战性的问题，特别是在用户的任务具有多种QoS需求的情况下。利用效用函数对用户的多种QoS进行建模．提出了一个同时兼顾任务完成时间和用户服务质量的目标函数。在此基础上提出了一种计算网格环境下针对一组具有QoS需求的相互独立的计算任务的启发式调度算法。模拟实验结果显示，该算法能较好的满足不同用户的需求并提升系统资源的利用率。     

异构多处理器系统的混合任务调度算法

针对实时异构系统的任务调度问题,提出了一种异构多处理器系统的混合实时任务调度算法.该算法采用带有非周期服务器的EDF( Earliest Deadline First)算法来调度单处理器上的任务集,可充分利用处理器的计算带宽.采用启发式搜索算法来进行任务的分配,以最大剩余计算带宽为搜索指标,可确保各处理器的负载尽量平衡...     

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

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

信任驱动的网格作业调度算法

针对目前网格资源管理中信任机制与作业调度机制分离的缺陷,基于网格信任模型与信任效益函数,提出了信任驱动的网格作业调度问题。对传统批作业调度算法进行信任扩展,提出了两种信任驱动的网格作业调度启发式。对信任驱动网格作业调度算法进行大规模仿真实验,有力地证明了信任驱动算法优于传统时间驱动算法,在平均信任效益和总信任效益等方面具有较好的综合性能。     

Evaluation of algorithms for efficient partitioning and scheduling of data bursts in satellite communications

We evaluate four scheduling algorithms for satellite communications that use the Time Division Multiple Access methodology. All the algorithms considered are based on the open‐shop model. The open‐shop model is suitably represented or modified to exploit some existing algorithms to solve the satellite communication problem. In the first two algorithms, namely pre‐emptive scheduling with no intersatellite links and greedy heuristics with two intersatellite links, a (traffic) matrix representation of the open‐shop model is used to get a near optimal schedule. In the next two algorithms, generalized heuristic algorithm and the branch and bound algorithm, the open‐shop model is modified to accommodate the inter‐satellite link and this modified open‐shop model is used to solve for a near optimal schedule. The basic methodology of all the algorithms are briefly described and their performance was evaluated through extensive simulations. The performance criteria to evaluate the algorithms are—run time of the algorithms, schedule lengths, and optimality of the algorithm against theoretical bounds. Three of the above‐mentioned algorithms are evaluated by comparing the performance criteria under similar conditions. Optimal branch and bound algorithm is not evaluated due to its high complexity. The general heuristic algorithm is found to give a good trade off between computation time and optimality. The computation time is comparable with the pre‐emptive scheduling algorithm and greedy heuristic algorithm and the schedule length achieved is near to the lower bound value. Copyright © 2005 John Wiley & Sons, Ltd.     

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.     

Greedy Tree Growing Heuristics on Block-Test Scheduling Under Power Constraints

Greedy scheduling algorithms are proposed here to improve the test concurrency under power limits. An extended tree growing technique is used to model the power-constrained test scheduling problem in these algorithms. A constant additive model is employed for power dissipation analysis and estimation. The efficiency of this approach is assessed with test scheduling examples and the experimental results are presented. Known list scheduling approaches are proven to give acceptable power-constrained test scheduling results quickly, but not guaranteed to be optimal.     

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     

Energy-aware scheduling with probabilistic deadline constraints in wireless networks

In a shared-medium wireless network, an effective technique that allows for a tradeoff of message transmission time for energy savings is to transmit messages over multiple smaller hops as opposed to using the long direct source-destination hop. In this context, we address the problem of scheduling messages with probabilistic deadline constraints. Unlike most other works in this area, we consider the practical aspects of the erroneous channel condition and the receiver energy consumption while solving the scheduling problem. Our solution is three fold – first we prove that the problem is NP-hard. We then present an Integer Linear Program (ILP) formulation for the scheduling problem. Finally, we present efficient heuristic scheduling algorithms which minimize the energy consumption while providing the required guarantees. Our simulation studies show that the proposed heuristic algorithms achieve energy savings comparable to that obtained using the linear programming methodology under practical channel conditions.     

基于改进免疫遗传算法的带硬时间窗车辆调度问题的实现

免疫算法是模仿生物体高度进化,复杂的免疫系统仿生的一种智能化启发式算法。带硬时间窗的车辆路径问题(VSPHTW)是在基本的车辆路径问题(VSP)上增加了时间窗约束条件的一种变化形式,是一个典型的NP难题。通过采用一种改进的信息熵计算方法、交叉和变异概率的自适应机制,构造一个改进的免疫算法来求解VSPHTW,并将求解结果与其他遗传算法比较。比较结果显示,该算法对于求解VSPHTW问题具有较好的性能。     

Meta‐heuristic algorithms for channel scheduling problem in wireless sensor networks

The channel scheduling problem is to decide how to commit channels for transmitting data between nodes in wireless networks. This problem is one of the most important problems in wireless sensor networks. In this problem, we aim to obtain a near‐optimal solution with the minimal energy consumption within a reasonable time. As the number of nodes increases in the network, however, the amount of calculation for finding the solution would be too high. It can be difficult to obtain an optimal solution in a reasonable execution time because this problem is NP‐hard. Therefore, most of the recent studies for such problems seem to focus on heuristic algorithms. In this paper, we propose efficient channel scheduling algorithms to obtain a near‐optimal solution on the basis of three meta‐heuristic algorithms; the genetic algorithm, the Tabu search, and the simulated annealing. In order to make a search more efficient, we propose some neighborhood generating methods for the proposed algorithms. We evaluate the performance of the proposed algorithms through some experiments in terms of energy consumption and algorithm execution time. The experimental results show that the proposed algorithms are efficient for solving the channel scheduling problem in wireless sensor networks. Copyright © 2011 John Wiley & Sons, Ltd.