混合裝配流水線平衡與產(chǎn)品排序?qū)α魉€的交互影響

混合裝配流水線平衡與產(chǎn)品排序?qū)α魉€的交互影響

0混合裝配花線平衡和排序問題生產(chǎn)計劃決策的重要指標之一是makepsan（分類長度）。最小商用車，最大生產(chǎn)率，最小機器和員工的空閑時間，低生產(chǎn)和制造成本。關(guān)于最小化makepsan的研究文獻主要集中在folpen，m-p-mx。文獻中使用不同的方法來最小化folpen。在文獻中，不同的限制下，使用不同的方法來最大化folpen。文獻采用改進的遺傳計算方法，在生產(chǎn)線上配置指紋。文獻介紹了使用混合水線管的示例，并發(fā)現(xiàn)了兩種型號和三種機器的在線分段方法。已經(jīng)檢索到的關(guān)于makespan最小化的研究文獻,如,都是假設(shè)給定流水線上的設(shè)備數(shù)(工作站數(shù))、工件(產(chǎn)品)在機器設(shè)備上(工作站內(nèi))的加工時間(負荷)的前提下來進行的.但是,對于Flowshop,尤其是混合裝配流水線來說,有兩個重要而且相關(guān)的方面:一是作業(yè)任務(wù)的分配,即流水線的平衡問題;另一個就是在工作站及其任務(wù)確定(確定了工作站數(shù)目、工作站內(nèi)的作業(yè)元素、工作站負荷)的情況下,決定產(chǎn)品加工(裝配)順序,即排序問題.流水線的平衡問題是NP-hard,而且產(chǎn)品排序問題也是NP-hard,這兩個方面是緊密相關(guān)的,流水線的平衡問題處于排序問題的上游,已有的Flowshop研究文獻都是優(yōu)化下游排序問題,沒有考慮到上游平衡問題對下游排序問題的影響,多數(shù)的裝配線流水線的研究文獻也是獨立考慮這兩個方面的.一些學(xué)者,如Thomopoulos,Merengo,YeoKeunKim和Miltenburg均意識到了流水線平衡與產(chǎn)品排序的聯(lián)系以及對流水線績效的交互影響,同時研究混合裝配流水線的平衡和排序問題.Thomopoulos研究了直線型流水線的平衡和排序問題,采用的是串行獨立處理的方法,先進行流水線的平衡,然后再進行產(chǎn)品排序,Merengo也是采用串行處理的方法,把平衡優(yōu)化和排序優(yōu)化交替進行.文獻的串行獨立方法的搜索范圍大大小于問題的解空間.Kim和Miltenburg,都是以負荷均衡為目標,采用并行協(xié)同處理的方法來解決混合U型裝配線的平衡和排序問題.Kim采用雙種群協(xié)同進化的優(yōu)化方法來解決,較好地考慮了兩個問題之間的交互影響.Miltenburg采用單一的聯(lián)合種群的進化算法來優(yōu)化,在處理兩個問題之間的交互影響方面存在不足.對于基于時間競爭的企業(yè)來說,對makespan的優(yōu)化,就等于壓縮了供應(yīng)鏈的制造周期,使整個供應(yīng)鏈實現(xiàn)快速響應(yīng),成為企業(yè)的新的競爭優(yōu)勢來源.目前,我們尚沒有發(fā)現(xiàn)對混合裝配流水線最小makespan的優(yōu)化研究.因此,本文采用協(xié)同進化的并行的協(xié)同優(yōu)化方法來研究混合裝配流水線上最小化makespan問題.文章的內(nèi)容是這樣安排的.第一部分介紹混合裝配流水線,并通過實例分析流水線平衡和產(chǎn)品排序?qū)α魉€績效的交互影響;第二部分建立混合裝配流水線優(yōu)化的數(shù)學(xué)模型;第三部分給出了模型的協(xié)同優(yōu)化算法思路,第四部分進行數(shù)值分析并將協(xié)同優(yōu)化和其他優(yōu)化方法進行比較;第五部分給出文章的結(jié)論.1混合花線的平衡與排序隨著JIT運作模式在供應(yīng)鏈的各個環(huán)節(jié)推行,混合流水裝配流水線就成為制造企業(yè)實現(xiàn)快速反應(yīng)市場需求的一種生產(chǎn)組織方式,這種方式實現(xiàn)了多品種小批量,甚至是單件生產(chǎn)的經(jīng)濟模式,混合裝配流水線上的產(chǎn)品一般是規(guī)格和工藝相似的一個產(chǎn)品族,各種產(chǎn)品混合而非成番輪批投產(chǎn),大大增加了生產(chǎn)的靈活性,降低庫存,減少風(fēng)險.豐田、摩托羅拉、神龍(武漢)等國內(nèi)外知名企業(yè)均采用混合裝配流水線,產(chǎn)生了極大的效益,尤其以豐田公司的混流生產(chǎn)聞名世界.混合裝配流水線上makespan優(yōu)化的提法是:在一個計劃期內(nèi),生產(chǎn)一族產(chǎn)品,共有M品種,市場對這族M個品種的總需求為D產(chǎn)品單位,每個品種的需求為Dm(m=1,2,\:,M),Μ∑m=1Dm=D.完成每種產(chǎn)品所需的作業(yè)元素、作業(yè)元素的時間以及作業(yè)元素之間的優(yōu)先關(guān)系預(yù)先給定.要在一定的規(guī)則下將所有的作業(yè)元素分配到流水線上的工作站中,同時確定產(chǎn)品的投產(chǎn)順序,最小化makespan目標.混合裝配流水線的優(yōu)化存在兩個方面的問題,一個是流水線的平衡問題,即在滿足給定的技術(shù)約束(通常用優(yōu)先圖來表示,圖1中(a)-(d))的條件下,把完成產(chǎn)品所需的作業(yè)元素(或任務(wù))分配到工作站中,我們一般給定工作站數(shù)和一個預(yù)定節(jié)拍;另一個就是排序問題,一般采用循環(huán)排序法.假設(shè)g為產(chǎn)品需求Dm(m=1,2,\:,M)的最大公因子,記dm=Dm/g,d=Μ∑m=1dm.把(d1,d2,\:,dM)稱為一個最小比例集.實際的排產(chǎn)中,只對最小比例集中的d個產(chǎn)品排序,稱為一個排產(chǎn)循環(huán).重復(fù)排產(chǎn)循環(huán)g次,就達到了對D個產(chǎn)品排序的目的.循環(huán)排產(chǎn)的好處在于裝配過程中對各種零部件消耗速度均衡,利于實施JIT運作模式.流水線的平衡與排序?qū)α魉€的優(yōu)化目標均有顯著影響,看一個例子.實例在一條混合裝配流水線上生產(chǎn)一族規(guī)格相似的系列產(chǎn)品A、B、C,在某一時間段內(nèi),三種產(chǎn)品的需求分別為1280單位、640單位、1280單位.假設(shè)設(shè)計的生產(chǎn)節(jié)拍為12時間單位,三種產(chǎn)品的優(yōu)先圖分別為圖1(a)、1(b)和1(c),聯(lián)合優(yōu)先圖為圖1(d),作業(yè)元素的時間在圖中的作業(yè)元素的右上角.給出兩個平衡方案和兩個排序方案,則有4種組合,分別對應(yīng)混合流水線的4種組織方法.計算4種方案下流水線的makespan.可以看出,在相同的排序方案下,不同的平衡方案對應(yīng)著不同的目標,如表1中方案1和方案2;同樣,在相同的平衡方案下,不同的排序方案,對應(yīng)著不同的目標,如表1中方案3和方案4.這說明平衡與排序是緊密相關(guān)和交互影響著優(yōu)化的結(jié)果.2算法1:ssk下面我們建立混合裝配流水線最小化makespan的數(shù)學(xué)模型.模型參數(shù):K為流水線上工作站的數(shù)目;C為預(yù)先設(shè)定的流水線的節(jié)拍;n為產(chǎn)品的作業(yè)元素的個數(shù),E為作業(yè)元素的集合,E={1,2,…,n}.任意的i∈E,記Prec(i)是作業(yè)元素i的直接優(yōu)先元素的集合,例如對作業(yè)元素i=7來說,Prec(7)={4,5}.M為流水線上產(chǎn)品的種類;tmi為第m種產(chǎn)品的第i個作業(yè)元素的時間;ˉti為所有M種單位產(chǎn)品的第i個作業(yè)元素的平均時間,ˉti=Μ∑m=1tmiDmΜ∑m=1Dm;dm為最小比例集中第m種產(chǎn)品的數(shù)量,m=1,2,\:,M;d為最小比例集中各種產(chǎn)品數(shù)的和,d=Μ∑m=1dm.決策變量:xik為平衡方案的0-1決策變量,第i個作業(yè)元素分配在第k個工作站中,則xik=1,否則xik=0,i=1,2,\:,n;k=1,2,\:,k.yjm為排序方案的0-1決策變量,排序序列中第j個位置上為型號為m的產(chǎn)品,則yjm=1,否則yjm=0,j=1,2,\:,d;m=1,2,\:,M.pj為排序序列中第j個位置上的產(chǎn)品,顯然,當yjm=1時,pj=m,j=1,2,\:,d;m=1,2,\:,M.目標函數(shù)與中間變量:f為目標函數(shù),這里f=makepan,計算方法在下面介紹.STkm為第m種單位產(chǎn)品在第k個工作站的負荷,計算方法為SΤkm=n∑i=1xiktmi,k=1,2,\:,Κ;m=1,2,\:,Μ.skj為排序序列中第j個產(chǎn)品在第k個工作站中的開始加工時間,j=1,2,\:,d;k=1,2,\:,K.ckj為排序序列中第j個產(chǎn)品在第k個工作站中的結(jié)束加工時間,j=1,2,\:,d;k=1,2,\:,K.混合流水生產(chǎn)系統(tǒng)的優(yōu)化模型為:Οbjective:minf,(1)SubjecttoΚ∑k=1xik=1,?i∈E,(2)xik≤k∑j=1xhj,?i∈E,?h∈Ρrec(i),k=1,2,\:,Κ,(3)n∑i=1xikˉti≤C,k=1,2,\:,Κ,(4)Μ∑m=1yjm=1,j=1,2,\:,d,(5)d∑j=1yjm=dm,m=1,2,\:,Μ.(6)式(1)是要優(yōu)化的目標函數(shù),f=makespan;計算方法如下:排序序列中第一個產(chǎn)品p1在第一個工作站的開始加工時間為0,即s11=0;則排序序列中第一個產(chǎn)品p1在第一個工作站中結(jié)束加工時間為c11=s11+SΤ1p1=SΤ1p1;排序序列中第1個產(chǎn)品p1在第k(k=1,2,\:,K)個工作站的開始加工時間和結(jié)束加工時間分別為sk1=sk-1,1+SΤk-1,p1,k=2,3,\:,Κ,ck1=sk1+SΤ1p1,k=2,3,\:,Κ.排序序列中第j(j=2,3,\:,d)個產(chǎn)品pj在第1個工作站的開始加工和結(jié)束加工時間分別為s1j=s1,j-1+SΤ1,pj-1,j=2,3,\:,d,c1,j=s1j+SΤ1pj,j=2,3,\:,d.排序序列中第j(j=2,3,\:,d)個產(chǎn)品mj在第k(k=1,2,\:,K)個工作站的開始加工時間和結(jié)束加工時間分別為skj=max{ck,j-1,ck-1,j},ckj=skj+SΤkpj,k=2,3,\:,Κ;j=2,3,\:,d.在一個排產(chǎn)循環(huán)中,制造周期為makespan=cΚd.式(2)～(4)是混合裝配線流水線平衡優(yōu)化的約束,其中,式(2)保證一個作業(yè)元素分配在一個而且僅能在一個工作站內(nèi);式(3)表示只有當一個作業(yè)元素的所有(直接)優(yōu)先元素均被分配到工作站內(nèi),則這個作業(yè)元素才能被分配;式(4)保證分配到一個工作站內(nèi)的作業(yè)元素平均作業(yè)時間不超過給定的節(jié)拍;式(5),(6)表示混合裝配流水線排序優(yōu)化的約束,其中,式(5)保證在排序序列的一個位置上有且僅有一個產(chǎn)品;式(6)保證在排序序列的所有位置上某一種產(chǎn)品的數(shù)量恰好為這種產(chǎn)品的需求量.3遺傳算法描述平衡種群和排序種群之間的相互作用協(xié)同進化是將遺傳算法用于求解不同類型而又相互聯(lián)系的優(yōu)化設(shè)計問題時提出的,其基本思想是不同類型問題在各自設(shè)計空間相對獨立的演化進程中,互相影響,協(xié)同地進行.Maher和Poon等在1996年提出“問題-設(shè)計”協(xié)同進化模型,這里,我們把它變更為“平衡-排序”模型應(yīng)用到混合裝配流水線的優(yōu)化上來,其中平衡種群以X表示,排序種群以Y表示,如圖2.圖2闡明了協(xié)同進化過程就是平衡種群和排序種群之間隨著時間的推移相互作用的過程.該模型描述了如下的一個進化機制,進化的兩個種群為平衡種群和排序種群,各個種群的進化都是在另外一個種群的最新一代的指導(dǎo)下進行的,因而稱為協(xié)同進化模型.本文采用遺傳算法分別求解基于共同目標的平衡種群和排序種群的優(yōu)化問題,排序的優(yōu)化是在給定的平衡設(shè)計下進行的,而排序的變化反過來又會影響平衡優(yōu)化的結(jié)果.平衡優(yōu)化和排序優(yōu)化是相互影響的協(xié)同進化的過程.整個協(xié)同進化的過程如為:在第t代確定的平衡種群下X(t),設(shè)計或優(yōu)化排序種群,得到第t代的排序種群Y(t),Y(t)又作為平衡種群進化的適應(yīng)性衡量標準,使得平衡種群由X(t)進化到X(t+1),在平衡種群X(t+1)的指導(dǎo)下,排序種群由Y(t)進化到Y(jié)(t+1),如此協(xié)同進化下去,直到得到滿意的混合流水生產(chǎn)系統(tǒng)的設(shè)計目標.對于遺傳算法的編碼設(shè)計、操作算子設(shè)計,不作詳細說明,可參考文獻.4數(shù)值分析4.1加工流程及分析優(yōu)化第一節(jié)中的實例,在工作站數(shù)K=4,流水線的節(jié)拍C=12,協(xié)同優(yōu)化的結(jié)果為:平衡種群X的最優(yōu)個體有:2→1→4→5→3→7→8→6→91→2→4→3→5→7→8→6→92→1→4→5→3→7→8→6→92→1→4→3→5→7→8→6→9對應(yīng)的排序種群Y的最優(yōu)個體為:C→C→A→A→B四個平衡種群個體對應(yīng)的平衡方案是相同的,譯碼結(jié)果,即平衡方案見表2.將上述的平衡種群的最優(yōu)個體1→2→4→3→5→7→8→6→9與排序種群中的最優(yōu)個體C→C→A→A→B結(jié)合,求解流水線的makespan=76.畫出產(chǎn)品在各個工作站內(nèi)的加工流程圖,如圖3.這里,B產(chǎn)品在第4個工作站中沒有裝配任務(wù)(負荷為0,見表2).由于本例的問題規(guī)模較小,可采用完全列舉法來計算.完全列舉法分成兩個步驟:第一步,列出平衡種群中所有的個體(這里共有103個)和排序種群中的所有個體(這里共有30個);第二步,將平衡種群中的個體與排序種群的個體一一組合,共有103×30=3090種組合,計算每一種組合下的makespan值,選出最優(yōu)解,完全列舉法得到的結(jié)果與協(xié)同優(yōu)化結(jié)果是一致的.進一步地,在這里我們采用串行獨立優(yōu)化方法來最小化makespan,這種方法也是分兩步進行,第一步先進行流水線的平衡,優(yōu)化的目標為流水線的均衡指數(shù)SI,其中在得到流水線平衡問題優(yōu)化解的前提下,再進行第二步的產(chǎn)品排序優(yōu)化.串行獨立優(yōu)化方法第一步得到的流水線平衡問題的解為2→5→1→3→4→7→8→6→9.在這個平衡方案下,求解產(chǎn)品排序問題,得到產(chǎn)品排序問題的解為C→C→A→A→B,這時,混合裝配流水線的makespan=80.需要強調(diào)說明的是,串行獨立優(yōu)化算法僅是一種局部優(yōu)化方法,沒有考慮流水線平衡和排序兩個問題的交互影響,獨立考慮這兩個問題割裂了它們的內(nèi)在聯(lián)系,縮小了問題的解空間,難以搜索到“最匹配”的一對平衡種群的個體和排序種群的個體.在問題規(guī)模較小,列舉法可行前提下,我們在每一步的優(yōu)化中采用完全列舉法,同樣不能得到最優(yōu)解makespan=76.說明了即使有無窮的計算時間,串行獨立優(yōu)化方法本身存在著一種難以逾越的局限性,一般情況是不能得到全局最優(yōu)解的.而并行協(xié)同優(yōu)化方法由于考慮了兩個問題之間的聯(lián)系,是一種全局優(yōu)化的搜索方法.只要有充分多的計算機時,就能夠搜尋到最匹配的兩個個體,得到全局最優(yōu)的優(yōu)化結(jié)果.4.2產(chǎn)品排序優(yōu)化下面我們給出三種算法的比較分析.第一種算法為完全列舉法,第二種算法為串行獨立優(yōu)化方法,第三種算法為協(xié)同優(yōu)化算法.其中,當問題的規(guī)模較大時,完全列舉法耗時大,不可行,僅對小規(guī)模的問題使用;對于串行獨立優(yōu)化方法,采用進化算法,先對指標SI進行平衡優(yōu)化,在獲得平衡優(yōu)化結(jié)果的基礎(chǔ)上,進行產(chǎn)品排序的優(yōu)化.協(xié)同優(yōu)化方法采用協(xié)同進化算法,并行協(xié)同