一类多机排序问题算法及其计算复杂性研究  

The Algorithm and its Computational Complexity for a Type of Problem of Scheduling Multiprocessor Tasks

作　　者：杨汉兴[1] 

机构地区：[1]武汉冶金科技大学管理工程系

出　　处：《武汉冶金科技大学学报》1997年第3期373-379,共7页

摘　　要：在经典排序论中，一般都假设每个工件在任一时刻仅被一台机器加工，且每台机器至多仅加工一个工件。在这篇文章中，研究这样一类排序问题：每个工件可以被多个不同的机器子集加工，其加工速度对于不同的机器子集是不同的，被加工的工件假定是可以间断且是独立的。排序问题的性能测度是排序长度。在以上条件下求解这类问题算法被给出，对其计算复杂性也作了研究。In classical scheduling theory,it is generally assumed that each task can be processed by one processor at a time and that a processor is capable of processing at most one task at a time.In this paper,such type of scheduling multiprocessor tasks is analyzed:Each task is allowed to be executed by any of more than subset of processors and its processing speed is different for distinct subset of processors.Tasks are assumed to be preemptable and independent.The performance measure of the scheduling problem is schedule length.Under above conditions the polynomial time algorithm for the problem is given and its computational complexity has been studied as well.

关 键 词：计算复杂性 多项式时间算法 排序论 算法 

分 类 号：O226[理学—运筹学与控制论]