金世國，張巧利

（1.鄭州信息科技職業(yè)學(xué)院，河南 鄭州 450046；2.河南廣播電視大學(xué)，河南 鄭州 450008）

工件帶有相容約束性及運(yùn)輸時間的分批排序研究

金世國1，張巧利2

（1.鄭州信息科技職業(yè)學(xué)院，河南 鄭州 450046；2.河南廣播電視大學(xué)，河南 鄭州 450008）

近年來，工件帶有相容約束性的加工運(yùn)輸問題在物流和供應(yīng)鏈管理領(lǐng)域得到了廣泛地關(guān)注。這里討論相應(yīng)的單機(jī)平行分批排序問題，首先把工件間的相容約束用圖來刻畫，進(jìn)一步給出了問題的復(fù)雜性，并對相容約束圖為分裂圖的情形，給出了時間界為O(n2)的多項(xiàng)式時間算法。

相容約束；單機(jī)；平行分批

在排序論中，工件是被加工的對象；機(jī)器是提供加工的對象。分批排序問題是指若干個工件可以在同一批加工，加工過程中不允許中斷。平行分批排序是指機(jī)器可以同時加工多個工件，每批工件同時開工與完工，該批工件中，加工時間的最大者稱為批的加工時間。現(xiàn)有一臺批處理機(jī)和足夠多的車輛，n 個工件J1,J2,… ,Jn需要在機(jī)器上加工，完工后用車輛將其運(yùn)送到目的地。每個工件加工時間pj，運(yùn)輸時間qj。其中有的工件可以放在同批中加工，而有的工件不能在同批加工。一批完工后并行地運(yùn)輸。批B的加工時間為

i完工時間用C(Bi)來表示，運(yùn)輸時間 。因而產(chǎn)生這樣一個問題：在工件具有這種相容約束的條件下，如何進(jìn)行分批，如何對這些批排序，可以使得這樣的分批排序的目標(biāo)函數(shù)值最?。课覀冞@里考慮目標(biāo)為工件最后到達(dá)顧客時間的情形。把工件的相容約束條件用一個圖來刻畫．把工件集對應(yīng)于有n個頂點(diǎn)的圖G的頂點(diǎn)集；然后考慮圖的邊集，任兩個頂點(diǎn)連邊當(dāng)且僅當(dāng)對應(yīng)的工件是相容。

對于工件帶運(yùn)輸時間或單機(jī)平行分批排序問題，已經(jīng)有了很多研究成果。Lawer等證明了離線時是強(qiáng)NP困難的，但是若工件允許被打斷此時問題變?yōu)榱硕囗?xiàng)式可解，同時當(dāng)工件到達(dá)時間一致時，存在著名的LDT (the longest delivery timefirst)算法，當(dāng)工件不同時到達(dá)時，Kise等證明了LDT算法的競爭比為2。

1 問題的復(fù)雜性

團(tuán)分解問題：給定團(tuán)G =(V,E)和整數(shù)K ≤V，則問圖G 的頂點(diǎn)能否被劃分為k ≤K個不交的子集合V1,V2,… ,Vk，使得圖G[Vi](1 ≤ i ≤k)是圖G的一個完全子圖。

引理1： 團(tuán)分解問題是NP困難。

命題1 ：問題1| p? batch; pj=p,qj=q;G|Dmax是NP困難。

證明：顯然，該排序問題的判定問題屬于NP類。

用團(tuán)的分解問題來做歸結(jié)。我們由引理1得知，團(tuán)分解問題是NP困難的。給團(tuán)分解問題的一實(shí)例G =(V,E)和正整數(shù)K，構(gòu)造1| p? batch; pj=p,qj=q;G|Dmax的判定問題的實(shí)例如下：V(G)的n 個頂點(diǎn)分別對應(yīng)n 個有同一工時p及運(yùn)輸時間q的工件，同時記門檻值為Y = Kp+q。此時，排序問題的判定問題為：是否有平行分批排序π使得Dmax以給定的門檻值作為上界，即Dmax≤Y？如果團(tuán)分解問題有解，也就是存在一整數(shù)k ≤K，使圖G的頂點(diǎn)集V(G)被劃為k 個不相交的子集且每一子集的導(dǎo)出子圖G[Vi](1 ≤ i ≤k)均為圖G的完全子圖，則排序問題中團(tuán)Vi視為一批，即有k批，且批序列為一可行排序。明顯，Dmax= kp +q ≤Y 是成立的，所有排序問題有解。反之，如果該排序問題有解，也就是存在一可行排序π，滿足Dmax≤Y = Kp+q 。不失一般性設(shè)則有Dmax=kp + q ≤Y =K p +q，把VBi作為批Bi中工件的頂點(diǎn)集，G[VBi]為圖G 的完全子圖，那么劃分VB1,… ,VBk是團(tuán)分解問題的一解。

2 相容約束為分裂圖時算法

