兩類特殊的在線分批排序問題.pdf

1、1045905321136文學(xué)論大位州學(xué)鄭士碩論文題目:作者姓名:學(xué)科門類:專業(yè)名稱:研究方向:導(dǎo)師姓名、職稱:兩類特殊的在線分批排序問題王申重理學(xué)運(yùn)籌學(xué)與控制論圖論與組合最優(yōu)化李文華教授二零零八年四月摘要本文主要考慮了兩類特殊的在線分批排序問題.所謂在線，本文指的是按時(shí)在線.工件信息在其到達(dá)之前是一無所知的，并且一旦工件被安排后就不允許再改變.所謂平行分批排序是指機(jī)器可以同時(shí)成批加工多個(gè)工件.每批包含的工件同時(shí)開工同時(shí)完工，批的加工時(shí)

2、間是這批中加工時(shí)間的最大者.首先研究了批容量為3的單機(jī)平行分批排序.主要結(jié)果如下:(l)對排序問題11一‘a(chǎn)teh，6=3:，，=1on一l，ne，r‘:l，m、tedrestar，slCmax，我們給出了競爭比為號的最好可能的在線算法.(2)對排序問題1凈一6a:ch，6=3on一l乞ne，r‘l壇m蔥tedresta:tsl味a二，我們證明了竟?fàn)幈认陆鐬闀x，并給出了競爭比為號的在線算法.其次，對帶有特殊工件的平行分批排序問題進(jìn)行了研

3、究.這里所有工件都是在線的，但是，其中有一些工件，它們要求單獨(dú)成批，其它工件不能與其共批，并且一旦到達(dá)就要對其立即加工。我們稱其為特殊工件，其它工件稱為普通工件.假設(shè)特殊工件間不沖突.主要結(jié)果如下:(1)對排序I可題1卜pee蔥alJob(restart)腸=1o。一l蔥ne，r‘，DI藝無，我們給出了競爭比為普的最好可能的在線算法.(2)對排序問題PZls尹ee‘a(chǎn)ljo6伽m:n):p一bateh，b=ocon一l蔥ne，r‘I嶸a