基于隙網絡的單件車間排序問題研究

單位鈴的排序問題是最普遍、最復雜的排序問題。只有在極個別的例外，我們才能找到有效的算法。1959年，王希德提出了用概整規劃方法解決這個問題，但計算量非常大。例如，當機器數為5和零件數為6時，有105個變量和174個約束條件。1965年，伯克斯和沃爾提出了一種分支邊界法，其效果優于通常的分類方法。隨著問題規模的增加，計算時間更大。ignall和schrgred采用了這種統計結果：在分支邊界法中，三個機器中n個加工工藝的水車間排列所需的計算時間是n（n）m，這只是一個解決方案，也就是說，加工順序的總數是n！m，這里的m是機器總數。規模較大的單件車間排序問題或它的特殊情況——流水車間排序問題,受計算時間或經濟性的制約,求其最優解是不現實的,人們普遍采用啟發式方法求“滿意解”.啟發式方法的效果只能用統計數據比較衡量,對于某一具體的排序問題,無論在計算前或在計算后,都不能確定所求得的結果的滿意程度.這是可以理解的:啟發式方法簡單、方便,但缺乏理論基礎,在找不到實用的優化方法之前,大量的實際排序問題總得要解決,只得使用這類方法了.為此,本文定義了一般單件車間排序問題的極小點或局部最優解:任一工件的所有工序在一個排序中都獲得最優安排.與數學上函數極值點的定義相比,這一排序極值點的定義更為嚴謹.函數極值點只允許其自變量沿一個方向增減,而遍歷一個工件在排序中的加工安排方案本身就屬于NP難題.為此,本文將單件車間排序問題轉化成一種新型的網絡問題,通過對這種網絡的分析和生成,提出了求解這一排序問題極小點的多項式時間算法.1機器上加工和響應面確定與排序問題通常使用的名詞術語一致:n個工件J1,…,Jn在m臺機器M1,…,Mm上加工.一個工件在一臺機器上的加工稱之一道“工序”.工件Ji的工序數為ν(i).用“加工路線”表示工件加工工序先后順序的技術約束,用“加工順序”表示各臺機器上工件加工的先后順序.排序亦即確定加工順序,使給定的目標函數優化.1.1機器上加工的工藝條件所討論的排序問題一般遵循約束:(a)任一工件不能同時在不同的機器上加工;(b)任一工件的上一道工序完成后,即可進入下一道工序所在的機器上加工;(c)一旦工件的某道工序開始加工,必須一直進行到該工序結束;(d)允許工件在工序之間等待,允許機器在工件未到達時閑置;(e)每臺機器同時只能加工一個工件.1.2[1[1]的及其分類用{J}表示以下排序:pi(1?1)?j(1?1)???pi(1?μ(1))?j(1?μ(1))?pi(m?1)?j(m?1)???pi(m?μ(m))?j(m?μ(m))pi(1?1)?j(1?1)???pi(1?μ(1))?j(1?μ(1))?pi(m?1)?j(m?1)???pi(m?μ(m))?j(m?μ(m))Dmax=max{Dr∈[1,m]}其中Dr=μ(r)∑s=1(pi(r?s)?j(r?s)+xr?s)pi(r,s),j(r,s)=Nr,s·δ稱δ為該排序問題的漸變量.若所有的Nr,s之間不存在公約數,則稱δ為該排序問題的最大漸變量.亦即,任一工序都可表示為漸變量δ的整數倍,顯然,Dmax也是δ的整數倍.設某一加工順序{J}的總流程時間為Dmax,漸變量為δ,我們對{J}中的任一工序作如下分類:若pi(r,s),j(r,s)增加δ時,Dmax亦增加δ,則稱pi(r,s),j(r,s)為關鍵工序;若pi(r,s),j(r,s)減少δ時,Dmax亦減少δ,則稱pi(r,s),j(r,s)為單支關鍵工序,簡稱單支工序;若pi(r,s),j(r,s)增加δ時,Dmax增加δ,pi(r,s),j(r,s)減少δ時,Dmax保持不變,則稱pi(r,s),j(r,s)為并支關鍵工序;若pi(r,s),j(r,s)增加δ時,Dmax保持不變,則pi(r,s),j(r,s)為非關鍵工序.2預測的最優安排—極小點和隙作為最優排序,{J}必須具有這樣的性質:對于給定的目標函數,{J}中的任一工件的加工安排是最優的.換言之,從{J}中取出任一工件的全部工序,再任意地插回去,都不可能獲得比Dmax更優的目標值.定義具備以上性質的排序為極小點,其總流程時間為極小值.不具備這一性質的排序也稱之點,但不是極小點.當然,從某一點上抽出的工件愈多,而任意插回去又能滿足這一性質,則該點愈接近于最小點.定理1如果{J}中任一具有單支工序的工件獲得最優安排,則{J}為極小點,反之亦然.證明:根據單支工序的定義,若Ji不含單支工序,則從{J}中抽出Ji后,{J}的目標函數值仍保持不變.另一方面,若{J}為極小點,則{J}中的每一工件都獲得了最優安排,自然包括具有單支工序的工件在內.(證畢)已知{J}中至少包含一個單支工序的工件Ji的全部工序為pi,j(α(1),β(1)),…,pi,j(α(ν(i)),β(ν(i)))pi?j(α(k)?β(k))為Ji的第k道?序?亦即j(α(k),β(k))=k我們用{J}i表示抽出Ji的全部工序后的{J}.若Ji在{J}中的安排不是最優的,則存在另一個點,其目標函數值小于Dmax.基于此,我們取(Dmax-δ)為{J}i的總流程時間,從而定義{J}i的隙yr,s為pi(r,s),j(r,s)開工前或pi(r,μ(r)),j(r,μ(r))完工后機器Mr上的最長閑置時間間隔:yr,s=br,s(s=1)(1)yr,s=br,s-ar,(s-1)-pi(r,s-1),j(r,s-1)(2≤s≤μ(r)-1)(2)yr,s=Dmax-δ-ar,s-pi(r,s),j(r,s)(s=μ(r))(3)根據約束條件(c),處于加工狀態的工序不能中斷,所以求取Ji在{J}i中的最優安排時,Ji的工序僅能插置在{J}i的隙中.對于每一個隙yr,s,用Ar,s和Br,s分別表示其開始時刻和結束時刻,即yr,s=Br,s-Ar,spi,j(α(k),β(k))>yα(k),s我們將pi?j(α(k)?β(k))插置于yα(k)?s時?則{J}i的目標值D(i)max≥Dmax?此時?無論選擇什么方案將Ji的其它?序安排到{J}i?都不可能得到比Dmax更優的目標值.因此?在機器Μα(k)上我們僅考慮大于或等于pi?j(α(k)?β(k))的那些隙∶yα(k),ω(k,1),…,yα(k),ω(k,η(k))Σ(r,s)(k,w):從Ak,w到Ar,s的最短路徑,其取值為pi,k插置yk,w后Ar,s必須后延的最短時間,且Ar,s后延了這一時間后,yr,s仍為可行隙.Σ(k-1,v)(r,s)(k,w):當pi,(k-1)插置yk-1,v時,從Ak,w到Ar,s的最短路徑.Σ(k-1,v)(k-2,u)(r,s)(k,w):當pi,k-1插置yk-1,v且pi,k-2插置yk-2,u時,從Ak,w到Ar,s的最短路徑.3.3節點最短路徑的確定生成網絡就是確定節點間的最短路徑和相鄰路徑及其取值.為此我們需要符號Ω(r,s),k:第k列的節點子集,第k列上存在到節點Ar,s的最短路徑的節點都在該子集中.定理2最短路徑Σ(r,s)(k,w)存在的充分與必要條件為Σ(r?s)(k?w)＜+∞(4)其中Σ(r?s)(k?w)=min{Σ(k-1?v)(r?s)(k?w)|Ak-1?v∈Ω(k?w)?k-1∩Ω(r?s)?k-1}(5)Σ(k-1?v)(r?s)(k?w)=min{Σ(k-1?v)(k-2?u)(r?s)(k?w)|Ak-2?u∈Ω(k-1?v)?k-2∩Ω(k?w)?k-2∩Ω(r?s)?k-2}(6)由以下計算過程確定:A′k?w=Ak?w+Σ(k-2?u)(k?w)(k-1?v)A′r?s=Ar?s+Σ(k-2?u)(r?s)(k-1?v)將pi,k插置yk,w并且取A′k,w為開工時間,我們計算A′r,s在{J}i中的后延時間σ(k-1,v)(k-2,u)(r,s)(k,w).如果Br?s-A′r?s-σ(k-1?v)(k-2?u)(r?s)(k?w)＜pi?r且A′k?w+pi?k＞Br?s-pi?r則Σ(k-1?v)(k-2?u)(r?s)(k?w)=+∞否則Σ(k-1?v)(k-2?u)(r?s)(k?w)=Σ(k-2?u)(r?s)(k-1?v)+σ(k-1?v)(k-2?u)(r?s)(k?w)(7)定義σ(k-1,v)(k-2,u)(r,s)(k,w)為Σ(k-1,v)(k-2,u)(r,s)(k,w)的相鄰路徑.證明:a.必要性.假設Σ(r,s)(k,w)=+∞,則根據式(5),(6)僅有2種可能.可能性1:Ω(k,w),k-1∩Ω(r,s),k-1=?,亦即,當pi,k-1插置第(k-1)列上任何一隙,yk,w和yr,s中至少有一個成為不可行隙.可能性2:Ω(k,w),k-1∩Ω(r,s),k-1≠?,,但對于任一Ak-1,v∈Ω(k,w),k-1∩Ω(r,s),k-1,當pi,k-1插置yk-1,v和pi,k插置yk,w后,yr,s將轉變成不可行隙.無論以上哪種情況出現,都不存在從Ak,w到Ar,s的最短路徑.b.充分性.我們運用數學歸納法證明充分性條件,同時給出隙網絡的生成過程.證k=2時成立.因為A0,0=0,pi,0=0,所以從節點A0,0到它的后續列上的所有節點的最短路徑存在且取值都為0.對于每一v∈[1,η(1)],我們插置pi,1于y1,v,并取pi,1的開工時間為A1,v,從而計算得A1,v到后續列上節點的最短路徑.現在,我們討論從A2,w到Ar,s的最短路徑.設A1?v∈Ω(2?w)?1∩Ω(r?s)?1(3≤r≤ν(i)+1)如圖2所示,當pi,1插置y1,v時,節點A2,w和Ar,s至少后延至A′2?w=A2?w+Σ(2?w)(1?v)A′r?s=Ar?s+Σ(r?s)(1?v)插置pi,2于y2,w且在時刻A′2,w開始加工pi,2,我們計算得A′r,s的后延時間σ(1,v)(r,s)(2,w).因此隙yr,s減小為y′r?s=Br?s-A′r?s-σ(1?v)(r?s)(2?w)若y′r,s<pi,r,則只要pi,1插置于y1,v,就不存在從A2,w到Ar,s的最短路徑,這種情況用Σ(1,v)(r,s)(2,w)=+∞表示.另一方面,若A′2,w+pi,2>Br,s-p′i,r亦即pi,2在y2,w中的最早完工時刻超過p2,r在yr,s中的最遲開工時刻,這種情況也表示為Σ(1,v)(r,s)(2,w)=+∞.除這兩種情況外,我們得到Σ(1?v)(r?s)(2?w)=Σ(r?s)(1?v)+σ(1?v)(r?s)(2?w)因此,取遍每一個節點A1,v∈Ω(2,w),1∩Ω(r,s),1,最終求得Σ(r?s)(2?w)=min{Σ(1?v)(r?s)(2?w)|A1?v∈Ω(2?w)?1∩Ω(r?s)?1}假設(k-1)列成立,證k列成立.設已知pi,k-2插置第(k-2)列上不同的隙中時,第(k-1)列上節點到后續列上節點的全部最短路徑,我們來確定pi,k-1插置第(k-1)列上不同的隙中時,第k列上節點到后續列上節點的全部最短路徑.不失一般性,設Ak-2?α；Ak-2?β∈Ω(k-1?v)?k-2∩Ω(k?w)?k-2∩Ω(r?s)?k-2且Σ(k?w)(k-1?v)=Σ(k-2?α)(r?w)(k-1?v)Σ(r?s)(k-1?v)=Σ(k-2?β)(r?s)(k-1?v)如圖3所示,我們僅需要考慮2種情況.情況1:α=β=u.即僅當pi,k-2插置yk-2,u時,Ak,w和Ar,s同時獲得由pi,k-1插置yk-1,v產生的最短后延時間.因此,pi,k在yk,w中和pi,r在yr,s中的最早開工時間分別為A′k?w=Ak?w+Σ(k?w)(k-1?v)A′r?s=Ar?s+Σ(r?s)(k-1?v)同理可得相鄰路徑σ(k-1,v)(r,s)(k,w)和Σ(k-1?v)(r?s)(k?w)=Σ(k-2?u)(r?s)(k-1?v)+σ(k-1?v)(r?s)(k?w)(8)情況2:α≠β.對于這種情況,我們必須計算第(k-2)列上每一個滿足必要條件的點,從而產生式(6).顯然,式(8)僅是式(6)的特例.(證畢)3.4管插置最優安排定理3對于第r列上任一節點Ar,s,若Ω(r?s)?k=?(9)則Ji在{J}i中不存在最優安排,亦即,Ji在{J}中的加工安排最優.證明:如果Ji在{J}i中存在最優安排,則pi,k必須插置在k列上的某個隙中,而式(9)表明,無論pi,k插置在k列哪個隙,都會導致第r列上無可行隙.(證畢)因此,當這種情況出現時,我們終止{J}i的隙網絡生成,轉而檢查其它具有單支工序的工件在{J}中的安排是否最優.網絡分析的目的在于從網絡上找出Ji在{J}i中的最優安排.我們給出存在這一安排的充要條件:{J}i的隙網絡上第(ν(i)-1)列到ν(i)列至少存在一條最短路徑.必要性是顯而易見的,證充分性則必須找出這一最優安排,其途徑有多條,在此略述.4節點市場條件的確定假設Dmax減少d×δ方可達到某個極小點,且每個工件在每臺機器上僅加工一次,即ν(1)=?=ν(n)=m在此我們取計算一次排序占用的時間為1個單位,現構造最壞情況:(a)每個工件在優化的過程中始終存在單支工序;(b)任意兩個不同列的節點始終存在最短路徑;(c)遍歷所有的n個工件后才使Dmax減少δ;(d){J}i的所有隙都為可行隙.計算2次排序可獲得{J}i的所有隙和隙的開始時刻.根據式(5),(6),最多需n2次排序來確定始于某個節點的全部最短路徑.找出極小點,需要的總計算時間為f(R)=2dmn3其中R表示問題的規模.上式表明f(R)具有多項式時間復雜性.因此,本文提出的極小點算法為有效算法.pi(r,s),j(r,s)不僅表示工件Jj的第j道工序,而且表示該工序的加工時間,它為機器Mr上的第s個加工.現用ar,s表示工序pi(r,s),j(r,s)的最早開工時刻,且若j(r,s)=1,s=1,則ar,s=0.定義機器Mr上開始加工前的空閑時間間隔為由此,我們獲得完成{J}中全部工件加工所需的時間,即總流程時間存在δ>0,對于每一個工序pi(r,s),j(r,s),都有一個正整數Nr,s,使1.3漸變量和關鍵工序與ar,s相應,我們用br,s表示pi(r,s),j(r,s)在{J}中的最遲開工時刻,且若j(r,s)=ν(i),s=μ(r),則br,s=Dr-pi(r,s),j(r,s).給定所有工件的加工時間和加工路線,則Dmax僅取決于如何排序.本文亦取Dmax為目標函數.運用式(1)～(3),并注意到用(Br,s-Ar,s)取代式(2),(3)中的yr,s,于是產生基于上述分析,使{J}i中的所有工序在最早開工時刻加工,我們計算得每個隙的開始時刻Ar,