单处理器最少延误问题的双逆向调度算法  

Bi-backward Scheduling Algorithm for the Problem of Minimizing the Tardiness on a Single Processor

作　　者：李云峰[1] 武小悦[1] 

机构地区：[1]国防科技大学信息系统与管理学院,湖南长沙410073

出　　处：《小型微型计算机系统》2007年第4期670-673,共4页Journal of Chinese Computer Systems

摘　　要：单处理器最少延误问题实际上是对任务集中每一个任务如何分配执行时间使得延误任务数量最少的问题,该问题是处理器调度问题中一类重要的基础问题.本文主要对该问题的调度算法进行研究,提出了一种基于排序的双逆向分配任务执行时间的调度算法,称为双逆向调度算法,该算法时间复杂度为O(n2),通过验证该算法是可行的.另外,还对任务关系进行了分析,并提出了任务固有冲突、任务临界冲突时刻、任务时间窗口中心点、任务间接冲突、任务冲突度等概念.In practice,the problem of minimizing the tardiness on a single processor is how to assign executive time for each of a set of tasks in order to minimize the total tardiness, this problem is a kind of important basic problem of processor scheduling problems. This paper tackles the scheduling algorithm of this problem, and proposes an algorithm of assigning executive time for tasks by bi-backward approach based on sorting, which is named Bi-Backward Scheduling Algorithm. The algorithm＇s time complexity is O（n^2） ,and validated feasible. Otherwise, this paper also analyzes task relationships, and puts forward some concepts： tasks＇ inherent conflict, tasks＇ critical conflict time, task＇s time window center, tasks＇ indirect conflict, tasks＇ conflict degree and so on.

关 键 词：单处理器调度 调度算法 固有冲突 冲突度 临界冲突时刻 间接冲突 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置]