帶有運輸?shù)膯螜C平行分批在線排序問題.pdf

1、所謂排序，就是在一定的約束條件下分配時間資源去完成一些任務，使一個或多個目標達到最優(yōu)。近年來，在線排序和分批排序是兩個發(fā)展比較迅速的排序模型。在線排序是指工件信息在其到達之前是一無所知的，并且一旦工件被安排后就不允許再改變。平行分批排序是指機器可以同時加工多個工件，每批的加工時間是這批工件中所有工件加工時間的最大者。一旦批開始加工就不能被中斷，直到該批被加工完畢。 本文中，我們研究了一種在線排序模型：帶有運輸?shù)膯螜C平行分批在線排

2、序問題。在這里，我們有一臺批處理機和充分多的車輛。有n個工件J1，J2，Jn，每個工件都分別有一個到達時間rj，加工時間pj和運輸時間qj。工件的這些信息在其到達之后我們才能獲得。在此問題中，每個工件需要在機器上加工，并且工件一旦完工就由車輛將其運送到目的地。我們的目標函數(shù)是最小化所有工件被運到目的地所花費的時間。用Graham等人[4]提出的三參數(shù)表示法，我們的問題可以表示為：1|on-line,rj，qj，B|Dmax，其中Dmax

3、=max{Dj|Dj=Cj+qj，1≤j≤n}.本文的主要結果如下： (1)給出了排序模型1|on-line,rj，qj，B=∞|Dmax的一個競爭比不超過2的在線算法。 (2)給出了排序模型1|on-line,rj，qj，pj=p，prec,B=∞|Dmax一個競爭比為(√5+1)/2的在線算法。該在線算法是最好可能的。 (3)給出了排序模型1|on-line,rj，qj,B＜n|Dmax的一個競爭比不超過3的