童 昕，張 亮,張 安，陳 永，陳光亭
(1.杭州電子科技大學(xué)理學(xué)院，浙江 杭州 310018；
2.浙江水利水電學(xué)院信息工程學(xué)院，浙江 杭州 310018)
排序最初的應用來(lái)源于工業(yè)生產(chǎn)，習慣上將可用的資源稱(chēng)之為機器，需要完成的任務(wù)稱(chēng)為工件。排序主要研究如何有效利用資源，在限定條件下完成若干任務(wù)，使收益最大化。帶沖突約束的排序問(wèn)題起源于資源受限，假設每個(gè)工件在加工過(guò)程中對某些資源有特定需求，而資源總量有限，當一些工件對某種資源的總需求超過(guò)供應時(shí)，就會(huì )發(fā)生沖突[1]。沖突關(guān)系可以用一般圖來(lái)刻畫(huà)，稱(chēng)為沖突圖，圖中邊的2個(gè)端點(diǎn)對應加工窗口不能重疊的2個(gè)工件。沖突圖的補圖稱(chēng)為許可圖，許可圖中邊的2個(gè)端點(diǎn)對應加工窗口可以重疊的2個(gè)工件。因此，沖突圖約束的排序與對應許可圖約束的排序是等價(jià)的。對于最小化時(shí)間表長(cháng)即最小化最大完工時(shí)間的平行機排序問(wèn)題，Baker等[2]證明了當機器數m≥3時(shí)，單位工件的情形是強NP-難的。對于m=2，單位工件的情形等價(jià)于在許可圖中尋找最大基數匹配問(wèn)題，因此是多項式時(shí)間可解的；
對于工件的加工時(shí)間pj∈{1,2}的情形，Even等[1]提出一種基于最大匹配的多項式時(shí)間最優(yōu)算法。
對于工件具有釋放時(shí)間的排序，Bendraouche等[3]證明了以下特殊情形已經(jīng)是強NP-難的：許可圖為二部圖G=(N1∪N2,E)，且N1中只含有加工時(shí)間為2釋放時(shí)間為0的工件，N2含有加工時(shí)間為1釋放時(shí)間為0和加工時(shí)間為2釋放時(shí)間為r的工件；
他們[4]還將這一強NP-難結論從二部圖推廣至一類(lèi)更廣泛的許可圖情形，即當N1是一個(gè)獨立集、N2的誘導子圖是完全圖、二部圖等結構的情形。
定義[5]給定圖G=(V,E)，若邊集M?E中任意2條邊在G中均不相鄰，則稱(chēng)M為G的1個(gè)匹配。對于賦權圖，定義匹配M的權為M中所有邊的權之和。賦權圖G的所有匹配中，權最大的匹配稱(chēng)為最大權匹配。
針對P2|G=(N1∪N2,E),N1={20},N2={10,2r}|Cmax問(wèn)題，本文設計了一種基于最大權匹配的近似算法。首先，對二部圖G中的邊進(jìn)行賦權，任意邊e=(Js,Jt)∈E，邊的權重me=min{ps,pt}；
然后，調用文獻[6]提出的KM算法，找到G的最大權匹配M，M中含有(20,10)和(20,2r)這2種邊；
最后，先加工匹配M中的邊(20,10)對應的頂點(diǎn)工件以及孤立工件20和10，保證匹配邊對應的工件以及2類(lèi)孤立工件，兩兩之間無(wú)重疊。若加工完這些工件未到r時(shí)刻，則匹配M中的邊(20,2r)以及剩余孤立工件2r從r時(shí)刻開(kāi)始無(wú)空閑加工；
若加工完這些工件達到或超過(guò)r時(shí)刻，則接著(zhù)加工匹配M中的邊(20,2r)以及剩余孤立工件2r。算法產(chǎn)生的排序分為5種結構，如圖1所示。其中結構a表示1個(gè)20工件和1個(gè)10工件在2臺機器上同時(shí)進(jìn)行加工；
結構c表示1個(gè)20工件在1臺機器上單獨加工；
結構d表示1個(gè)10工件在1臺機器上單獨加工；
結構e表示1個(gè)20工件和1個(gè)2r工件在2臺機器上同時(shí)進(jìn)行加工；
結構f表示1個(gè)2r工件在1臺機器上單獨加工。在不引起歧義時(shí)，a,c,d,e,f也表示各個(gè)結構的數量，記算法所產(chǎn)生排序的最大完工時(shí)間為Cmax。
圖1 算法產(chǎn)生的排序的5種結構
根據最優(yōu)排序中是否存長(cháng)鏈結構，分為以下2種情形。
情形1當不存在長(cháng)鏈時(shí)，最優(yōu)排序的結構有6種，如圖2所示。結構a*表示1個(gè)20工件和1個(gè)10工件在2臺機器上同時(shí)進(jìn)行加工；
結構b*表示1個(gè)20工件和2個(gè)10工件在2臺機器上同時(shí)進(jìn)行加工；
結構c*表示1個(gè)20工件在1臺機器上單獨加工；
結構d*表示1個(gè)10工件在1臺機器上單獨加工；
結構e*表示1個(gè)20工件和1個(gè)2r工件在2臺機器上同時(shí)進(jìn)行加工；
結構f*表示1個(gè)2r工件在1臺機器上單獨加工。
圖2 無(wú)長(cháng)鏈時(shí)，最優(yōu)排序的6種結構
從圖2可以看出，算法所產(chǎn)生排序的最大完工時(shí)間
證明算法產(chǎn)生的排序與最優(yōu)排序中20,2r,10這3種工件的數目相同，則有：
a+c+e=a*+b*+c*+e*
(1)
e+f=e*+f*
(2)
a+d=a*+2b*+d*
(3)
將式(1)×2+式(2)×2+式(3)，可得：
3a+2c+d+4e+2f=3a*+4b*+2c*+d*+4e*+2f*
(4)
算法產(chǎn)生的排序中匹配的權重為a+2e，此情形下最優(yōu)排序匹配的權重為a*+b*+2e*，則有：
a+2e≥a*+b*+2e*
(5)
由式(4)和式(5)，可得：
證畢。
圖3 最優(yōu)排序有長(cháng)鏈時(shí)的(k+6)種結構
引理2當最優(yōu)解結構滿(mǎn)足情形2時(shí)，若進(jìn)一步有2(a*+b*+c*)+d* 證明用反證法證明。假設最優(yōu)排序中所有長(cháng)鏈都在r時(shí)刻之后開(kāi)始加工，由2(a*+b*+c*)+d* 引理3當最優(yōu)解結構符合情形2時(shí)，必有2(a*+b*+c*)+d*≥r-2。 證明用反證法證明。假設2(a*+b*+c*)+d*≤r-3，按圖4對最優(yōu)排序進(jìn)行調整，從中可以看出，長(cháng)鏈結構使得最大完工時(shí)間減少了1個(gè)單位時(shí)間，這與最優(yōu)排序矛盾。證畢。 圖4 最優(yōu)排序調整過(guò)程 圖5 最優(yōu)排序再次調整過(guò)程 情形2中，若最優(yōu)排序的結構滿(mǎn)足2(a*+b*+c*)+d*≥r-1，引理4顯然成立。證畢。 證明算法產(chǎn)生的排序與最優(yōu)排序中20,2r,10這3種工件的數目相同，則有： (6) (7) (8) 由式(6)×2+(7)×2+(8)可得： (9) (10) 由式(9)和式(10)，可得： 證畢。 由引理1和引理5得出如下結論。 通過(guò)1個(gè)例子來(lái)驗證算法的界是緊的。假設工件集N={20,10,10}，許可圖G和算法得到的排序以及最優(yōu)排序如圖6所示。 圖6 緊例的許可圖、算法排序及最優(yōu)排序
