文献类型：期刊文献

中文题名：关于延误时间的平行机排序问题的复杂性

英文题名：The Complexity of the Parallel Machine Scheduling about Tardiness

作者：苏纯洁[1]

机构：[1]华东理工大学数学系,上海200237

年份：2002

卷号：28

期号：6

起止页码：657

中文期刊名：华东理工大学学报（自然科学版）

外文期刊名：Journal of East China University of Science and Technology

收录：CSTPCD;;国家哲学社会科学学术期刊数据库;Scopus;北大核心:【北大核心2000】；CSCD:【CSCD2011_2012】；

基金：国家青年基金资助项目 (10 10 10 0 7)

语种：中文

中文关键词：服务器;平行机;排序;复杂性

外文关键词：server; machine; scheduling; complexity

摘要：研究了当目标函数和延误时间有关时 ,带两个服务器的 3台平行机排序问题的复杂性。首先证明了 P3 ,S2 /si=1 /Lmax是强 NP-难的 ,然后证明了另两个问题 P3 ,S2 /pi=1 /Lmax和 P3 ,S2 /si=1 ,di=d/Lmax都是
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.