23147.具有交貨期或友好釋放時間的在線排序研究

1、AthesissubmittedtoZhengzhouUniversityforthedegreeofdoctorResearchononlineschedulingwithdeadlines●●●orKlndreleaSetlmeSByWenjieLiSupervisor：ProfJinjl’angYuanPureMathematicsSchoolofMathematicsandStatisticsMarch，2014摘要在線排序是現(xiàn)

2、代排序中的核心研究方向，廣泛地應(yīng)用于生產(chǎn)管理、物流運輸、商品銷售、網(wǎng)絡(luò)服務(wù)等很多領(lǐng)域。近二十年來，在線排序得到國內(nèi)外同行的廣泛關(guān)注和深入研究，并促使其成為現(xiàn)代排序領(lǐng)域中發(fā)展最為迅速的方向之一。本文所說的“在線”是指時間在線(onlineovertime)。也就是說，工件是隨著時間依次到達(dá)的，并且只有在工件的到達(dá)時間我們才能詳知它的一切信息。我們有以下三種關(guān)于時間在線的排序模型：不可中斷模型(nonpreemptivemodel)，中斷可

3、續(xù)模型(preemption—resumemodel)，中斷重啟模型(preemptionrestartmodel)。人們通常用競爭比來衡量一個在線算法的性能。對一個最大化目標(biāo)函數(shù)的在線排序問題，我們稱在線算法4是p競爭的(P≥1)，如果對任一實例I都有A(，)≥(1／p)OPT(／)成立，其中4(I)表示，在算法A生成的排序下的目標(biāo)值，OPT(／)表示，在離線最優(yōu)排序下的目標(biāo)值。類似的，對一個最小化目標(biāo)函數(shù)的在線排序問題，稱4是p競爭

4、的如果滿足4(J)≤POPT(／)。由此可見，競爭比P越接近于1，就表明在線算法的性能越優(yōu)良。在第二章中，我們研究多組不兼容等長工件多臺平行批處理機在線排序問題。在該問題中，同組工件可以放入一個加工批中進(jìn)行加工，不同組的工件不能在同一批被加工。每一批最多可加工b個工件，b=oo表示批容量無界，b0，一個整的釋放時間r(J)≥0，一個整的必須交貨期d(J)≥0和一個實數(shù)的權(quán)值w(J)≥0。目標(biāo)是確定一個工件可以中斷重啟的在線排序使得按時完