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