本文主要研究两台平行机上平行工件的在线排序和一类三阶段供应链排序问题。　　 全文共四章。　　 第一章介绍排序问题的基本概念和相关知识,并总结国内外研究现状及本文研究结果。　　 第二章主要讨论带惩罚时间的两台平行机上平行工件的在线排序问题。对于平行工件Jj,若放在单台机上加工,其执行时间为tj=pj;若安排在两台机上加工,则需要给一个惩罚时间cj,即此时工件的执行时间为tj=pj/2+cj。目标函数是极小化最大完工时间。当惩罚时间不同时,给出竞争比为1+α1的最优算法(其中α1=(√5-1)/2);当惩罚时间相同时,分别给出了渐近性能比为3/2和绝对性能比为α2≈1.54的在线近似算法,α2为α32-2α22+2α2-22=0的根。　　 第三章研究一类三阶段供应链排序问题。储存工件的仓库和工厂在不同的地点,工件加工前需要从仓库运到工厂,加工完后再运回仓库。文中主要考虑两种模型,第一种是两辆有容量限制的同类型车和单台机;第二种是一辆车和两台平行机。目标函数是极小化最后一个工件运回仓库的时间。工件加工时是不可中断的。针对两个模型,提出相应算法并证明其最坏情况界为2和2+1/λ-1(其中λ＞1)。　　 第四章对全文进行总结并展望待研究的问题。