| 一类多机排序问题算法及其计算复杂性研究 |
| |
| 引用本文： | 杨汉兴.一类多机排序问题算法及其计算复杂性研究[J].武汉科技大学学报(自然科学版),1997(3). |
| |
| 作者姓名： | 杨汉兴 |
| |
| 作者单位： | 武汉冶金科技大学管理工程系 |
| |
| 摘 要： | 在经典排序论中，一般都假设每个工件在任一时刻仅被一台机器加工，且每台机器至多仅加工一个工件。在这篇文章中，研究这样一类排序问题：每个工件可以被多个不同的机器子集加工，其加工速度对于不同的机器子集是不同的，被加工的工件假定是可以间断且是独立的。排序问题的性能测度是排序长度。在以上条件下求解这类问题算法被给出，对其计算复杂性也作了研究。
|
| 关 键 词： | 计算复杂性 多项式时间算法 非多项式时间算法 |
The Algorithm and its Computational Complexity for a Type of Problem of Scheduling Multiprocessor Tasks |
| |
| Yang Hanxing.The Algorithm and its Computational Complexity for a Type of Problem of Scheduling Multiprocessor Tasks[J].Journal of Wuhan University of Science and Technology(Natural Science Edition),1997(3). |
| |
| Authors: | Yang Hanxing |
| |
| Institution: | Yang HanxingDepartment of Management Engineeing,Wuhan Yejin University of Science and Technology,Wuhan 430081,China. |
| |
| Abstract: | 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. |
| |
| Keywords: | computational complexity polynomial time algorithm non polynomial time algorithm |
| 本文献已被 CNKI 等数据库收录！ |
