帶有運(yùn)輸?shù)膯螜C(jī)平行分批在線排序問(wèn)題.pdf

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

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

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