中文摘要：

排序和路线问题都是有很强应用背景的组合最优化问题，关于它们的高效算法的研究是当前国际上组合最优化研究的前沿领域，本项目对一些排序和路线问题的复杂性和算法，特别是在线算法进行了研究。对于线形网络上的单台机车调度问题，其中工件有就绪时间和处理时间要求，目标函数为时间表长，就机车需要返回和不需返回的情形分别设计了3/2和5/3近似算法。若工件没有处理时间要求，即便是多台机车调度，我们也获得了多项式时间最优算法。证明了树形网络上的两台机车流水作业问题是NP困难的，并就返回情形设计了13/9近似算法。对于一般网络上的自由作业问题，针对各种情形，皆得到了改进的近似算法。研究两台同类机上，目标函数为时间表长，工件列表到达的半在线排序问题，在已知工件最大加工时间时，针对两台机器速度比s的绝对多数取值给出了最好可能的算法；在可重排每台机器上最后一个工件时，针对s的所有取值给出了最好可能的算法。研究工件有到达时间约束的无容量限制的m台平行批处理机排序问题，关于m的所有取值给出了最好可能的在线算法。这些研究成果，一些解决了国际学术刊物上提出的待解决问题，一些是关于新问题、新方法的研究，有较高的学术价值。