本文主要研究了一些新型平行机排序问题和路线问题,包括工件有加工机器限制的排序问题、带有缓冲器的平行机排序问题、遍历每条边的修理员问题以及货运码头堆场排序问题。我们分析了这些问题的复杂性,设计了相应的算法,理论分析了这些算法的性能,并对部分算法进行数值模拟来验证算法的有效性。第一章介绍了组合优化问题的背景,阐述了一些本文涉及的理论知识,例如算法复杂性、NP完备理论、线性规划的舍入以及匹配的相关概念和定理,最后介绍了排序问题和路线问题的定义以及所研究问题的国内外研究状况。第二章研究了工件有加工机器限制的排序问题,给定m台机器和n个工件,每个工件Jj只能选择在给定的一个机器集合Mj上加工,加工时间为pj,目标是极小化时间表长。首先,当任意工件Jj均有|Mj| = 2时,我们给出了一个1.883-近似算法。然后我们分析了当工件的加工机器集合Mj为一个连续区间的情形:证明了当工件只有两种大小,且大工件大于1/2倍目标值时,这个问题是可解的;当所有工件的|Mj|均相等时,我们设计了一个PTAS。最后,我们给出一些负面结果.:考虑工件至多能在三台变速机上加工,如果该问题有(2-ε)近似算法,则经典问题R||Cmax也会有(2-ε)-近似算法;考虑异速机上的Graph Balancing问题,如果该问题有(2-ε)-近似算法,则Unrelated Graph Balancing 问题也会有(2-ε)-近似算法。第三章研究了带有缓冲器的平行机排序问题,目标是极小化完工时间之和。在该问题中,工件的顺序给定。如果没有缓冲器,我们只能按照这个顺序依次安排工件到机器上加工;如果工件在加工之前需进入容量为κ的缓冲器,我们可以在缓冲器中的κ个工件中随意挑选一个来加工,所以缓冲器可以让我们一定程度的修改工件顺序。首先,我们给出了反例,说明按照经典排序问题的排序规则无法得到最优解。然后当机器数量和缓冲器容量均给定的情况下,我们设计了一个多项式时间的动态规划算法。最后证明若机器数量是任意的,即使缓冲器容量为1,其加权完工时间和问题也是强NP-困难的。第四章考虑了一个路线问题。对一个图,我们从出发点开始寻找一条路线,使得该路线访问每条边至少一次,使得所有边的访问时间之和最小,这里每条边的访问时间可理解为边上有若干“点”的访问时间之和。该问题不同于经典的中国邮递员问题或者旅行售货员问题,是旅行修理员问题的一种特殊情形,我们称为遍历边的修理员问题。我们证明了这个问题无论在有向图还是无向图下均是NP-困难的,并设计了一个(?)近似算法。当图是二连通时,我们给出了一个4/3-近似算法。第五章我们研究了一个货运码头堆场排序问题,堆场上有多台取料机同时作业来完成任务,每台机器占据一条直线轨道,原材料成堆的存放在轨道两边,机器需要先移动到原材料的位置,然后开始加工采集。如何给机器分配加工任务和加工顺序,极小化时间表长。当机器允许同时加工同一位置上的原材料时,我们设计了一个FPTAS。当机器不允许同时加工同一位置的材料时,我们设计了一个2-近似算法,并对只有两台机器的情形,我们设计了一个3/2-近似算法,最后对这两个近似算法使用数值模拟来验证算法的有效性。第六章对本文进行总结,并提出一些今后可以继续研究的方向。