金世國，張巧利

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

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

金世國1，張巧利2

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

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

相容約束；單機；平行分批

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

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

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

1 問題的復雜性

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

引理1： 團分解問題是NP困難。

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)語

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

[1]唐國春，張峰，羅守成． 現(xiàn)代排序論[M]．上海：上?？茖W普及出版社,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

河南省教育廳科學技術(shù)研究重點項目(15A110003)。