1、本文研究同類平行機(jī)上的在線、半在線排序問題.全文共分為四章.
　　 第一章主要介紹了排序問題的基本概念，并給出了相關(guān)符號和定義.
　　 第二章研究三臺同類機(jī)上的在線排序問題Q3/online/Cmax·記sj為機(jī)器的加工速度，j=1，2，3.且設(shè)0

2、t<1+√31/6，s≥3t/5+2t-6t2}而G2={(s，t)｜t≥1+s，s≥1).當(dāng)(s，t)∈G1時，LS算法的競爭比為1+s+2st/s+st；而當(dāng)(s，t)∈G2時，LS算法的競爭比為1+s/st+1.此外，對于任意的(s，t)，LS算法的競爭比不超過min{1+s+2st/s+st，1+s/st+1，1+s+3st/1+s+st}，且在常數(shù)競爭比的意義下，LS算法是最好的在線算法，其競爭比為2.
　　 第三章研

3、究兩臺同類機(jī)上的預(yù)先知道工件最大長度這一部分信息下的半在線排序問題.記sj為機(jī)器的加工速度，j=1，2.且設(shè)0

4、半在線問題的下界等于“純”在線算法LS的競爭比，這也就意味著此時預(yù)先知道工件最大長度這一部分信息對改進(jìn)算法的性能沒有用處.
　　 第四章研究在三臺特殊的同類機(jī)上，預(yù)先知道工件最大長度這一部分信息下的半在線機(jī)器覆蓋問題.記sj為機(jī)器的加工速度，j=1，2，3.且設(shè)0