多人共站裝配線2025作業(yè)分配方案優(yōu)化

多人共站裝配線2025作業(yè)分配方案優(yōu)化

安裝過程平衡（albp）是制造領(lǐng)域的一個重要問題，直接關(guān)系到安裝效率和生產(chǎn)效率。同時，albp是典型的非模型優(yōu)化問題。因此,對ALBP的研究具有重要意義。傳統(tǒng)ALBP假設(shè)每個工作站分配一個工人進行操作,適用于自動化程度較高的裝配線。然而手工或半手工生產(chǎn)的產(chǎn)品,往往因其體積較小,同一工作站內(nèi)可能由幾名工人同時獨立地對各自負責(zé)的在制品進行一系列相同的作業(yè),之后將操作完成的在制品通過傳送裝置送至下一工作站。相比單人工作站的裝配線,多人共站裝配線可有效平衡工作站之間工作負荷,提高工時的使用效率;提高裝配線的可靠性,減小斷線率。相比于ALBP,多人共站裝配線平衡問題(Multi-MannedAssemblyLineBalancingProblem,MM-ALBP)不僅考慮作業(yè)的分配,而且考慮工人的分配,增加了問題求解的難度。按照傳統(tǒng)的ABLP分類方法,將MM-ALBP分為兩類:第一類(MM-ALBPI)是給定節(jié)拍時間(CycleTime,CT),最小化工人數(shù);第二類(MM-ALBPII)是給定工人數(shù),最小化節(jié)拍時間。目前,對MM-ALBP的研究相對較少,Simaria和Vilarinho將工作站負荷達到最小工位時間作為引入并行工作站的標(biāo)準(zhǔn),求解MM-ALBP。Bukchin和Rubinovitz根據(jù)并行操作成本的不同情形,構(gòu)建了以最小化總成本為優(yōu)化目標(biāo)的MM-ALBPI模型,并將人員分配問題轉(zhuǎn)化成設(shè)備選擇問題,從而簡化模型。Ege等設(shè)定并行工作站的上限,最小化設(shè)備成本,構(gòu)建了兩種分支定界法分別得到最優(yōu)解和似優(yōu)解。Akpinar和Bayhan研究了一種同時考慮區(qū)域約束和并行工作站的混流裝配線平衡問題,在給定節(jié)拍下最小化工作站數(shù),最大化工作站負荷平衡指數(shù)以及工作站內(nèi)并行工作站之間的負荷平衡指數(shù),并構(gòu)建一種混合遺傳算法求解模型。錢雄文構(gòu)建了MM-ALBPII的數(shù)學(xué)模型,并利用遺傳算法求解。Kelleg?z和Toklu研究了多人共站負責(zé)不同作業(yè)的MM-ALBP,并設(shè)計了一種高效的分支定界算法求解問題。本文主要研究MM-ALBPII,以最小化裝配線節(jié)拍為主要目標(biāo),最小化平行操作工人數(shù)為第一輔助目標(biāo),最小化工人負荷標(biāo)準(zhǔn)差為第二輔助目標(biāo),構(gòu)建數(shù)學(xué)模型,提出一種基于兩階段結(jié)構(gòu)式譯碼算法的結(jié)構(gòu)式譯碼遺傳算法求解該模型。1多作業(yè)任務(wù)1MM-ALBPII可以描述為給定工人數(shù)和各工序作業(yè)時間,以及工作站能分配到的最大工人數(shù),在滿足加工優(yōu)先次序關(guān)系的條件下,考慮多人共站,確定作業(yè)和人員的分配方案,以最優(yōu)化目標(biāo)函數(shù)。文中將使用的變量如下:N作業(yè)總數(shù),i,g,h=1,2,…,N;J工作站數(shù)的估計上限,j=1,2,…,J;W給定工人數(shù);K工作站能分配到的最大工人數(shù),k=1,2,…,K;ti作業(yè)i的操作時間;C節(jié)拍時間;決策變量:根據(jù)上述變量定義,建立MM-ALBPII的數(shù)學(xué)模型:其中:ε是一個很小的數(shù),作為懲罰因子。式(1)表示以最小化裝配線節(jié)拍為主要目標(biāo),以最小化平行操作工人數(shù)為第一輔助目標(biāo),以最小化工人負荷標(biāo)準(zhǔn)差為第二輔助目標(biāo)。式(2)表示裝配線上分配的所有工人數(shù)等于給定工人數(shù)。式(3)表示作業(yè)之間的優(yōu)先次序約束。式(4)表示工作站所分配到的作業(yè)時間總和不能超過該工作站的容量。式(5)表示一個作業(yè)只能被分配到一個工作站上。式(6)表示工作站所分配到的工人數(shù)惟一。2翻譯代碼的遺傳計算方法設(shè)計基于文獻設(shè)計一種結(jié)構(gòu)式譯碼遺傳算法,該算法在運行過程中始終只對可行作業(yè)序列子空間進行搜索,以減小搜索范圍,提高搜索效率。2.1作業(yè)元素排成一列本文采用序列編碼方式:按作業(yè)元素被分派至工作站的先后順序,將作業(yè)元素排成一列,每個作業(yè)元素對應(yīng)一個基因位。序列編碼對目標(biāo)函數(shù)和操作算子具有較強的適應(yīng)性。2.2合并工作站的構(gòu)建階段1按單人工作站得到最優(yōu)分配方案(1)按公式計算初始過渡節(jié)拍Cavg。(2)按基因排序分別將作業(yè)分配至當(dāng)前工作站,若該工作站已含有的作業(yè)時間總和超過Cavg,則將當(dāng)前工序分配到當(dāng)前工作站,并進行下一工作站的分配,直至分配完所有作業(yè),令Cavg等于該方案最大工作站工時。(3)令Cavg=Cavg-step(step為節(jié)拍下降步長),按基因排序分配至當(dāng)前工作站,若該工作站已含有的作業(yè)時間總和超過Cavg,則將該工序分配至下一工作站,并開始下一工作站的分配,直至分配完所有作業(yè),計算分配方案的工人總數(shù)WT,最大工作站工時為WLmax。(4)若WT大于給定工人數(shù),輸出最優(yōu)分配方案,退出;否則令Cavg=WLmax,轉(zhuǎn)(3)。階段2合并工作站使得節(jié)拍最小化(1)找出等效工時(工作站總工時/工作站分配人數(shù))最大的瓶頸工作站(若存在多個,則隨機選擇一個),記為W0,其等效工時記為ETmax。(2)分別計算瓶頸工作站與其上游和下游工作站合并之后的等效工時,較小的記為ETless,相應(yīng)的工作站記為W1,較大的記為ETmore,相應(yīng)的工作站則記為W2。(3)若WLless≥ETmax,則退出;否則,轉(zhuǎn)(4)。(4)若瓶頸工作站與工作站W(wǎng)1的工人總數(shù)不超過K,則合并這兩個工作站,并轉(zhuǎn)(1),否則,轉(zhuǎn)(5)。(5)WLmore≥ETmax,則退出;否則,轉(zhuǎn)(6)。(6)若瓶頸工作站與工作站W(wǎng)2的工人總數(shù)不超過K,則合并這兩個工作站,并轉(zhuǎn)(1),否則,退出。2.3生成當(dāng)前特征采用隨機拓撲排序算法生成初始種群,使得初始種群中的所有作業(yè)序列都是可行作業(yè)序列,其步驟如下:(1)置當(dāng)前序列為空。(2)從當(dāng)前優(yōu)先次序圖中隨機選取一個入度為0的節(jié)點插入當(dāng)前序列的尾部。(3)刪去當(dāng)前優(yōu)先次序圖中該節(jié)點以及與它直接相連的邊;若當(dāng)前順序圖中已無節(jié)點,轉(zhuǎn)(4),否則轉(zhuǎn)(2)。(4)輸出當(dāng)前作業(yè)序列。2.4變異算子的生成交叉算子的主要思想是,首先隨機在兩個體內(nèi)確定一個交叉片斷,并通過交換兩交叉片斷中的相同元素子序列,生成滿足作業(yè)順序約束的新個體。具體步驟如下:(1)生成兩個不同的隨機數(shù),利用它們確定交叉片斷,并進而得到兩交叉片斷的相同元素子序列和不同元素子序列。(2)交換兩交叉片斷的相同元素子序列,并與原來的不同元素子序列進行歸并排序,從而生成新的交叉片斷,將新的交叉片斷替換原交叉片斷,形成新染色體。變異算子的主要思想是,使變異元素在序列中可移動范圍內(nèi)的前后移動實現(xiàn)。具體步驟如下:(1)生成一個隨機整數(shù),確定變異元素的位置,并計算該變異元素的可移動范圍(即在可行序列中,變異作業(yè)的直接序前作業(yè)集中位置下標(biāo)最大值,與直接序后作業(yè)集中位置下標(biāo)最小值之間的范圍)。(2)將該作業(yè)在可移動范圍內(nèi)進行隨機移動。2.5初始種群p0記N(p)為種群大小,P(t)為第t代種群,Pc為交叉概率,Pm為變異概率,éxù為不超過實數(shù)x的最大整數(shù)。結(jié)構(gòu)式譯碼遺傳算法總流程如下:步驟1初始化種群,令t=0,產(chǎn)生初始種群P(0),其規(guī)模設(shè)為N(p)。步驟2適應(yīng)度值計算,計算第t代種群P(t)中每個個體的適應(yīng)度值。步驟3選擇,從P(t)中選擇N(p)個個體復(fù)制到P(t+1)。步驟4交叉,從P(t+1)中隨機選取對個體進行交叉,產(chǎn)生的r對子代個體取代原來的r對父代個體。步驟5變異,從P(t+1)中隨機選擇個個體進行變異,生成的新個體替換原來的父代個體。步驟6精英策略,P(t)中適應(yīng)度值最高的個體取代P(t+1)中適應(yīng)度值最低的個體。步驟7令t=t+1,若最優(yōu)值保持max＿iter次不變,則輸出最優(yōu)方案,結(jié)束;否則,轉(zhuǎn)步驟2。3算法有效性比較為驗證結(jié)構(gòu)式譯碼遺傳算法的有效性以及多人共站的優(yōu)勢,本文采用MATLAB實現(xiàn)算法,并分別針對Jackson(如圖1)和Buxey(如圖2)問題進行實驗分析。用結(jié)構(gòu)式譯碼遺傳算法對Jackson問題進行求解。令K=2,Pc=0.8,Pm=0.2,N(p)=40,max＿iter=300,給定工人數(shù)分別為4、5、6時,分別給出其作業(yè)分配方案和人員分配方案,如表1所示。比較表1中結(jié)構(gòu)式譯碼遺傳算法與分支定界法的結(jié)果發(fā)現(xiàn),兩種方法得到的節(jié)拍時間、并行操作工人數(shù)、工人負荷標(biāo)準(zhǔn)差均相同,表明該算法的有效性,同時也說明本文的兩階段結(jié)構(gòu)式譯碼算法的高效性,能將工作站上的工人進行有效合理的安排,以使節(jié)拍時間下降,同時又最小化并行操作工人數(shù),降低并行成本。對Buxey問題,當(dāng)工作站分別取8～14時,各隨機運行算法10次(Pc=0.8,Pm=0.2,N(p)=100,max＿iter=3000),取得最優(yōu)結(jié)果,并與文獻進行比較,結(jié)果如表2所示。由表2中的求解結(jié)果可以發(fā)現(xiàn):(1)當(dāng)K=1,即不考慮多人共站時,結(jié)構(gòu)式譯碼遺傳算法和文獻中算法得到的節(jié)拍時間均相等,但本文算法的負荷標(biāo)準(zhǔn)差更優(yōu)。(2)當(dāng)K=2、3時,即在多人共站條件下,結(jié)構(gòu)式譯碼遺傳算法的節(jié)拍時間、工人負荷標(biāo)準(zhǔn)差同時下降,可見多人共站可有效縮短生產(chǎn)節(jié)拍同時使工人間的負荷更加均衡。4結(jié)構(gòu)式譯碼遺傳算法求解匹配方案優(yōu)化在多人共站裝配線平衡問題中,考慮了最小節(jié)拍時間、并行操作工人數(shù)和工人負荷標(biāo)準(zhǔn)差的綜合影響,以比較最小節(jié)拍時間相同的