论文部分内容阅读
平行机排序问题随着其约束条件及目标函数的不同而有许多种变形。本文研究了以覆盖问题作为约束条件的平行机排序问题，是一种以两个组合优化问题作为基本模型的组合问题。本文通过探讨各个组合优化问题的性质，并结合组合问题所具有独特的结构，提出了有效的近似算法。本文以顶点覆盖及一般的覆盖问题作为约束条件，结合了平行机排序问题的经典算法LPT算法以及覆盖问题的近似算法Local Ratio,给出了一系列的近似算法。其中对于顶点覆盖约束下的平行机排序问题，给出了(3-2/(m+1))近似比的LLR算法，其中m为机器数目。此外对于m=2的情形我们给出了2近似比的LRBi算法；随后我们将LLR算法的想法推广到对于一般覆盖约束条件下的平行机排序问题模型，给出了(r+max{0,(m-r)/r})近似比的LArE算法，其中r表示覆盖问题的Ar算法的近似比；最后我们给出可任意近似到(r+∈)近似比的LArE_∈算法，并与之前的结果进行了比较。本文的创新点如下：1、关于平行机排序和顶点覆盖的组合问题给出(3-2/(m+1))近似算法。2、在组合算法的基础上，融入了在一定条件下进行枚举的思想，从而得到更有效的算法。3、关于平行机排序和覆盖问题的组合问题，当机器数目固定时本文给出近似比最优的多项式时间算法。