| 异时排序问题的算法复杂性 |
| |
| 引用本文： | 杨晓光.异时排序问题的算法复杂性[J].应用数学与计算数学学报,1999,13(2):94-96. |
| |
| 作者姓名： | 杨晓光 |
| |
| 作者单位： | 中国科学院系统科学研究所管理决策与信息系统开放实验室!北京，100080 |
| |
| 摘 要： | 我们将限制某些工件不能同时处理的平行机排序问题称为异时排序问题．本文我们讨论工件加工时间相同、目标为总完工时间最小的异时排序问题．我们证明了当机器台数为2时，该问题等价于图上的最大匹配问题，因此存在组合强多项式时间算法；但量当机器台数为3或者多于3时，该问题是强NP困难的．
|
| 关 键 词： | 异时排序 等工时 最大匹配 强NP困难 |
Complexity of Non-Simultaneously Scheduling Problem |
| |
| XIAOGUANG YANG.Complexity of Non-Simultaneously Scheduling Problem[J].Communication on Applied Mathematics and Computation,1999,13(2):94-96. |
| |
| Authors: | XIAOGUANG YANG |
| |
| Abstract: | In this paper, we consider a multiprocessor scheduling model to minimize the makespan whichrequires some jobs can not be processed simultaneously We only consider the equal execution timecase. If there are only two machines, we show that the scheduling problem is equivalent to maximummatching problem on a graph, hence can be solved in combinatorial strongly polynomial algorithm.But if there are three or more machines, we show the the scheduling problem is NP-hard in thestrong sense. |
| |
| Keywords: | non simultaneous equal execution time maximum matching NP-hard |
| 本文献已被 CNKI 维普 等数据库收录！ |
