一种网格环境下的资源协同调度算法

基于传统的DAGs调度算法,提出了一种适于网格环境下使用的协同调度算法,目标是使得一组应用程序的整体执行时间最小,并且算法中提供了对资源的提前预约的支持。模拟结果表明,该算法与传统的调度算法相比,性能有了较大的提高 。     

改进遗传算法在网格任务调度中的应用

为了提高遗传算法的搜索性能,同时满足网格资源的优化分配,提出了一种带过滤机制的遗传算法,使其适用于网格任务调度问题的优化处理.仿真研究表明该算法更符合网格调度的复杂环境,能得到较短的任务执行时间和较好的负载均衡性.     

离散微粒群优化算法在网格任务调度中的应用

网格任务调度算法是影响网格成功与否的关键技术之一.在研究现有任务调度策略的基础上,指出Min-Min算法的负载不均衡性.借鉴遗传算法中的交叉操作过程,提出了一种新的任务调度算法.该算法对传统的连续型微粒群优化算法进行改进,使其适用于网格任务调度问题的优化处理,实现网格资源的优化分配.仿真研究表明该算法更符合网格调度的复杂环境,能得到较短的任务执行时间和较好的负载均衡性.对比分析表明,离散微粒群优化算法所得结果优于常用的Min-Min调度方案,是一种高效的调度方法.     

基于任务-资源分配图优化选取的网格依赖任务调度

任务调度是网格应用系统获得高性能的关键.网格计算中一个大型的应用程序往往被分解为具有依赖关系的多个任务.在资源个体差异较大、广域互连的网格环境下任务间的依赖关系对传统的调度策略提出了新的挑战.任务调度的主要工作是为任务分配资源以及确定任务的执行次序,将依赖任务的可能的资源分配方案表示为任务-资源分配图（T-RAG）,在该图的基础上提出了基于T-RAG优化选取的依赖任务调度模型,将依赖任务调度问题转化为图的优化选取问题,解析最优任务-资源分配图可以同时确定资源分配方案和任务的执行次序即为最优调度方案.最后,实现了基于该模型的任务调度算法,该算法与ILHA算法的对比分析表明,在资源差异较大及任务间存在大量数据传输的情况下所提出的算法更优.     

一种基于DAG图划分的网格关联任务调度算法

网格计算中的大型应用程序往往被分解为多个关联任务.对于这类应用,任务间的依赖是一个不可忽略的因素.传统算法只能将其视为元任务来考虑,限制了对任务粒度的进一步划分,从而大大降低了任务调度的性能.本文提出一种基于DAG图划分的关联任务调度算法.它优先调度关键路径上的任务,同时利用任务复制的方法充分利用资源上的时间碎片,保证依赖关系及时得到满足.仿真结果表明,对于网格环境下的大规模关联任务,该算法有效地提高了作业执行速度和资源使用效率.     

一种快速的网格任务调度算法的设计

网格任务的执行环境具有动态性、分布性等特征,为了能顺利完成任务并使其具有较好的执行效率,需要一种有效的策略来进行任务的调度.结合信息处理的特点,提出一种快速有效的网格任务调度算法.该算法采用历史信息预测任务的执行时间,根据任务的截止时间要求对子任务进行合理分组.最后,给出了该算法在网格模拟器上的测试结果,并与一些算法进行了比较.结果表明,本算法对大作业以及截止期限紧急的作业具有较好的调度效果.     

基于微粒群算法的网格工作流优化调度问题的研究

网格工作流中的调度问题是一个复杂且具有挑战性的问题,它影响着网格工作流执行成功与否及效率的高低.针对具有时序和因果约束关系的网格工作流优化调度问题进行了研究,建立了网格工作流的任务调度模型和调度问题的目标模型,并应用微粒群算法来优化网格工作流中任务的调度.实验结果证明该算法优于传统的调度算法.     

网格应用程序的分解和提交

随着网格技术的不断发展,应用到网格上的应用程序越来越多。网格环境是一个分布式异构的计算环境,为了更有效地利用网格资源和提高程序运行效率,可以结合网格特点采用应用程序分解技术来达到目的。本文通过对应用程序类型以及一个分解实例的分析,得出这样的结论:对于适合分解的应用程序,采用分解技术可以提高应用程序的执行效率。     

