本文研究了一些由三个经典的车间排序问题,和最短路问题各自组合而成的组合问题。问题的目的是在一个工件集中选取一个子集,使其构成一个最短路问题的可行解,然后把工件安排到一个车间进行排序,使所得排序的最大完工时间最小。本文先对这些问题的计算复杂性进行研究。第一个结果是即使在只有两台机器的情况下,这些问题仍是NP难的。第二个结果是当机器数目作为问题的输入时,除非P=NP,这些问题不存在近似比小于2的多项式近似算法。随后根据每一个问题的特点设计相应的近似算法,并对这些算法的时间复杂性和近似比进行分析。最后讨论把问题的结果推广到车间排序和最小支撐树,或和一个更广泛的covering问题的组合问题上。本文表明前面的研究结果基本都可以推广到车间排序和这两个问题各自的组合问题上。本文主要的创新点如下:1.通过结合车间排序问题和最短路(最小支撐树、covering)问题,提出一系列新的组合优化问题,并证明了这些问题的计算复杂性和提出了相应的近似算法。2.针对车间排序问题的特点,提出了一个比covering问题更广泛的问题,把它应用到车间排序问题和它的组合问题的定义上,并得到一个对组合优化问题的组合问题适用性更广泛的定义。3.对于这些组合问题,根据车间排序问题的已有算法返回的解的特点,通过重复迭代算法和修正权重的思想,设计出一系列有效求解的近似算法,同时进一步扩展了这个思想的应用。