一种基于虚拟截止时间制导的改进的Min-Min元任务调度算法  

A Virtual Deadline Guided Min-Min Meta-task Scheduling Heuristic

作　　者：杨疆湖[1] 高传善[1] 黄昌来[1] 李明[1] 

机构地区：[1]复旦大学计算机科学与工程系,上海200433

出　　处：《计算机科学》2006年第8期72-75,共4页Computer Science

摘　　要：在网格环境下,资源状况和用户行为相当复杂,是一个异构计算环境,元任务(meta-task)调度比传统并行调度更为复杂。如何映射一组任务到一组机器上被证明是NP问题,其目的一般是最小化任务完成时间(makespan)。为解决这一问题,已经提出一些启发式任务调度算法,例如具有代表性的Min-Min元任务调度算法。本文在Min-Min元任务调度算法的基础上,通过虚拟截止时间制导的方法来改进Min-Min算法。实验结果表明,本文提出的算法具有更短的任务完成时间。In Grid environment which is a Heterogeneous Computing（HC） environment, resource status and user behavior are very complicated, so scheduling heuristics for meta-task are more complicated than traditional parallel scheduling heuristics. How to map a set of tasks on a set of machines is known to be NP-hard. The goal of those scheduling heuristics is minimize the makespan of the meta-tasks. Some heuristics are introduced to solve such scheduling problem, including Min Min and other heuristics. In this paper, based on traditional Min-Min scheduling heuristic, a virtual deadline guided meta-task scheduling heuristic is proposed. The simulation results show that the proposed heuristic has less makespan than traditional Min Min scheduling heuristic.

关 键 词：元任务(meta-task) 虚拟截止时间 调度 算法 MIN-MIN 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]