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

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

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

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

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