李俊成 王 巍
(東北林業(yè)大學機電工程學院,黑龍江 哈爾濱 150040)
裝配線問題(Assembly Line Balancing Problem,ALBP)[1]在現(xiàn)代制造領(lǐng)域中具有重要地位,自福特汽車公司建立生產(chǎn)線以來,相關(guān)人員一直在探索和研究該問題,并在此期間進行了多次嘗試。
裝配線平衡問題的不同的目標函數(shù)主要分為3 類:在已知生產(chǎn)節(jié)拍的情況下,使工作站數(shù)最小化(即ALBP-Ⅰ);在已知工作站數(shù)的情況下,使生產(chǎn)節(jié)拍最小化(即ALBP-Ⅱ);在已知工作站數(shù)和生產(chǎn)節(jié)拍的情況下,使裝配線負荷更均勻,即平滑指數(shù)最小化(即ALBP-Ⅲ)。已知裝配線問題屬于NPhard 問題[2],通常使用精確算法或元啟發(fā)式算法對裝配線平衡問題進行求解,例如原丕業(yè)等[3]提出的改進的自適應(yīng)遺傳算法求解模型能夠更好地解決混流裝配線平衡問題。
本文根據(jù)裝配線平衡問題的特征,以最小化工作站數(shù)量、綜合考慮裝配線平衡率和平滑指數(shù)為優(yōu)化目標建立裝配線平衡模型,并結(jié)合遺傳算法與蟻群算法,提出了一種混合優(yōu)化算法模型(GA-ACO),以解決裝配線平衡問題。
本文研究的裝配線平衡問題是在生產(chǎn)節(jié)拍已知的情況下,在裝配過程中,各工序在緊前作業(yè)順序的約束下將全部工序安排到工作站中進行裝配作業(yè),保證每個工作站的裝配時間不超過生產(chǎn)節(jié)拍,并盡量使安排的工作站數(shù)最少且每個工作站的裝配作業(yè)時間和裝配作業(yè)負荷盡量均衡。本文將裝配線平衡率和平滑指數(shù)作為評價指標,其中的裝配線平衡率表示裝配線的平衡狀況,平衡率越大,說明裝配線平衡效果越好。平滑指標表示裝配線的負荷狀況,平滑指數(shù)越小,說明裝配線負荷越均勻。本文將裝配線平衡率與平滑指數(shù)相結(jié)合,并作為目標函數(shù)。
本文所提問題的基本假設(shè)如下。1)只對某一類產(chǎn)品進行裝配作業(yè)。2)每道工序作業(yè)時間是已知且確定的。3)所有作業(yè)工序必須滿足優(yōu)先順序。4)每道工序只能分配到一個工作站中。5)每個工作站的裝配工作時間不能超過生產(chǎn)節(jié)拍。
本文所提多目標裝配線平衡問題的數(shù)學描述如下。
裝配線平衡率P越大,表示裝配線平衡狀況越好,即裝配線空余時間最少;平滑指數(shù)SI越小,表示裝配線負荷越均勻。二者分別如公式(1)、公式(2)所示。
式中:P為裝配線平衡率;SI為平滑指數(shù);m為工位的數(shù)量;sti為第i個工作站的工作時間;CT為生產(chǎn)節(jié)拍。
裝配線平衡優(yōu)化目標函數(shù)H1、H2分別如公式(3)、公式(4)所示。
約束條件如公式(5)~公式(8)所示。任意2 個工作站不能出現(xiàn)重復的工序如公式(5)所示。任意1 個工作站的裝配時間都≦生產(chǎn)節(jié)拍如公式(6)所示。任意1 個裝配工序都應(yīng)被分配到工作站中如公式(7)所示。每個工序的緊前作業(yè)關(guān)系如公式(8)所示。
式中:H1、H2表示目標函數(shù);Mk1、Mk2分別為第k1個和第k2個工作站所分配工序的集合;Tk表示第k個工作站的所有工序裝配時間;M 表示所有工作站中工序的集合;Mk表示第k個工作站上所分配工序的集合;Pij=1 表示工序i是工序j的緊前作業(yè)順序;i∈Ma、j∈Mb表示工序i和工序j分別在第a個和第b個工作站完成。
本文將遺傳算法與蟻群算法相結(jié)合,提出了一種混合優(yōu)化算法模型來求解裝配線平衡問題。首先,對遺傳算法參數(shù)進行初始化設(shè)置,用隨機拓撲法[4]按照工序順序圖生成初始序列,產(chǎn)生初始種群,然后計算初始種群的適應(yīng)度值。其次,通過選擇、交叉和變異等方法生成新的種群,再計算新種群的適應(yīng)度值。進行迭代調(diào)整后,得出最優(yōu)結(jié)果。再次,將蟻群算法中所有參數(shù)進行初始化設(shè)置,將遺傳算法得到的最終解作為蟻群算法最初的信息素分布,隨機生成螞蟻的初始節(jié)點,根據(jù)概率選擇公式選擇下一可行節(jié)點,更新信息素,并計算每條路徑的信息素濃度。經(jīng)過迭代調(diào)整后,生成裝配線平衡問題的最優(yōu)解?;旌蟽?yōu)化算法模型求解裝配線平衡問題流程如圖1所示。
圖1 混合優(yōu)化算法模型流程圖
2.2.1 生成初始種群
本文要求初始群體中的所有作業(yè)序列均為可行作業(yè)序列,采用基于作業(yè)順序的染色體編碼規(guī)則。根據(jù)作業(yè)順序圖,用隨機拓撲排序法生成初始序列,以確保初始種群的多樣性。隨機拓撲排序的一般步驟如下。1)從序列圖中隨機選擇一個輸入度為0 的頂點并輸出。2)從序列圖中刪除該頂點和所有以該頂點為起點的有向線段。3)重復步驟1 和2,直到序列圖為空或者不存在輸入度為0 的頂點為止。4)輸出當前序列并生成初始種群
2.2.2 選擇
本文采用輪盤賭法進行選擇操作。個體的適應(yīng)度值越高時,則個體被選中的概率越大,如公式(9)所示。
式中:Pxi表示個體被選中的概率;fxi表示被選中個體的適應(yīng)度值;fxj表示不同個體的適應(yīng)度值。
2.2.3 交叉
交叉是指從種群中根據(jù)概率隨機選擇2 個個體,并將2 個個體間的染色體進行交換。本文選擇的交叉方式是兩點交叉,即從染色體中隨機選擇2 個交叉點,將這2 個交叉點間的染色體進行交換,形成新的基因序列,如圖2所示。
圖2 交叉操作示意圖
2.2.4 變異
變異是指用其他等位基因替換個體染色體的基因座的基因值,從而形成一個新的個體,如圖3所示。
圖3 變異操作示意圖
2.3.1 評價解的質(zhì)量的目標函數(shù)
本文求解的是ALBP-Ⅰ問題,即明確生產(chǎn)節(jié)拍,使工作站數(shù)最少。在求解過程中,如果以目標函數(shù)H1為目標函數(shù),會出現(xiàn)大量重復解,不易區(qū)分。因此,選用目標函數(shù)H2來評價解的質(zhì)量。
2.3.2 信息素更新
本文的信息素更新策略為全局信息素更新。當螞蟻周游全部裝配工序并構(gòu)建全局最優(yōu)解后,才會添加信息素,從而使其他螞蟻跟隨,提高了搜索的目的性。當前迭代中,全局最優(yōu)螞蟻會根據(jù)公式(10)、公式(11)更新全局信息素。
式中:τij為信息素強度;τij(t)為t時刻信息素強度;τij(t+1)為(t+1)時刻的信息素強度;ρ為信息素揮發(fā)系數(shù);H2為當前最優(yōu)分配方案的目標函數(shù)。
基于上述算法的思路和流程,為了驗證其有效性,用MATLAB R2021b 實現(xiàn)上述算法,采用網(wǎng)址“https://assemblyline-balancing.de/”中的標準算例進行測試和比較。分別用傳統(tǒng)遺傳算法模型與混合優(yōu)化算法模型對裝配線平衡問題進行求解,并比較其平衡優(yōu)化效果。
本文采用經(jīng)典問題Buxey 問題對模型進行驗證,并與實例庫中的其他案例[5-8]進行比較。Buxey 問題的作業(yè)優(yōu)先順序如圖4所示。
圖4 Buxey 問題的作業(yè)優(yōu)先順序圖
基于混合算法求解裝配線平衡問題,具體參數(shù)見表1。
表1 混合優(yōu)化算法模型參數(shù)
Buxey 問題由29 個裝配工序組成,當生產(chǎn)節(jié)拍CT=36s 時,混合算法模型所得裝配線平衡結(jié)果如圖5所示。
圖5 裝配線平衡圖
本文將混合算法模型與傳統(tǒng)遺傳算法模型所得結(jié)果進行比較,見表2 和表3。根據(jù)表2、表3 可知,當混合算法模型和遺傳算法模型在CT=36s 時,對于Buxey 問題,2 種算法模型都可以得出最小工作站數(shù)m=10 的結(jié)果,均為最優(yōu)工作站數(shù)。但混合算法模型所得裝配線平衡率和平滑指數(shù)分別為0.952941%和2.04939,而遺傳算法模型所得裝配線平衡率和平滑指數(shù)分別為0.925714%和4.09878。顯而易見,混合算法模型所得裝配線平衡率更高且平滑指數(shù)更小,證明在裝配線平衡問題的求解方面,本文所提混合算法模型比遺傳算法模型更好。
表2 混合算法模型求解結(jié)果
表3 遺傳算法模型求解結(jié)果
為了更好地驗證本文混合算法模型的有效性,需要與文獻[5-8]中相同的經(jīng)典案例進行比較,驗證結(jié)果見表4。根據(jù)表4 可知,混合優(yōu)化算法模型求解裝配線平衡算例與遺傳算法模型有較明顯的差距。混合優(yōu)化算法模型在每個算例的驗證中都得到了最優(yōu)工作站數(shù),而遺傳算法模型則在多種算例中多次出現(xiàn)未達到最優(yōu)工作站數(shù)的情況。并且在2 種算法模型均達到最優(yōu)工作站數(shù)的情況下,混合優(yōu)化算法模型的目標函數(shù)值H2均不小于遺傳算法模型的目標函數(shù)值H2。因此在裝配線問題的求解中,本文提出的混合優(yōu)化算法模型比遺傳算法模型更具有效性。
表4 經(jīng)典算例驗證結(jié)果
本文針對第一類裝配線平衡問題,并結(jié)合第三類裝配線問題提出了一種混合算法模型,在已知生產(chǎn)節(jié)拍的情況下,求解出最小工作站數(shù)、最大裝配線平衡率和最小平滑指數(shù)。該算法模型將遺傳算法與蟻群算法相結(jié)合,并以將遺傳算法最終解作為蟻群算法最初信息素分布的方式將2 種算法結(jié)合起來,從而有效改進前期收斂速度不足的問題。在目標函數(shù)上,增加了裝配線平衡率與平滑指數(shù)相結(jié)合的目標函數(shù),能夠在2 種算法同時獲得最小工作站數(shù)的情況下更好地評價算法的優(yōu)劣,進而選擇效果更好的算法。與經(jīng)典算例進行比較后可知,在求解裝配線平衡問題方面,本文所提混合優(yōu)化算法模型能夠獲得更多的最優(yōu)解和最小的平滑指數(shù)。由此可以證明,本文所提GA-ACO 混合優(yōu)化算法模型對裝配線平衡問題具有更好的求解能力。