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

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

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

3、(√5+1/2)的最好可能在線算法.
　　 第三章考慮了單機(jī)在線分批排序問題,工件帶有運(yùn)輸時(shí)間,目標(biāo)函數(shù)為最小化工件的最大運(yùn)輸完工時(shí)間.利用Graham等人(1979)引入的三參數(shù)法,該問題可表示為:
　　 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,
　　 我們給出了一個(gè)競爭比為(√5+1/2)的最好可能的在線彈性算法.對于限制問題
　　 1｜p-batch,on-line,qmax＼qmin≤1+α,B=∞｜Lmax,我們證明了Poon和Yu(2005)的彈性算法的競爭比不超過(√5+1/2),也就是說,該彈性算法仍是最好的.
　　 第四章總