AN O(N LOG N) FEASIBILITY ALGORITHM FOR PREEMPTIVE SCHEDULING OF N INDEPENDENT JOBS ON A HYPERCUBE

被引：6

作者：

AHUJA, M

ZHU, YH

机构：

[1] Department of Computer and Information Science, The Ohio State University, Columbus

来源：

INFORMATION PROCESSING LETTERS | 1990年 / 35卷 / 01期

关键词：

balanced search tree; Hypercube; preemptive scheduling;

D O I：

10.1016/0020-0190(90)90166-U

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a new feasibility algorithm to decide if n independent jobs can be finished by a given deadline T on an m-dimensional hypercube system. It takes O(n log n) time and generates a schedule with at most n -2 preemptions. A previously known algorithm takes O(n2) time and produces a schedule with up to 1 2n(n-1) preemptions. © 1990.

引用

页码：7 / 11

页数：5