| 关于延误时间的平行机排序问题的复杂性 |
| |
| 引用本文： | 苏纯洁. 关于延误时间的平行机排序问题的复杂性[J]. 华东理工大学学报(自然科学版), 2002, 28(6): 657-660,664 |
| |
| 作者姓名： | 苏纯洁 |
| |
| 作者单位： | 华东理工大学数学系,上海,200237 |
| |
| 基金项目： | 国家青年基金资助项目 (10 10 10 0 7) |
| |
| 摘 要： | 研究了当目标函数和延误时间有关时，带两个服务器的3台平行机排序总是的复杂性。首先证明了P3，S2/si=1/Lmax是强NP-难的，然后证明了另两个问题P3，S2/Pi=1/Lmax和P3，S2/si=1，di=d/Lmax都是NP-难的。
|
| 关 键 词： | 服务器 平行机 排序 复杂性 |
| 文章编号： | 1006-3080(2002)06-0657-04 |
The Complexity of the Parallel Machine Scheduling about Tardiness |
| |
| SU Chun-jie. The Complexity of the Parallel Machine Scheduling about Tardiness[J]. Journal of East China University of Science and Technology, 2002, 28(6): 657-660,664 |
| |
| Authors: | SU Chun-jie |
| |
| Abstract: | In this paper, the complexity of the parallel machine scheduling with two servers was studied. It is proved that the P3,S2/s_i=1/L_ max problem is strong NP-hard. Then it is also proved that the other two problems P3,S2/p_i=1/L_ max and P3,S2/s_i=1,d_i=d/L_ max are NP-hard. |
| |
| Keywords: | server machine scheduling complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
