兩類在線分批排序問題研究.pdf

1、排序論是組合優(yōu)化的一個重要分支,對它的研究有著深刻的理論意義和重要的應用前景.在線排序和分批排序是近年來排序論研究中十分活躍的前沿課題.本文對兩個在線平行分批排序問題進行了研究.論文的主要內容如下:
　　 第一章簡單介紹了排序問題的相關定義、記號及相關知識.
　　 第二章考慮了兩臺機器在線分批排序問題,其中一臺是批處理機,一臺是標準機；目標函數為極小化工件的最大完工時間.利用Graham等人(1979)引入的三參數法,該

2、問題可表示為
　　 P2｜on-line,p-batch,B1=∞,B2=1｜Cmax.
　　 對上述一般問題,我們首先給出了一個改進的下界1+β,其中β=√2/2≈0.707.接著給出了兩個競爭比為2的簡單在線算法.最后設計了兩個有待進一步研究的在線算法.對限制問題
　　 P2｜on-line,p-batch,agreeable(rj,pj),B1=∞,B2=1｜Cmax,
　　 我們給出了一個競爭比為

3、(√5+1/2)的最好可能在線算法.
　　 第三章考慮了單機在線分批排序問題,工件帶有運輸時間,目標函數為最小化工件的最大運輸完工時間.利用Graham等人(1979)引入的三參數法,該問題可表示為:
　　 1｜p-batch,on-line,B=∞｜Lmax.對于限制問題
　　 1｜p-batch,on-line,Pj≥qj,B=∞｜Lmax,
　　 1｜p-batch,on-line,agreeabl

4、e(pj,qj),B=∞｜Lmax和
　　 1｜p-batch,on-line,Pj=P,B=∞｜Lmax,
　　 我們給出了一個競爭比為(√5+1/2)的最好可能的在線彈性算法.對于限制問題
　　 1｜p-batch,on-line,qmax＼qmin≤1+α,B=∞｜Lmax,我們證明了Poon和Yu(2005)的彈性算法的競爭比不超過(√5+1/2),也就是說,該彈性算法仍是最好的.
　　 第四章總