圖G =(V,E)為分裂圖，是指其頂點(diǎn)集可以分為兩個部分：V = X ∪ Y,X ∩ Y =? ，其中X為獨(dú)立集，Y為團(tuán)，且除G[Y ]內(nèi)的邊外，E還有一些X與Y間的邊。這里工件集的相容約束用分裂圖G 表示，其中工件集是圖G 的頂點(diǎn)集。從而及為工件集?，F(xiàn)假設(shè)工件加工時間均為p ，xi的運(yùn)輸時間為q(xi)，yj的運(yùn)輸時間為q(yj)。全部工件在一分批機(jī)器M上加工，這里批容量無限，且同批加工的工件必須是G的一團(tuán)。問題為求一分批排序使任務(wù)的完工時間最小。

這里，Bi為第i 批的工件集（圖G的一個團(tuán)），第i 批的完工時間為運(yùn)輸時間為先來分析一下工件分批情況。由X ={x1,x2,… ,xm}是獨(dú)立集知，頂點(diǎn)xi各占一批(該批中還可能有其相鄰的頂點(diǎn))。記xi在Y中的鄰集為N(xi)，有xi∪N(xi)是一團(tuán)，此團(tuán)或其中部分可做為一批。另外，Y是一團(tuán)，其任一部分均可作為一批，與xi不相鄰的頂點(diǎn)需要單獨(dú)作為一批，即若則必須占一批。下Y′面我們假設(shè)Y′≠?，如此，方案至少包含m+1批。問題的關(guān)鍵是如何把Y的頂點(diǎn)放入到這些批中，可以使目標(biāo)函數(shù)Dmax最小。然后，簡化問題：（1）若存在y ∈N(xi)滿足q(y ) ≤q(x)，則工件y可以分到xi在的批B 中，該批的運(yùn)輸時間q(B ) =q(xi)沒有變化，對目標(biāo)函數(shù)也沒有影響，因此可把這樣的頂點(diǎn)給暫時給刪去。（2）若存在y ∈Y Y′滿足q(y ) ≤q(Y′)，則工件y 可以分到Y(jié)′在的批中，該批的運(yùn)輸時間沒有變化，對目標(biāo)函數(shù)也沒有影響，因此也可以把這樣的頂點(diǎn)給暫時刪去。

證明：此時m+1批可看成m+1個單獨(dú)的工件，從而可轉(zhuǎn)化為單機(jī)排序問題1||Dmax，用熟知的LDT (the longest delivery time first)規(guī)則，就可以得最優(yōu)解。

下面考慮YY′≠?的情況，解決如何將Y Y′的頂點(diǎn)添加到m+1批中去。

命題3：取所有工件中運(yùn)輸時間最大的為v*，即（1）如果v*∈X，不失一般性設(shè)v*=x1，則有最優(yōu)解使{x1}是第一批。（2）如果，則有最優(yōu)解使Y′為第一批。（3）如果記則有最優(yōu)解使v*與及Y′中具有最大運(yùn)輸時間者位于第一批。

Step 3：如果所有的批都已順序，那么終止，輸出最優(yōu)排序

Step 4：從未順序及未分批的所有工件中，挑出運(yùn)輸時間最大的工件v*。（1）若v*∈X，比如v*=xi，則將xi所在的批安排在最前面（未安排順序的批的第一位）。（2）若v*∈Y′，則將Y′所在的批安排在最前面。（3）若v*∈Y~，則從與v*相鄰的頂點(diǎn)及Y′中挑出運(yùn)輸時間最大的，如某個xil或Y′，同時將v*放入它所在的批，將此批排在最前面。令

證明：由命題2及3可知算法的正確性。下面只證明時間復(fù)雜性。

算法開始執(zhí)行時，對所有工件的運(yùn)輸時間q(xi)或q(yj)按照遞減的順序排列，其運(yùn)行時間為O(n logn)。此時得到及Y′按照LDT順序排列，算法以下步驟都以此為基礎(chǔ)。其次，每一次循環(huán)算法都確定出一批順序，所以循環(huán)數(shù)≤k≤n。而每一循環(huán)中的計(jì)算量體現(xiàn)在Step 4的(4．3)，找出與最壞情形需要掃描X 中的所有頂點(diǎn)。故計(jì)算量是O(n)。由此，總計(jì)算復(fù)雜性為

3 結(jié)語

工件帶有相容約束性及運(yùn)輸時間的單機(jī)平行分批排序問題具有很強(qiáng)的實(shí)際應(yīng)用背景，本文對其問題復(fù)雜性進(jìn)行了研究，并對于相容約束為分裂圖時的排序問題給出了時間界為O(n2)的多項(xiàng)式時間算法。

[1]唐國春，張峰，羅守成． 現(xiàn)代排序論[M]．上海：上?？茖W(xué)普及出版社,2003：40-42．

[2]Poon C K and Zhang P．Minimizing makespan in batch machine scheduling[J]．Algorithms, 2004, 39:155-174．

[3]Garey M R and Johnson D S．Computers and Intractability: A Guide to the Theory of NP-Completeness[M]． W． H． Freeman and Company, New York, 1979．

TB114.1

A

1671-0711（2017）08（下）-0226-02

河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目(15A110003)。