网格应用程序执行时间预测系统

为了合理利用网格资源和改进应用程序的执行性能,需要对应用程序的执行时间进行实时预测,为任务调度系统和网格用户提供调度依据.本文工作建立了执行时间预测系统,周期性的产生预测信息并转换为统一格式注册到网格信息服务中.本文使用资源映射方法预测应用程序执行时间,并且设计一组实验测试系统性能.实验结果表明,本系统能够低开销,灵敏地预测执行时间,并且预测误差较小.     

基于网格计算的混合负载均衡策略

根据分布式系统的静态和动态负载均衡策略的优缺点,提出了在网格计算环境下的混合负载均衡策略.为了让网络中节点在网格计算环境中有效地执行需要大量计算的复杂任务,提出了用来评估节点效率的函数,并结合模拟实验证实了在此函数下算法的优越性.     

Parallel-identical-machine job-shop scheduling with different stage-dependent buffering requirements

The neglect of buffering requirements in a classical job shop scheduling system often results in inapplicability in many complex real-world applications. To overcome this inapplicability, a new and more generalised scheduling problem is proposed under different stage-dependent buffering requirements and parallel use of identical-function machine units at each processing stage in job shop environments. The problem is formulated as a mixed integer programming model that can be exactly solved by ILOG-CPEX for small-size instances. Moreover, a hybrid metaheuristic algorithm embedded with a state-of-the-art constructive algorithm is developed. The computational experiment shows that the proposed metaheuristic can efficiently solve large-size instances. The result analysis indicates that the proposed approach can provide better configuration of real-world scheduling systems. The proposed DBPMJSS methodology has a potential to analyse, model and solve many industrial systems with the requirements of buffering conditions, particularly for manufacturing, railway, healthcare and mining industries.     

附加信息对负载可任意划分应用调度的影响

研究需要附加信息的可任意划分应用的调度问题.文章首先引入附加信息的概念,扩展了DLS模型,在此基础上重新分析了在这类应用中经典的平均划分(EQS)算法的缺陷,并提出了一个无空闲时间调度算法(NIS).基于这两个算法的解析表达解,严格地证明了NIS算法的调度性能总是优于EQS算法.由于在这类应用中典型的情况是每个处理器需要相同的附加信息,文章进一步研究了这类典型应用.分析表明,与EQS算法相比有更大范围的应用能利用NIS算法获得并行计算的收益,NIS算法所能利用的资源也更多.     

基于GSPN和人工免疫算法的并行测试任务调度研究

针对ATS中并行测试任务调度复杂、难以优化的问题,提出了一种广义随机Petri网和人工免疫算法相结合的任务调度优化算法.首先对并行测试系统建立广义随机Petri网(GSPN)模型,然后将激发的变迁序列集作为并行测试任务调度路径;将免疫克隆选择算法(ICSA)应用到并行测试系统任务调度问题中,并提出一种自适应克隆选择算子,搜索最优任务调度路径,得到以测试时间最短为目标的最优任务调度方案.用某型雷达接收机并行测试系统对该算法进行仿真验证,结果表明,与改进的混合遗传算法(IHGA)相比,该算法能够便捷地得到任务调度最优序列,且测试效率更高.     

并行任务图的优化调度算法

科学与工程计算中的很多复杂应用问题需要使用科学工作流技术,超算领域中的科学工作流常以并行任务图建模,并行任务图的有效调度对应用的高效执行有重要意义。给出了资源限制条件下并行任务图的调度模型;针对Fork-Join类并行任务图给出了若干最优化调度结论;针对一般并行任务图提出了一种新的调度算法,该算法考虑了数据通信开销对资源分配和调度性能的影响,并对已有的CPA算法在特定情况下进行了改进。通过实验与常用的CPR和CPA算法做比较,验证了提出的新算法能够获得很好的调度效果。本文提出的调度算法和得到的最优调度结论对工作流应用系统的高性能调度功能开发具有借鉴意义。     

MOPT: list-based heuristic for scheduling workflows in cloud environment

