幾類特殊的分批排序問題.pdf

1、平行分批排序和在線排序是兩個發(fā)展比較迅速的排序模型．平行分批排序是指機器可以同時加工多個工件，每批包含的工件同時開工同時完工，批的加工時間是這批工件中加工時間的最大者。在線排序是指工件信息在其到達之前是一無所知的，并且一旦工件被安排后就不允許再改變。 本文主要考慮了幾類特殊的分批排序問題。首先研究了工件具有相容約束的帶有運輸?shù)膯螜C平行分批排序問題．在這里，我們有一臺批處理機和充分多的車輛．有n個同工時的工件J<,1>，J<,2>

2、，…，J<,n>，每個工件的加工時間為p，運輸時間為q<,j>．這些工件間有的工件可以在同一批中加工，而有的則不能在同一個批中加工．一批完工后并行地運輸．這里的目標(biāo)函數(shù)是工件最后運達顧客的時間．我們把這些工件分別對應(yīng)于一個圖G中不同的頂點，如果工件是相容的，則圖G中對應(yīng)的頂點間就可以連邊，否則就不連邊．通過這一轉(zhuǎn)換，我們就把工件的相容性約束通過圖論中具體的團來刻畫，從而使解決相容性約束條件下的排序問題顯得更加直觀．于是我們所考慮的模型可

3、記為1｜p-batch；p<,j>=p，q<,j>；G｜D<,max>，其中，圖G就是代表我們所討論的工件相容約束性，D<,max=max{D<,j>｜D<,j>=C<,j>+q<,j>，1≤j≤n}．由張群發(fā)的碩士學(xué)位論文[8]可知1｜p-atch；p<,j>=p；G｜C<,max>是NP-困難的，從而我們的問題亦是NP-困難的．相容約束圖限定為某些特殊圖類時，本文給出了多項式時間算法．主要結(jié)論如下： (1)相容約束圖G限定為

4、分裂圖時，文中給出了問題1｜p-batch；p<,j>=p，g<,j>；G｜D<,max>的時間界為D(n<'2>)的最優(yōu)算法． (2)相容約束圖G限定為完全二部圖時，文中給出了問題1｜p-batch；p<,j>=p，q<,j>G｜D<,max>的時間界為O(nlogn)的最優(yōu)算法。 (3)相容約束圖G限定為完全m部圖時，文中給出了問題1｜p-batch；p<,j>=p，q<,j>G｜D<,max>的時間界為O(nlog

5、n)的最優(yōu)算法。 (4)相容約束圖G限定為直徑不超過4的樹時，文中給出了問題1｜p-batch；p<,j>=p，q<,j>G｜D<,max>的時間界為O(nlogn)的最優(yōu)算法。 其次，本文對帶有禁用區(qū)間的目標(biāo)為最小化最大完工時間的單機平行分批排序問題進行了研究．在經(jīng)典排序中，所有機器都是假設(shè)在整個加工過程中一直可用。然而，這個假設(shè)往往太過理想，在實際生產(chǎn)過程中，情形可能并非如此。由于對機器的預(yù)防性維修或機器突然出現(xiàn)故障

6、都會導(dǎo)致機器在某一段時間內(nèi)不能使用，有時候我們也把機器不能使用的這一段時間叫做機器的禁用區(qū)間。我們假設(shè)機器的禁用區(qū)間是在工件就緒前已經(jīng)確定的。工件就只能在剩下的時間內(nèi)加工。文中考慮兩種禁用情形：若一個批在禁用區(qū)間之前未能完工而它在機器重新可用后可以接續(xù)加工,這種情形稱為可繼續(xù)的，用記號r-a來表示；若該批不可接續(xù)而只能重啟，即從頭開始加工，我們稱為不可繼續(xù)的，用記號nr-a表示，這是借文獻[10]的用法．本文對離線情形，要么給出了多項式

7、時間算法，要么給出了近似算法；對一般在線情形，給出了其競爭比的下界可任意大的證明，并對特殊情形給出了最好可能的算法．本文最后對帶有強制工件的單機在線分批排序問題進行了討論．這里所有工件都是在線的，但是，其中有一些特殊工件，它們要求單獨成批，其它工件不能與其共批，并且一旦到達就要對其立即加工，我們稱其為強制工件(master job)，其它工件稱為自由工件．假設(shè)強制工件間不沖突．該模型可記為1｜masterjob；p-batch，B；on

8、-line,T<,j>｜C<,max>文中考慮了和強制工件相沖突的批可中斷(pmtn)與需要重啟(restart)兩種情形，主要結(jié)果如下： (5)給出了問題1｜masterjobf(restart)；p-batch，6=∞；on-lineT<,j>｜C<,max>的競爭比下界及最好可能算法． (6)給出了問題1｜masterjob(restart)；p-batch，b｜C<,max>的競爭