SCHEDULING INDEPENDENT TASKS WITH DEADLINES ON SEMI-IDENTICAL PROCESSORS

被引：38

作者：

SCHMIDT, G

机构：

[1] Technical Univ of Berlin, West Ger, Technical Univ of Berlin, West Ger

来源：

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY | 1988年 / 39卷 / 03期

关键词：

JOB ANALYSIS - MATHEMATICAL TECHNIQUES - Algorithms;

D O I：

10.1057/jors.1988.44

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

Given m semi-identical processors which are parallel processors all working with the same speed but in different time intervals of availability and n independent tasks with deadlines, the problem of constructing a feasible pre-emptive schedule is examined. We present an O(mm log n) time algorithm to construct such a schedule whenever one exists. We show that the number of induced pre-emptions is proportional to the total number of processing intervals and deadlines.

引用

页码：271 / 277

页数：7