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

金世國，張巧利

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

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

金世國1，張巧利2

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

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

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

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

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

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

1 問題的復(fù)雜性

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

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

命題1 ：?jiǎn)栴}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 個(gè)頂點(diǎn)分別對(duì)應(yīng)n 個(gè)有同一工時(shí)p及運(yùn)輸時(shí)間q的工件，同時(shí)記門檻值為Y = Kp+q。此時(shí)，排序問題的判定問題為：是否有平行分批排序π使得Dmax以給定的門檻值作為上界，即Dmax≤Y？如果團(tuán)分解問題有解，也就是存在一整數(shù)k ≤K，使圖G的頂點(diǎn)集V(G)被劃為k 個(gè)不相交的子集且每一子集的導(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 相容約束為分裂圖時(shí)算法

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

這里，Bi為第i 批的工件集（圖G的一個(gè)團(tuán)），第i 批的完工時(shí)間為運(yùn)輸時(shí)間為先來分析一下工件分批情況。由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最小。然后，簡(jiǎn)化問題：（1）若存在y ∈N(xi)滿足q(y ) ≤q(x)，則工件y可以分到xi在的批B 中，該批的運(yùn)輸時(shí)間q(B ) =q(xi)沒有變化，對(duì)目標(biāo)函數(shù)也沒有影響，因此可把這樣的頂點(diǎn)給暫時(shí)給刪去。（2）若存在y ∈Y Y′滿足q(y ) ≤q(Y′)，則工件y 可以分到Y(jié)′在的批中，該批的運(yùn)輸時(shí)間沒有變化，對(duì)目標(biāo)函數(shù)也沒有影響，因此也可以把這樣的頂點(diǎn)給暫時(shí)刪去。

證明：此時(shí)m+1批可看成m+1個(gè)單獨(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)輸時(shí)間最大的為v*，即（1）如果v*∈X，不失一般性設(shè)v*=x1，則有最優(yōu)解使{x1}是第一批。（2）如果，則有最優(yōu)解使Y′為第一批。（3）如果記則有最優(yōu)解使v*與及Y′中具有最大運(yùn)輸時(shí)間者位于第一批。

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

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

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

算法開始執(zhí)行時(shí)，對(duì)所有工件的運(yùn)輸時(shí)間q(xi)或q(yj)按照遞減的順序排列，其運(yùn)行時(shí)間為O(n logn)。此時(shí)得到及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)輸時(shí)間的單機(jī)平行分批排序問題具有很強(qiáng)的實(shí)際應(yīng)用背景，本文對(duì)其問題復(fù)雜性進(jìn)行了研究，并對(duì)于相容約束為分裂圖時(shí)的排序問題給出了時(shí)間界為O(n2)的多項(xiàng)式時(shí)間算法。

[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)。