??
生產(chǎn)調(diào)度是生產(chǎn)管理的核心內(nèi)容和關(guān)鍵技術(shù),其任務(wù)是在企業(yè)有限的資源約束下,確定工件在相關(guān)設(shè)備上的加工順序和加工時間,以保證所選定的生產(chǎn)目標(biāo)最優(yōu)。系統(tǒng)、全面、合理的生產(chǎn)調(diào)度方案不僅有助于企業(yè)提高綜合管理水平,而且可為之帶來顯著的經(jīng)濟效益[1-2]。
表面處理是包括電鍍、化學(xué)鍍、表面氧化等多種類型的表面加工技術(shù)。傳統(tǒng)的表面處理生產(chǎn)線根據(jù)經(jīng)驗安排生產(chǎn)計劃,在已有的生產(chǎn)計劃和加工工藝條件下采用幾何規(guī)劃法繪制載料小車運動流程圖來安排吊運任務(wù)[3-4],以防止設(shè)備任務(wù)沖突。該方法工作量大,而且不能優(yōu)化生產(chǎn)周期。
本文根據(jù)某廠的自動化集成電鍍生產(chǎn)線實際工況,在滿足設(shè)定的加工工藝參數(shù)和加工設(shè)備不沖突的約束下,利用遺傳算法(genetic algorithms,GA)與模擬退火算法(simulated annealing, SA)的優(yōu)勢,采用遺傳模擬退火算法(genetic simulated al-gorithms,GSA)排定生產(chǎn)線作業(yè)計劃[5-10],求解各批工件在相應(yīng)設(shè)備上的加工任務(wù)。
1·問題描述
在電鍍生產(chǎn)中,不同品種的電鍍種類可共用某些設(shè)備,比如前處理和一些后處理工藝等,因此在電鍍生產(chǎn)線可以集成某些具有部分相同工藝的電鍍種類,而不同產(chǎn)品的工序可能不同。但在生產(chǎn)線設(shè)計中根據(jù)工序集中的原則排列設(shè)備,使產(chǎn)品的加工工序方向一致。在某些對于加工時間嚴(yán)格控制的表面處理操作中,生產(chǎn)工藝要求中間產(chǎn)物在上一設(shè)備處理完畢后,立即轉(zhuǎn)移到下一設(shè)備中加工,不能延誤,以免破壞電鍍膜,因此,該生產(chǎn)線采用了零等待(zerowaiting, ZW)方式。在生產(chǎn)線中,為了提高生產(chǎn)效率,在部分關(guān)鍵加工工位設(shè)有若干平行設(shè)備單元,如設(shè)備EL具有a個平行單元。圖1為該生產(chǎn)過程示意圖。
由圖1可知該電鍍生產(chǎn)線是流水線生產(chǎn),可簡化為Flow Shop調(diào)度問題:N批工件在M個設(shè)備單元的流水加工過程。每批工件在各個設(shè)備上的加工順序相同;每批工件在每個設(shè)備單元上只加工1次;在某一時刻每個設(shè)備單元只加工1批產(chǎn)品,每批產(chǎn)品只在一個設(shè)備單元上加工;各批工件在各臺設(shè)備上的加工時間和準(zhǔn)備時間已知;要求得到某種調(diào)度方案使得某項指標(biāo)最優(yōu)[2]。
設(shè)N批產(chǎn)品的加工序列為P={P1,P2,…,Pn};M個設(shè)備單元的序列為E={E1,E2,…,EL,…,EM};第i批被加工的產(chǎn)品在第j個設(shè)備上需要的加工時間為T(i,j);產(chǎn)品Pi(i=1,2,…,N)的第1道加工開始時間為S(Pi,E0);產(chǎn)品Pi在第k臺設(shè)備的加工時間為T(Pi, k), i=1,2,…,N, k=1,2,…,M;加工準(zhǔn)備時間為A(Pi,k);加工開始時間記為S(Pi,k);加工完成時間記為C(Pi,k)。調(diào)度目標(biāo)是確定產(chǎn)品的最優(yōu)加工序列P={P1,P2,…,Pn},并求解產(chǎn)品Pi的在各個加工設(shè)備單元的加工開始時間S(Pi,k)和結(jié)束時間C(Pi,k),使得總加工完成時間即MakeSpan最小。
2·數(shù)學(xué)模型的建立
2.1虛擬工位的引入
在加工工藝路線中引入虛擬工位[11],即當(dāng)產(chǎn)品不在某一設(shè)備上加工時,設(shè)產(chǎn)品在該設(shè)備的加工時間為0,其輔助時間也為0。這樣得出每批產(chǎn)品的虛擬加工工序相同,又可以反映生產(chǎn)工序設(shè)置的實際情況,同時方便數(shù)學(xué)模型的建立。設(shè)產(chǎn)品Pi在設(shè)備Ej不加工,則應(yīng)該滿足。
2.2約束條件的建立
2.2.1 加工開始時間和結(jié)束時間的約束
對于電鍍產(chǎn)品的加工過程,如果給定任一批次產(chǎn)品Pi(i=1.2,…,N)的第1道加工工序的開始時間S(Pi,0)、各個工位的加工時間T(Pi,k)和加工準(zhǔn)備時間A (Pi, k) (k=1,2,…,M ),當(dāng)T(Pi,k)=0時,表示產(chǎn)品Pi在第k個工位上的加工時間為0,即不需要在該工位加工,則Pi在各個設(shè)備的加工完成時間也就確定了,即
工件在加工前的輔助時間A(Pi,k)主要是指載料小車將該批從上一槽位提取上升到高位,停止一段時間滴去依附在工件上的水和藥液以減少藥液交叉污染后行走到下一個工位,然后放置在夾具上的時間。提取、滴水和放置過程固定,行走時間根據(jù)需要加工的下移工位與當(dāng)前工位的距離來計算的。根據(jù)生產(chǎn)實際情況,上升時間、下降時間和滴水時間各為5 s,基本行走世間為6 s,每多移動一個工位增加1 s。虛擬工位的輔助時間為0,非虛擬工位的輔助時間為：
2. 2. 2 加工工序的約束
為了計算一個確定產(chǎn)品加工序列P中各批工件的加工開始時間,將生產(chǎn)線劃分為2類:即不具有平行設(shè)備單元的生產(chǎn)線段和具有平行設(shè)備單元的生產(chǎn)線段。
當(dāng)生產(chǎn)線不存在平行工位的時候,為避免設(shè)備的任務(wù)重疊,即在某一工位,前一個加工任務(wù)沒有完成時后一個加工任務(wù)已經(jīng)到來,文獻[12]提出如下的約束條件:
2.2.3 平行設(shè)備單元的約束
在產(chǎn)品序列P下,當(dāng)產(chǎn)品Pi加工到具有平行設(shè)備單元工位的時候,如果保證產(chǎn)品在該工位不發(fā)生設(shè)備任務(wù)沖突,則必須滿足在當(dāng)前時間下,該工位至少有一個平行設(shè)備單元空閑,即Pi的加工開始時間至少應(yīng)大于在Pi之前加工的、在工位L的加工時間不為0且與Pi最相鄰的a個工件加工完成時間的最小值,即:
2.2.4 生產(chǎn)周期的計算
若給定產(chǎn)品加工序列P=( P1,P2,…,PN),采用一種離散-回縮策略計算其MakeSpan,即在Gantt圖(圖2)上已知Pi的S(Pi,E0),離散Pj的S(Pj,E0)一個足夠大的值能使任何一臺設(shè)備的任務(wù)都不會重疊,然后開始回縮S(Pj,E0)到極限位置,即剛好不發(fā)生設(shè)備任務(wù)重疊位置。離散的時間可選擇為Pi在單個加工單元上的最大加工時間。這種離散-回縮策略能夠有效避免設(shè)備任務(wù)沖突,計算出總生產(chǎn)完成時間。生產(chǎn)線作業(yè)計劃的優(yōu)化排序可采用遺傳模擬退火算法求解出。程序設(shè)計模塊如圖3所示。
2. 3數(shù)學(xué)模型的建立
以最大流程時間MakeSpan最小為調(diào)度指標(biāo),則具有若干平行單元的零等待順序多目的電鍍自動化集成生產(chǎn)線生產(chǎn)優(yōu)化調(diào)度的數(shù)學(xué)模型可表達如下:
3·生產(chǎn)線作業(yè)計劃的優(yōu)化
3. 1 優(yōu)化算法的選擇
遺傳算法[5-10]因其高度的并行處理能力和全局搜索能力而被廣泛地應(yīng)用于諸多領(lǐng)域。理論上遺傳算法依“概率1”收斂于問題的最優(yōu)解,然而實踐應(yīng)用中,遺傳算法會出現(xiàn)過早收斂現(xiàn)象、局部尋優(yōu)能力較差等不足[5]。模擬退火具有較強的局部尋優(yōu)能力,它依據(jù)Metropolis準(zhǔn)則接受新解,能使搜索過程避免陷入局部最優(yōu)解,但把握整個搜索過程的能力不夠,不便于使搜索過程進入最有希望的搜索區(qū)域,從而使得模擬退火的運算效率不高[5]。
針對遺傳算法和模擬退火算法存在的問題,本文選擇一種基于遺傳算法和模擬退火算法的遺傳模擬退火算法。在算法中采用基于工件加工順序的編碼,通過遺傳模擬退火算法搜索解空間,找出一個最優(yōu)的工件加工序列以使MakeSpan最小,其程序流程如圖4所示。
由圖3可知,該混合策略本質(zhì)上是一個2層并行搜索結(jié)構(gòu)。內(nèi)部層次上,混合算法在各溫度下串行的依次進行SA和GA搜索,是一種2層串行結(jié)構(gòu),其中SA的初始解來自GA的進化結(jié)果,SA經(jīng)Metropolis抽樣過程得到的解又成為GA進一步進化的父代種群。外部層次上,GA提供了并行搜索結(jié)構(gòu),使SA轉(zhuǎn)化成為并行SA算法,因此混合算法始終進行種群并行優(yōu)化。通過退溫歷程(即初溫、退溫函數(shù)、抽樣次數(shù))控制混合策略的搜索行為。遺傳模擬退火算法在溫度較高時表現(xiàn)出較強的概率突跳性,體現(xiàn)為對種群的“粗搜索”,溫度較低時演化為趨化性局部搜索算法,體現(xiàn)為對種群的“細(xì)搜索”。這種混合不僅是算法結(jié)構(gòu)上的結(jié)合,而且是搜索機制和進化思想上的相互補充,為較好解決復(fù)雜優(yōu)化問題提供了有利的途徑。
3. 2 GSA算法的設(shè)計
1)初始化控制參數(shù),設(shè)置種群規(guī)模popsize、交叉概率pc、變異概率pm,初始化遺傳代數(shù)計數(shù)器gen=0,初始化種群個體計數(shù)器pop=2。
2)初始化種群P(gen),采用基于工件的編碼,隨機產(chǎn)生初始加工序列;計算初始種群的適應(yīng)度值fP1,fP2,…,fPM。由于調(diào)度的目標(biāo)是求最大流程時間的最小值,所以適應(yīng)度函數(shù)形式如式(9)所示[13]:
f(x)=MakeSpan。為了減小程序運行中的舍入誤差,取c=0,k=10 000。
3)設(shè)定初溫T0。初溫選擇的主要思想是為了平穩(wěn)分布中每一狀態(tài)的概率相等,這樣容易估計一個值為T0=kδ,k充分大,δ=max{f|c∈D}-min{f|c∈D},其中D為狀態(tài)空間。可令δ為初始化種群中個體間MakeSpan最大值和最小值之差。
4)對現(xiàn)有種群采用如下操作,直至產(chǎn)生下一代新的種群:
①從父代路徑中選擇復(fù)制子代。PS(gen)←select[P(gen)]。本算法采用輪盤賭選擇法,同時將父代最佳個體直接復(fù)制給子代。
②進行子代路徑交叉操作。根據(jù)交叉概率pc由PS(gen)中第i個個體PSi(gen)和第j個個體PSj(gen)交叉得到新個體Pci(gen)和Pcj(gen),并計算Pci(gen)和Pcj(gen)的適應(yīng)度值。
③采用Metropolis機制確定的接受概率p來確定是接受還是拒絕新個體Pmi(gen)和Pmj(gen)。
④進行子代路徑變異操作。根據(jù)變異概率pm由Pc(gen)中第i個個體Pci(gen)和第j個個體Pcj(gen)變異得到新個體Pmi(gen)和Pmj(gen),計算Pmi(gen)和Pmj(gen)的適應(yīng)度值,并采用Metropolis機制確定是否接收新個體。
⑤判斷子代是否已經(jīng)生成完畢,即pop是否達到popsize。若不等于,則: P (gen+ 1)=Pm(gen),pop=pop+2;轉(zhuǎn)步驟①;若等于則轉(zhuǎn)步驟④。
5)算法終止條件判斷,若不滿足,則P(gen)=Pm(gen),pop=2,按降溫表更新溫度參數(shù)T,轉(zhuǎn)步驟4);若滿足,則停止計算,輸出最優(yōu)解。采用基于不改變規(guī)則的控制法和溫度控制法,即當(dāng)一定迭代次數(shù)內(nèi)沒有改變最優(yōu)解或者當(dāng)前溫度低于設(shè)定溫度時,就認(rèn)為達到算法終止條件,停止循環(huán),輸出計算結(jié)果。
4·仿真實驗分析
在某廠家的表面處理車間排列2條自動化生產(chǎn)線,各有21個加工設(shè)備單元,其編號為101~121, 201~221,其中103酸鋅鍍鋅和217氰化鍍鎘有3個平行設(shè)備單元,每條生產(chǎn)線上各有1臺自動載料小車轉(zhuǎn)運工件,采用1個地軌車在生產(chǎn)線1和生產(chǎn)線2之間轉(zhuǎn)運工件。應(yīng)用上述調(diào)度算法,采用C++Builder開發(fā)了生產(chǎn)調(diào)度系統(tǒng),并嵌入其自動化生產(chǎn)線的控制程序中。
根據(jù)實際的加工工藝,對該算法進行仿真。當(dāng)隨機選擇10批產(chǎn)品和20批產(chǎn)品,分別采用SA和GSA計算10次,其計算結(jié)果如下: GA交叉概率為0·9,變異概率為0. 03,種群數(shù)量為20,根據(jù)產(chǎn)品批次選擇不同的遺傳運行次數(shù)Run; GSA參數(shù)為退火的初溫為2* (Max_MakeSpan-Min _MakeSpan),退火的速度為0. 9,最大運行次數(shù)為200,交叉概率為0·9,變異概率為0. 15,種群數(shù)量為20,當(dāng)連續(xù)30代其最優(yōu)解沒有發(fā)生變化時退出該循環(huán)。
5·結(jié)束語
本文分析了自動化集成電鍍生產(chǎn)線的生產(chǎn)調(diào)度優(yōu)化問題,在實際加工工序的基礎(chǔ)上引入虛擬工位將之轉(zhuǎn)化為改進的Flow Shop問題,在設(shè)備加工任務(wù)不能重疊和工件加工零等待的情況下,考慮了各批工件在不同工位間的加工輔助條件,分析了生產(chǎn)線的加工約束條件,采用離散-回縮策略求解在一定的工件加工順序下的總加工完成時間以及在各個設(shè)備上的加工時間,給出了生產(chǎn)調(diào)度的數(shù)學(xué)模型。對遺傳算法和模擬退火算法的有機結(jié)合,構(gòu)造了一種遺傳退火混合算法。該算法采用了基于工作的編碼,因而保證了遺傳進程中生成個體的可行性,有效地解決了工件機器順序的約束限制。根據(jù)生產(chǎn)線的實際加工情況,對算法進行了測試,結(jié)果表明,該算法具有良好的收斂性和魯棒性。實踐表明,該調(diào)度模塊能夠提高生產(chǎn)線的加工質(zhì)量,保證生產(chǎn)線的安全,提高生產(chǎn)效率。
