基于綜合作業(yè)順序圖的混合裝配線平衡問(wèn)題求解

0混合裝配線平衡算法的研究在同一線上，可以在相同的鉆孔線上連續(xù)混合不同類型的產(chǎn)品，結(jié)構(gòu)相似且靠近工藝的產(chǎn)品。如果沒(méi)有大量的倉(cāng)庫(kù)，它可以快速響應(yīng)市場(chǎng)的變化。為合理、有效地使用混合型裝配線,必須解決生產(chǎn)線平衡和生產(chǎn)排序兩個(gè)主要問(wèn)題。生產(chǎn)線平衡問(wèn)題是將產(chǎn)品裝配線上所有作業(yè)任務(wù)適當(dāng)?shù)胤峙涞礁鱾€(gè)工作站中,使各工作站的作業(yè)時(shí)間接近生產(chǎn)節(jié)拍;生產(chǎn)排序問(wèn)題是確定不同品種產(chǎn)品投入生產(chǎn)線的順序。本文主要研究混合裝配線平衡問(wèn)題(Mixed-modelAssemblyLineBalancingProblem,MALB-P)。由于MALB-P需要考慮不同品種之間的相互影響,它比單品種裝配線平衡問(wèn)題(Single-modelAssemblyLineBalancingProblem,SALB-P)更復(fù)雜。隨著混合裝配線在現(xiàn)代工業(yè)生產(chǎn)中的廣泛應(yīng)用,MALB-P越來(lái)越受到國(guó)內(nèi)外學(xué)者的重視。目前,對(duì)MALB-P的研究主要集中在兩個(gè)方面:①對(duì)于給定生產(chǎn)節(jié)拍,最小化工作站數(shù);②對(duì)于給定的工作站數(shù),最小化生產(chǎn)節(jié)拍。前者適用于計(jì)劃期產(chǎn)品需求量確定,通過(guò)適當(dāng)?shù)淖鳂I(yè)分配,最小化生產(chǎn)資源;后者適用于生產(chǎn)資源確定,通過(guò)適當(dāng)?shù)淖鳂I(yè)分配,最小化生產(chǎn)時(shí)間。無(wú)論哪一種情況,要達(dá)到生產(chǎn)線平衡都要解決作業(yè)任務(wù)的分配問(wèn)題,使分配到各個(gè)工作站中的作業(yè)量均衡。但混合裝配線上不同品種產(chǎn)品在所包含的作業(yè)任務(wù)和作業(yè)時(shí)間的差異,給均衡分配作業(yè)任務(wù)帶來(lái)了困難。在目前的研究中,解決這個(gè)問(wèn)題的方法主要通過(guò)如下步驟:首先由每種產(chǎn)品的作業(yè)順序圖得到多品種產(chǎn)品的綜合作業(yè)順序圖,然后按照各品種需求比例,計(jì)算每個(gè)作業(yè)任務(wù)的平均作業(yè)時(shí)間,最后根據(jù)多品種產(chǎn)品的綜合作業(yè)順序圖及每個(gè)作業(yè)任務(wù)的平均作業(yè)時(shí)間,將作業(yè)任務(wù)分配到各工作站。其實(shí)質(zhì)是首先將多品種裝配線等效為單品種裝配線,然后按照求解SALB-P的方法求解MALB-P。對(duì)于多品種混合裝配線,由于不同品種產(chǎn)品所包含的作業(yè)任務(wù)不盡相同,對(duì)同一種作業(yè)任務(wù)不同品種產(chǎn)品的作業(yè)時(shí)間也可能不同,MALB-P的上述解決方案只能實(shí)現(xiàn)生產(chǎn)線上各工作站的平均負(fù)荷平衡,而不能實(shí)現(xiàn)各工作站間瞬時(shí)負(fù)荷的平衡,從而生產(chǎn)線上會(huì)出現(xiàn)等待和阻塞現(xiàn)象,降低了工作站的工作效率。為此,求解MALB-P,不僅需要解決平均負(fù)荷的平衡問(wèn)題,而且需要考慮瞬時(shí)負(fù)荷的平衡問(wèn)題。目前,兼顧平均負(fù)荷平衡與瞬時(shí)負(fù)荷平衡問(wèn)題的研究很少,文獻(xiàn)求解MALB-P,設(shè)計(jì)了工作站數(shù)最少、各工作站間負(fù)荷均衡和工作站內(nèi)不同品種產(chǎn)品的負(fù)荷均衡三個(gè)目標(biāo)函數(shù),從而兼顧了平均負(fù)荷平衡與瞬時(shí)負(fù)荷平衡,但目標(biāo)函數(shù)中的空閑時(shí)間計(jì)算是以平均節(jié)拍為基礎(chǔ)的,難以準(zhǔn)確計(jì)算每種產(chǎn)品在一個(gè)工作站內(nèi)作業(yè)的空閑時(shí)間。文獻(xiàn)對(duì)給定序列的混合品種裝配生產(chǎn)線平衡算法進(jìn)行了研究,其優(yōu)化目標(biāo)是各工作站剩余工作總量最小,解決的是瞬時(shí)負(fù)荷平衡問(wèn)題,但其數(shù)學(xué)模型的建立是基于假設(shè):每個(gè)工作站內(nèi)的工人只負(fù)責(zé)裝配進(jìn)入其工作區(qū)域的工件,當(dāng)一個(gè)工人在某工件離開(kāi)其工作區(qū)域時(shí)未能完成裝配任務(wù),將放棄并轉(zhuǎn)而裝配下一個(gè)工件,而原先工件剩余的工作量假定在進(jìn)入下一個(gè)工作站前已被完成。這種假設(shè)對(duì)實(shí)際問(wèn)題做了相當(dāng)大的簡(jiǎn)化,距實(shí)際實(shí)施還有一定距離。本文從混合裝配線平均負(fù)荷平衡和瞬時(shí)負(fù)荷平衡兩方面對(duì)MALB-P進(jìn)行了研究。首先,根據(jù)計(jì)劃期對(duì)各種產(chǎn)品的需求量確定平均生產(chǎn)節(jié)拍,并計(jì)算最小工作站數(shù),對(duì)MALB-P建立數(shù)學(xué)模型,將MALB-P等效為SALB-P,采用遺傳算法求解,優(yōu)化目標(biāo)是各工作站平均作業(yè)時(shí)間的均方差最小,即使各工作站平均負(fù)荷盡可能接近;然后,對(duì)遺傳算法求解的一組較優(yōu)解,用eM-Plant仿真軟件從裝配線瞬時(shí)負(fù)荷平衡方面進(jìn)行仿真研究;最后,設(shè)計(jì)綜合評(píng)價(jià)指標(biāo),同時(shí)兼顧平均負(fù)荷平衡和瞬時(shí)負(fù)荷平衡,并依據(jù)綜合評(píng)價(jià)指標(biāo)確定最優(yōu)解。1問(wèn)題描述和數(shù)學(xué)模型1.1m種不同品種產(chǎn)品的綜合作業(yè)順序圖MALB-P可描述為:M種產(chǎn)品(稱為一種基型和多種變型的產(chǎn)品)在同一條裝配線上同時(shí)裝配。按照工藝要求,每種產(chǎn)品的裝配所包含的作業(yè)任務(wù)都有一定的先后順序約束,該約束可用作業(yè)順序圖描述。圖1為產(chǎn)品作業(yè)順序圖的一個(gè)例子,圖中a,b,c分別為產(chǎn)品A,B,C的作業(yè)順序圖。由于不同品種產(chǎn)品的作業(yè)任務(wù)不盡相同,其作業(yè)順序圖也不完全相同。為研究M種不同變型產(chǎn)品混合裝配的生產(chǎn)線平衡問(wèn)題,首先將每種產(chǎn)品的作業(yè)順序圖合成為綜合作業(yè)順序圖,圖2為圖1所示三種產(chǎn)品的綜合作業(yè)順序圖。一個(gè)綜合作業(yè)順序圖包含了M種產(chǎn)品裝配的全部N個(gè)作業(yè)任務(wù),對(duì)于同一種作業(yè)任務(wù),不同品種產(chǎn)品的作業(yè)時(shí)間可能不同,當(dāng)一種產(chǎn)品的裝配不包含其中某種作業(yè)任務(wù)時(shí),則將該任務(wù)的作業(yè)時(shí)間視為零。然后,根據(jù)作業(yè)任務(wù)的先后順序約束及一個(gè)最小生產(chǎn)循環(huán)內(nèi)M種產(chǎn)品的平均作業(yè)時(shí)間,將作業(yè)任務(wù)分配到各個(gè)工作站中。分配方案不同,各工作站的作業(yè)時(shí)間也不同,裝配線平衡問(wèn)題是求解一種滿足約束條件的作業(yè)任務(wù)分配方案,使裝配線上各工作站負(fù)荷均衡,減少各工作站的等待或阻塞時(shí)間,提高生產(chǎn)效率。1.2各工作站的負(fù)荷均衡優(yōu)化本文研究的MALB-P屬于MALB-P的第①類問(wèn)題,即對(duì)于給定生產(chǎn)節(jié)拍,最小化工作站數(shù)。首先根據(jù)計(jì)劃期內(nèi)裝配線上總作業(yè)量確定工作站數(shù)的下限,然后在算法運(yùn)行的過(guò)程中,根據(jù)負(fù)荷情況自動(dòng)調(diào)整工作站數(shù)。設(shè)在一個(gè)計(jì)劃期T中,對(duì)第m種產(chǎn)品的需求量為Dm(m=1,2,…,M),則對(duì)M種產(chǎn)品的總需求量D=Μ∑m=1DmD=∑m=1MDm,平均生產(chǎn)節(jié)拍CΤ=Τ/Μ∑m=1DmCT=T/∑m=1MDm。在一個(gè)最小生產(chǎn)循環(huán)中對(duì)第m種產(chǎn)品的需求量為dm,dm=Dm/r,r為D1,D2,…,DM的最大公約數(shù),對(duì)M種產(chǎn)品的總需求量d=Μ∑m=1dmd=∑m=1Mdm。第m種產(chǎn)品第i個(gè)作業(yè)任務(wù)的作業(yè)時(shí)間為tim,則最小工作站數(shù)可由式(1)計(jì)算:Smin=Μ∑m=1dmΝ∑i=1timCΤ?Μ∑m=1dm∑m=1Mdm∑i=1NtimCT?∑m=1Mdm。(1)式(1)計(jì)算結(jié)果是工作站數(shù)的下限,在平衡問(wèn)題求解中可能會(huì)由于作業(yè)任務(wù)在作業(yè)時(shí)間方面的原因,或不同品種產(chǎn)品的作業(yè)時(shí)間差異的影響,導(dǎo)致所需工作站數(shù)大于Smin。例如裝配線上有較多作業(yè)任務(wù)的平均作業(yè)時(shí)間較長(zhǎng),接近平均節(jié)拍。在作業(yè)分配過(guò)程中,若當(dāng)前工作站已分配了部分作業(yè)任務(wù),但作業(yè)時(shí)間遠(yuǎn)不足平均節(jié)拍,按照作業(yè)先后順序約束,當(dāng)前可分配的作業(yè)任務(wù)的平均作業(yè)時(shí)間很長(zhǎng),因此在工作站平均作業(yè)時(shí)間不超過(guò)平均節(jié)拍的約束下,該作業(yè)任務(wù)不能分配到當(dāng)前工作站中,只能分配到下一個(gè)工作站中,致使當(dāng)前工作站的剩余時(shí)間較長(zhǎng),導(dǎo)致裝配線所需工作站數(shù)增加,這時(shí)工作站數(shù)量Smin不能滿足需求,或者雖然按照平均負(fù)荷計(jì)算工作站數(shù)量Smin能夠滿足需求,但由于不同品種產(chǎn)品作業(yè)時(shí)間的差異,使個(gè)別品種產(chǎn)品在某個(gè)(或某些)工作站的作業(yè)時(shí)間超出平均節(jié)拍,而平均節(jié)拍是根據(jù)生產(chǎn)計(jì)劃計(jì)算出的,在這種情況下也需要調(diào)整工作站數(shù)量。因此,本文對(duì)平衡問(wèn)題求解時(shí),隨著作業(yè)分配需求對(duì)工作站數(shù)進(jìn)行調(diào)整,即首先以Smin為基礎(chǔ),在求解過(guò)程中通過(guò)對(duì)各工作站平均負(fù)荷和瞬時(shí)負(fù)荷的檢驗(yàn)來(lái)修正工作站數(shù)。在裝配線運(yùn)行中,各工作站負(fù)荷均衡非常重要,因?yàn)楫?dāng)負(fù)荷較均衡時(shí),各工作站的等待和阻塞時(shí)間較短,工作站的利用率較高,生產(chǎn)效率高;而當(dāng)負(fù)荷不均衡時(shí),各工作站的等待和阻塞時(shí)間較長(zhǎng),工作站的利用率低,生產(chǎn)效率低。因此,本文在最小化工作站數(shù)的同時(shí),設(shè)計(jì)了各工作站負(fù)荷均衡的優(yōu)化目標(biāo)。以各工作站負(fù)荷均衡為優(yōu)化目標(biāo)的MALB-P可描述為:minJ1=√S∑k=1(Μ∑m=1qmΤmk-S∑j=1Μ∑m=1qmΤmjS)2SJ1=∑k=1S??????∑m=1MqmTmk?∑j=1S∑m=1MqmTmjS??????2S????????????????????ue001?ue000ue000ue000ue000ue000。(2)s.t.S∑j=1xij=1,i=1,??Ν∑j=1Sxij=1,i=1,??N,(3)S∑j=1jxij≤S∑l=1lxkl,i,k=1,??Ν,(4)Τmj=Ν∑i=1tmixij,m=1,2,??Μ,j=1,??S,(5)Μ∑m=1qmΤmj≤CΤ,j=1,??S,(6)xij∈{0,1},i=1,…,N,j=1,…,S。(7)式中:qm為第m種產(chǎn)品需求量占所有產(chǎn)品總需求量的比例,即qm=Dm/D(0≤qm≤1,Μ∑m=1qm=1)。目標(biāo)函數(shù)(2)的優(yōu)化目標(biāo)是各工作站負(fù)荷的均方差最小,即各工作站負(fù)荷盡可能接近。約束條件(3)確保每個(gè)作業(yè)任務(wù)只能,且必須安排在一個(gè)工作站中;約束條件(4)確保作業(yè)任務(wù)的安排滿足作業(yè)優(yōu)先順序,其中i是k的緊前任務(wù);約束條件(5)計(jì)算第m種產(chǎn)品在工作站j中的總作業(yè)時(shí)間;約束條件(6)確保每個(gè)工作站的平均負(fù)荷不超過(guò)平均節(jié)拍CT;約束條件(7)給出了xij的取值范圍,當(dāng)?shù)趇個(gè)任務(wù)被安排到第j個(gè)工作站時(shí),xij取值為1,否則取值為0。2裝配線上各工作站的目標(biāo)函數(shù)式(2)～式(7)所描述問(wèn)題的解是一種作業(yè)任務(wù)的分配方案,即將混合裝配線上的作業(yè)任務(wù),在滿足作業(yè)先后順序及各工作站的平均負(fù)荷不超過(guò)平均節(jié)拍的約束條件下,分配到裝配線上各個(gè)工作站中,使目標(biāo)函數(shù)(2)達(dá)到最小。該問(wèn)題是NP難題,因此本文采用遺傳算法對(duì)問(wèn)題進(jìn)行求解。2.1基因串編碼與解碼基因串編碼為一長(zhǎng)為N的數(shù)據(jù)串,每一基因座的序號(hào)對(duì)應(yīng)作業(yè)任務(wù)序號(hào),基因座上的基因值表示該作業(yè)任務(wù)被分配到的工作站的編號(hào),圖3所示為一基因串編碼與解碼的例子。2.2任務(wù)集合及可行解編碼將N個(gè)作業(yè)任務(wù)安排到S個(gè)工作站,需要滿足作業(yè)先后順序及各工作站的平均負(fù)荷不超過(guò)平均節(jié)拍的約束條件。初始種群由一組個(gè)體組成,這些個(gè)體是一組可行解的編碼。產(chǎn)生有效個(gè)體基因碼(其所表示的解是滿足約束條件的可行解)的思路是,首先隨機(jī)產(chǎn)生一個(gè)滿足約束條件的解,然后對(duì)該可行解進(jìn)行編碼。具體步驟如下:步驟1設(shè)個(gè)體計(jì)數(shù)器count=1。步驟2隨機(jī)產(chǎn)生一個(gè)可行解:(1)裝配作業(yè)任務(wù)集合TA={ta1,ta2,…,taN};(2)根據(jù)綜合作業(yè)順序圖,記錄每一任務(wù)tai的緊前任務(wù)數(shù)目ni;(3)根據(jù)綜合作業(yè)順序圖,給出每一任務(wù)taj的后續(xù)任務(wù)集合{bj1,bj2,…,bju},其中u為任務(wù)taj的后續(xù)任務(wù)數(shù)量;(4)設(shè)當(dāng)前工作站為stp=st1,即初始化為第一個(gè)工作站,其中p(p=1,2,…,S)為當(dāng)前工作站編號(hào);(5)設(shè)循環(huán)計(jì)數(shù)器cc=1;(6)從集合TA中隨機(jī)選擇一個(gè)緊前任務(wù)數(shù)為零的任務(wù)安排到當(dāng)前工作站stp中;(7)檢查分配給當(dāng)前工作站的任務(wù)的累計(jì)平均作業(yè)時(shí)間是否超過(guò)上限值(CT),若超過(guò)則取消最后一次的分配,轉(zhuǎn)到(9),否則,轉(zhuǎn)到(8);(8)根據(jù)(2),(3)和(6),修改相關(guān)任務(wù)的緊前節(jié)點(diǎn)數(shù)目;(9)cc=cc+1,如果cc≤ccmax轉(zhuǎn)到(6),否則,轉(zhuǎn)到(10),其中,ccmax為作業(yè)分配循環(huán)次數(shù),NSmax≤ccmax<N,NSmax為裝配線上一個(gè)工作站內(nèi)所分配的作業(yè)任務(wù)數(shù)的最大值;(10)p=p+1,若p<S轉(zhuǎn)到(5),否則轉(zhuǎn)到(11);(11)剩余的任務(wù)安排到工作站sts中。步驟3對(duì)步驟2產(chǎn)生的可行解進(jìn)行基因編碼。步驟4count=count+1,如果count≤popsize,轉(zhuǎn)步驟2,否則轉(zhuǎn)步驟5。步驟5結(jié)束。2.3適應(yīng)性函數(shù)2.3.1-j1-j1因?yàn)槲闹袛?shù)學(xué)模型為最小值問(wèn)題,所以適應(yīng)度函數(shù)設(shè)計(jì)為f(J1)=1-J1μ。(7)式中μ為不小于J1max的常數(shù)。2.3.2遺傳操作期適應(yīng)度尺度變換在遺傳算法運(yùn)行的初期階段,種群中個(gè)體適應(yīng)度相差比較大,可能會(huì)有少數(shù)個(gè)體適應(yīng)度比其他個(gè)體適應(yīng)度高出很多,按照輪盤(pán)賭選擇方法選擇時(shí),這幾個(gè)高適應(yīng)度個(gè)體在下一代種群中將占很高比例,降低了種群中個(gè)體的多樣性,很容易陷入局部最優(yōu)。因此,在遺傳進(jìn)化的初期應(yīng)降低適應(yīng)度尺度,以降低種群中個(gè)體適應(yīng)度的差異程度,從而限制高適應(yīng)度個(gè)體的復(fù)制數(shù)量,維護(hù)種群中個(gè)體的多樣性。在遺傳運(yùn)行的后期階段,種群中個(gè)體的平均適應(yīng)度接近最佳個(gè)體的適應(yīng)度,即種群中個(gè)體適應(yīng)度比較接近,在遺傳操作中,個(gè)體之間幾乎沒(méi)有競(jìng)爭(zhēng)性,影響了對(duì)最優(yōu)解的進(jìn)一步搜索。為此,在遺傳進(jìn)化后期應(yīng)提高適應(yīng)度尺度,放大個(gè)體適應(yīng)度間的差異,以提高個(gè)體之間的競(jìng)爭(zhēng)性。本文采用的適應(yīng)度尺度變換式為:f′(J1)=fav(J1)+y[f(J1)-fav(J1)]。(8)式中:fav(J1)為種群中個(gè)體平均適應(yīng)度;f(J1)為原適應(yīng)度;f′(J1)為尺度變換后的新適應(yīng)度;y為尺度變換系數(shù),是進(jìn)化代數(shù)的函數(shù):y=ymin+ymax-ymingen-1(g-1)。(9)式中:g為進(jìn)化代數(shù);gen為最大進(jìn)化代數(shù);ymin和ymax分別為y的最小值和最大值。從式(9)可以看出,y隨g線性變化,當(dāng)g=1時(shí),y取最小值;當(dāng)g=gen時(shí),y取最大值。采用式(8)和式(9)進(jìn)行適應(yīng)度尺度變換,在遺傳操作初期,適應(yīng)度尺度最小,降低個(gè)體適應(yīng)度的差異,維持種群中個(gè)體的多樣性;隨著進(jìn)化過(guò)程的進(jìn)行,適應(yīng)度尺度呈線性增加;到進(jìn)化后期,適應(yīng)度尺度為最大值,使個(gè)體適應(yīng)度間的差異放大,有利于進(jìn)一步搜索最優(yōu)解。2.4選擇和堅(jiān)持2.4.1適應(yīng)度排序及復(fù)制選擇操作采用最優(yōu)保存策略和輪盤(pán)賭選擇相結(jié)合的方法。首先將種群中的個(gè)體按照適應(yīng)度由高至低排序,然后將適應(yīng)度排在前列的若干個(gè)個(gè)體直接復(fù)制到下一代種群中,其余個(gè)體采用輪盤(pán)賭法選擇。這種選擇方法既保存了種群中的優(yōu)良個(gè)體,又不降低種群中個(gè)體的多樣性。2.4.2作業(yè)順序約束交叉操作是從經(jīng)過(guò)選擇操作的個(gè)體中隨機(jī)選兩個(gè)個(gè)體,按照交叉概率pc進(jìn)行交叉操作。MALB-P對(duì)遺傳算法交叉操作的要求是:任意兩個(gè)個(gè)體基因串經(jīng)交叉操作后產(chǎn)生兩個(gè)有效的個(gè)體基因,即這兩個(gè)基因串解碼結(jié)果是滿足作業(yè)先后順序約束的可行解。采用常規(guī)的單點(diǎn)或多點(diǎn)交叉很難保證所產(chǎn)生的新個(gè)體是有效的。例如,圖4所示為多品種混合裝配的綜合作業(yè)順序圖,圖5所示的兩個(gè)基因串ch1和ch2分別表示兩種不同的作業(yè)分配方案。如果ch1和ch2進(jìn)行單點(diǎn)交叉,則得到ch1′和ch2′,如圖6所示。ch1′和ch2′的解碼結(jié)果如圖7所示,由圖7a可見(jiàn),由于任務(wù)11和15被安排在第一個(gè)工作站內(nèi),不能滿足作業(yè)先后順序約束,故編碼ch1′沒(méi)有實(shí)際意義,是一個(gè)無(wú)效的基因。本文采用交叉后檢驗(yàn)和修正的方法,保證解的有效性,即對(duì)交叉操作所產(chǎn)生的新基因串,按照作業(yè)先后順序約束進(jìn)行有效性檢驗(yàn),并對(duì)無(wú)效基因串進(jìn)行部分作業(yè)任務(wù)的重新分配,將其調(diào)整為有效基因串。例如,對(duì)圖6中的基因串ch1′進(jìn)行調(diào)整,將任務(wù)11調(diào)整到第二個(gè)工作站;將任務(wù)15調(diào)整到第四個(gè)工作站,經(jīng)過(guò)修正的基因串ch1″為有效基因,如圖8所示。2.4.3體基因串上隨機(jī)隨機(jī)選擇多個(gè)基因座上的基因按照pm變異概率進(jìn)行變異操作。首先,在種群中隨機(jī)選擇一個(gè)個(gè)體,然后在該個(gè)體基因串上隨機(jī)選擇兩個(gè)基因座,對(duì)這兩個(gè)基因座上的基因值以概率pm進(jìn)行交換。這種變異操作也可能產(chǎn)生無(wú)效個(gè)體,因此變異操作后,需要對(duì)新個(gè)體進(jìn)行有效性檢驗(yàn),對(duì)于無(wú)效個(gè)體,通過(guò)重新分配部分作業(yè)任務(wù)來(lái)加以修正,使其成為有效個(gè)體。2.4.4顯傳統(tǒng)法參數(shù)的選擇(1)增加個(gè)體多樣性種群大小size表示種群中所含個(gè)體的數(shù)目,size選擇較大時(shí),可增加種群中個(gè)體的多樣性,但算法的運(yùn)行速度較慢;而size選擇較小時(shí),雖然可提高算法的運(yùn)行速度,但降低了種群中個(gè)體的多樣性,容易產(chǎn)生遺傳算法的早熟現(xiàn)象,因此size取40～100較為合適。(2)對(duì)最優(yōu)解的搜索交叉、變異參數(shù)是遺傳操作的重要參數(shù),影響對(duì)最優(yōu)解的搜索性能。當(dāng)交叉、變異概率pc和pm選擇較小時(shí),會(huì)影響到種群中個(gè)體的多樣性,容易陷入局部最優(yōu);而當(dāng)pc和pm選擇較大時(shí),可能會(huì)破壞種群中的優(yōu)良個(gè)體,使種群中平均適應(yīng)度下降,影響對(duì)最優(yōu)解的搜索。因此本文采用變參數(shù)策略,按照參加交叉、變異的個(gè)體適應(yīng)度分三種情況選擇交叉、變異參數(shù):①對(duì)種群中最優(yōu)個(gè)體選擇,交叉、變異概率選為0,即不參加交叉、變異操作,直接復(fù)制到下一代。②對(duì)適應(yīng)度高于種群平均適應(yīng)度的個(gè)體,交叉、變異概率依個(gè)體適應(yīng)度與平均適應(yīng)度差值大小在pc1,pm1與pc2,pm2之間線性變化,其中pc1,pm1為交叉、變異概率的上限值,pc2,pm2為交叉、變異概率的下限值。個(gè)體適應(yīng)度與平均適應(yīng)度的差值越大,說(shuō)明該個(gè)體的適應(yīng)度較高,選擇的交叉、變異概率越低;而個(gè)體適應(yīng)度與平均適應(yīng)度的差值越小,說(shuō)明該個(gè)體的適應(yīng)度相對(duì)較低,選擇的交叉、變異概率越高。③對(duì)適應(yīng)度低于種群平均適應(yīng)度的個(gè)體,選擇較高的交叉、變異概率(pc1和pm1)。3裝配線運(yùn)行仿真研究采用遺傳算法求解MALB-P時(shí),力求分配給各個(gè)工作站的作業(yè)量盡可能接近,但混合裝配線上不同品種產(chǎn)品裝配所包含的作業(yè)任務(wù)和作業(yè)時(shí)間上的差異,使不同品種產(chǎn)品在同一工作站中的作業(yè)時(shí)間可能不同,同一品種產(chǎn)品在不同工作站中的作業(yè)時(shí)間也可能存在差異,以至于裝配線瞬時(shí)負(fù)荷難以平衡。裝配線瞬時(shí)負(fù)荷的不平衡,導(dǎo)致工作站等待和阻塞率增加,利用率降低。而瞬時(shí)負(fù)荷的平衡問(wèn)題很難用數(shù)學(xué)模型描述與求解。為此,本文通過(guò)仿真的方法對(duì)混合裝配線瞬時(shí)負(fù)荷平衡問(wèn)題進(jìn)行研究。采用離散事件系統(tǒng)仿真軟件eM-Plant對(duì)遺傳算法求解的一組較優(yōu)解進(jìn)行仿真研究,每個(gè)解代表一種作業(yè)分配方案,通過(guò)仿真研究,分析每一作業(yè)分配方案下裝配線的瞬時(shí)負(fù)荷平衡情況。圖9為應(yīng)用eM-Plant對(duì)多品種混合裝配線建模的一個(gè)例子,生產(chǎn)線上有workstation1,workstation2,workstation3和workstation4四個(gè)工作站,產(chǎn)品從Entrance流入,從Exit流出。EventController是事件控制器,通過(guò)事件控制器來(lái)控制事件發(fā)生時(shí)刻。ProcTime1,ProcTime2,ProcTime3和ProcTime4分別用于對(duì)上述四個(gè)工作站設(shè)定作業(yè)時(shí)間。每個(gè)產(chǎn)品在一個(gè)工作站中的作業(yè)時(shí)間等于該產(chǎn)品在該工作站中所需完成的全部作業(yè)任務(wù)的作業(yè)時(shí)間總和。由于不同品種產(chǎn)品包含的作業(yè)任務(wù)有所不同,而且對(duì)于相同的作業(yè)任務(wù),不同品種產(chǎn)品的作業(yè)時(shí)間也可能不同。仿真研究就是將第2章遺傳算法的求解結(jié)果在仿真模型中加以實(shí)現(xiàn)。通過(guò)運(yùn)行仿真模型,研究各工作站間瞬態(tài)負(fù)荷的平衡性。具體實(shí)現(xiàn)過(guò)程是:首先,在ProcTimei(i=1,2,3,4)中,對(duì)遺傳算法求解到的任務(wù)分配結(jié)果用Simtalk語(yǔ)言編程,定義分配到workstationi中的任務(wù),以及每個(gè)品種產(chǎn)品所包含的任務(wù)和作業(yè)時(shí)間,以控制每種產(chǎn)品在各個(gè)工作站中的作業(yè)時(shí)間;然后,運(yùn)行仿真模型,用Chart顯示各工作站利用率、等待率和阻塞率等指標(biāo),Chart顯示的仿真結(jié)果如圖10所示。圖10中的柱狀圖,顯示出每個(gè)工作站工作時(shí)間、等待時(shí)間和阻塞時(shí)間的百分率,即利用率、等待率和阻塞率,反映出混合裝配線瞬時(shí)負(fù)荷平衡情況。當(dāng)裝配線瞬時(shí)負(fù)荷不平衡率較高時(shí),工作站就會(huì)產(chǎn)生較長(zhǎng)的等待或阻塞時(shí)間,結(jié)果等待或阻塞率較高,利用率較低。圖10a和圖10b分別表示對(duì)兩種不同的作業(yè)分配方案的仿真結(jié)果,圖10a各工作站利用率平均值高于圖10b,說(shuō)明后者的裝配線瞬時(shí)負(fù)荷平衡率低于前者。以各工作站利用率平均值J2作為評(píng)價(jià)混合裝配線瞬時(shí)負(fù)荷平衡率的一個(gè)指標(biāo),當(dāng)J2較高時(shí),說(shuō)明工作站的阻塞或等待率較低,瞬時(shí)負(fù)荷平衡率較高。式(2)給出的目標(biāo)函數(shù)J1的優(yōu)化結(jié)果使各工作站平均作業(yè)量均衡;評(píng)價(jià)指標(biāo)J2反映了裝配線瞬時(shí)負(fù)荷平衡率,因此綜合優(yōu)化目標(biāo)函數(shù)設(shè)計(jì)為minJ=w1J1+w2(1-J2)。(10)式中w1,w2為權(quán)值。4生產(chǎn)效率較優(yōu)分配模型設(shè)三種產(chǎn)品A,B,C在同一條裝配線上混合裝配,一天(8h或28800s)這三種產(chǎn)品的計(jì)劃產(chǎn)量分別為DA=400,DB=200和DC=300。平均節(jié)拍CΤ=Τ/Μ∑m=1Dm=32s,三種產(chǎn)品的綜合作業(yè)順序圖如圖11所示,每個(gè)任務(wù)的作業(yè)時(shí)間如表1所示。在一個(gè)最小生產(chǎn)循環(huán)中,對(duì)每一種產(chǎn)品的需求量分別為dA=DA/100=4,dB=DB/100=2和dC=DC/100=3;對(duì)每一種產(chǎn)品需求比例分別為qA=4/9,qB=2/9和qC=1/3。用式(1)計(jì)算出工作站數(shù)量Smin=6。采用第3章介紹的遺傳算法,求解的最優(yōu)解如表2所示。從表中看出,各工作站平均負(fù)荷沒(méi)有超過(guò)設(shè)計(jì)的平均節(jié)拍CT,說(shuō)明按照平均負(fù)荷校驗(yàn)工作站數(shù)是滿足要求的,因此求解過(guò)程中工作站數(shù)沒(méi)有發(fā)生變化,即S=Smin=6。將求解結(jié)果輸入到仿真模型中,進(jìn)行瞬時(shí)負(fù)荷的校驗(yàn),發(fā)現(xiàn)由于個(gè)別品種的瞬時(shí)負(fù)荷超過(guò)設(shè)計(jì)節(jié)拍,使裝配線實(shí)際節(jié)拍達(dá)到36.5s,這種生產(chǎn)速率不能滿足生產(chǎn)計(jì)劃要求,需要增加一個(gè)工作站,以縮短裝配線節(jié)拍。將工作站數(shù)調(diào)整為S=7,