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

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

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