Cloud computing is a popular and widely adopted computing platform for the execution of scientific workflows as it provides flexible infrastructure and offers access to collection of autonomous heterogeneous resources. Effective scheduling of computationally complex workflows which contain many interconnected tasks is a complex problem and becomes more challenging in cloud environment. Optimal solutions can be obtained by considering not only the heterogeneity of computation costs involved, but also by taking into account the communication costs among the tasks in a way that schedule length of the application is reduced. In this paper, we propose a list scheduling heuristic, namely minimal optimistic processing time (MOPT), with optimized duplication approach. The additional feature is introduced for the entry task and is applied only in scenarios in which duplication is more practical and effective. The prioritization phase of the proposed work is based on an optimistic processing time matrix that is used for ranking of the tasks. The algorithm has same time complexity as state-of-the-art existing algorithms, but notable improvements are acquired in terms of makespan and other performance evaluation parameters. Extensive experimental analysis of the proposed algorithm is carried out using synthesized graphs and graphs from the real-world applications. The results prove that MOPT achieves quality schedules with reduced makespans. As communication cost among the tasks grows higher, performance of the proposed algorithm becomes more effective, thus providing the evidence that the MOPT algorithm is well-suited for communication-intensive applications.

     

复杂产品开发项目调度问题的模糊优化算法

对具有不确定时间参数的复杂产品开发项目调度问题,提出一种有效的模糊优化调度算法-基于预测的模糊BoP项目调度算法.首先,用模糊数表示不确定的时间参数,并构造相应的模糊数运算方法,对适合于确定性调度问题的BoP算法进行扩展,使其能处理模糊性时间参数.其次,修正了BoP算法中子项目调度方法,提高了算法的调度性能,降低了计算复杂度.大量的数值仿真实验表明,与基于启发式规则的调度算法相比,模糊BoP算法更适合于具有不确定时间参数的复杂产品开发项目调度问题.     

一种基于神经网络的生产调度方法

提出解决具有开、完工期限制的约束Job-shop生产调度问题的一种神经网络方法. 该方法通过约束神经网络,描述各种加工约束条件,并对不满足约束的开工时间进行相应调 节,得到可行调度方案;然后由梯度搜索算法优化可行调度方案,直至得到最终优化可行调度 解.理论分析、仿真实验表明了方法的有效性.     

萤火虫群优化算法在越库调度问题中的应用

萤火虫群优化算法是一种新兴的群体智能优化算法,目前在组合优化领域中的应用比较少。提出萤火虫群优化算法（Glowworm Swarm Optimization,GSO）求解越库调度问题的优化方法。越库调度问题是一类极为复杂的NP难题,是影响越库配送效率的关键问题。依据算法和问题特点,设计基于随机键的两段式最大顺序值编码方法。为了解决GSO算法优化精度低、收敛速度慢等问题,提出逐维移动,贪婪接受的搜索策略。基于社会心理学原理,对位置更新公式进行改进。通过实验仿真,结果表明改进的GSO算法是求解越库调度问题的有效方法。     

一类复杂生产调度问题的基于符号演绎的调度方法

针对带有时问不确定件的复杂生产过程调度问题,提出一种基于符号演绎的调度方法.首先将时间的不确定性信息看作符号型数据,并提出一种用于处理这些符号型数据的基于不确定区间的符号演绎方法;然后将此符号演绎方法与遗传算法相结合,提出一种预排调度计划与实时调度规则相结合的调度方法来求解上述复杂生产调度问题.实验表明,将基于符号演绎的调度方法用于求解带有时间不确定性的复杂生产过程调度问题,能够取得较好的调度效果.     

柔性Flow-Shop调度的遗传算法优化

柔性Flow-shop调度问题（Flexible Flow-shop Scheduling Problem,FFSP）是一般Flow-shop调度问题的推广,由于在某些工序上存在并行机器,所以比一般的Flow-shop调度问题更复杂。为了有效地解决柔性Flow-shop调度问题,用遗传算法求解,给出了一种改进的编码方法,能够保证个体的合法性;并根据编码方法提出了矩阵解码方法。最后以某汽车发动机厂金加工车间的生产调度实例进行仿真,通过比较表明了算法的有效性。