平行机排序问题是组合优化领域的一个基本问题，自从在二十世纪五十年代被提出后，平行机排序问题被人们广泛地研究，许多变种问题也孕育而生。尽管关于平行机排序，现有的模型已经有很多，然而这些模型的共同点是，要么就强制要求分配所有的工作，要么就对无法分配的工作给予一个惩罚。近期，王和崔提出了一个全新的研究思路，即研究平行机排序问题和另一个组合优化问题X的组合问题，确切地说，我们只需要在平行机排序问题中分配对应于X的一个可行解的那部分工作。他们首先考虑点集覆盖和平行机排序的组合问题并给出了一个3=2/(m+1)近似算法。此后，王提出了研究平行机排序与一类称为广义覆盖问题的最小化问题的组合问题模型，而贺在此基础上，提出了以最大化最快完工时间为目标函数的平行机排序问题和一类称为广义包裹问题的最大化问题的组合问题模型并给出了相应的近似算法。本文将针对上面提到的三个问题模型，即平行机排序与点集覆盖的组合问题，平行机排序与广义覆盖问题的组合问题和平行机排序与广义包裹问题的组合问题设计和改进现有的近似算法，以达到更好的最坏情形比。同时，对于平行机排序与点集覆盖的组合问题模型的算法，给出一个针对平行机排序与击中集的组合问题模型的推广。而对平行机排序与广义覆盖问题的组合问题模型，给出几个实例。本文还会对这三个问题模型给出实际生活中的应用背景。