【作者】 汪洋；

【导师】 王海明；

【作者基本信息】 兰州大学 ， 运筹学与控制论， 2008， 硕士

【摘要】 平行机排序是对单机排序问题的推广,同时又是研究许多更复杂的问题的基础。本文考虑了带传递时间的平行机排序问题。由于这个问题是NP-hard的,因而我们转为寻找问题的近似算法。我们考虑了三种近似算法:第一种为对偶阈值算法,在机器数为3时我们给出算法的界并证明其为紧的;第二种是LPT算法,我们给出它的一个界,但并不一定为紧界;针对一种更复杂的问题我们给出第三种算法,它是基于预处理算法的一种近似算法。以上三种算法都是多项式的,便于实现。更多还原

【Abstract】 Parallel machine scheduling problem is an extension of the single machine scheduling problem and the foundation of some more complicate problems.This paper considers the parallel machine scheduling problem with delivery times. The problem is NP-hard, so we want to find approximate algorithms to solve the problem. We investigate three approximate algorithms of the problem: the first one is the Dual-Threshold algorithm, and we give the bound of the algorithm when the number of the machines is 3 and we prove that the bound is tight; the second one is the LPT algorithm, and we give the bound of the algorithm which is not necessarily tight; for a more complicate problem we give an approximate algorithm based on the preprocessing algorithm. All of the three algorithms above are polynomial, so they can be easily realized.更多还原