幾類(lèi)特殊的分批排序問(wèn)題.pdf

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

2、，…，J<,n>，每個(gè)工件的加工時(shí)間為p，運(yùn)輸時(shí)間為q<,j>．這些工件間有的工件可以在同一批中加工，而有的則不能在同一個(gè)批中加工．一批完工后并行地運(yùn)輸．這里的目標(biāo)函數(shù)是工件最后運(yùn)達(dá)顧客的時(shí)間．我們把這些工件分別對(duì)應(yīng)于一個(gè)圖G中不同的頂點(diǎn)，如果工件是相容的，則圖G中對(duì)應(yīng)的頂點(diǎn)間就可以連邊，否則就不連邊．通過(guò)這一轉(zhuǎn)換，我們就把工件的相容性約束通過(guò)圖論中具體的團(tuán)來(lái)刻畫(huà)，從而使解決相容性約束條件下的排序問(wèn)題顯得更加直觀(guā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-困難的，從而我們的問(wèn)題亦是NP-困難的．相容約束圖限定為某些特殊圖類(lèi)時(shí)，本文給出了多項(xiàng)式時(shí)間算法．主要結(jié)論如下： (1)相容約束圖G限定為

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

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

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

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

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