文献类型：期刊文献

中文题名：带服务器的三台平行机排序问题的复杂性和近似算法

英文题名：THE COMPLEXITY AND APPROXIMATION ALGORITHM OF P_3,S_2//C_(max)

作者：苏纯洁[1]

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

年份：2003

卷号：26

期号：3

起止页码：544

中文期刊名：应用数学学报

外文期刊名：Acta Mathematicae Applicatae Sinica

收录：CSTPCD;;北大核心:【北大核心2000】；CSCD:【CSCD2011_2012】；

语种：中文

中文关键词：服务器;平行机;排序问题;复杂性;近似算法;NP-困难;三元划分问题

外文关键词：Parallel machine, server, complexity, approximation algorithm

摘要：本文研究了带服务器的三台平行机排序问题的复杂性,并给出了一个最好的在线近似算法。
We study the complexity of the three parallel machines scheduling problem with two servers, and we construct a best-possible on-line approximation algorithm.