基于隙網(wǎng)絡(luò)的單件車間排序問題研究

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