基于混合遺傳模擬退火算法的第二類裝配線平衡優(yōu)化

［摘 要］ 針對離散型制造企業(yè)的第Ⅱ類裝配線平衡問題，構(gòu)建以最小生產(chǎn)節(jié)拍、最小負(fù)載標(biāo)準(zhǔn)差為優(yōu)化目標(biāo)的數(shù)學(xué)模型。在經(jīng)典遺傳算法的基礎(chǔ)上，設(shè)計一種基于精英保留策略的種群分離機(jī)制以維持種群的基因多樣性，并根據(jù)算法的迭代進(jìn)程引入自適應(yīng)交叉與自適應(yīng)變概率操作；為提高算法的局部搜索能力，嵌入模擬退火算法的Metropolis準(zhǔn)則，形成一種混合遺傳模擬退火算法；通過標(biāo)準(zhǔn)案例集的12組實驗，相較于遺傳算法，混合遺傳模擬退火算法在求解能力上具有明顯優(yōu)勢。進(jìn)一步，以某企業(yè)的青貯機(jī)裝配線為案例，應(yīng)用混合遺傳模擬退火算法進(jìn)行求解，結(jié)果顯示該模型的有效性和混合遺傳模擬退火算法的優(yōu)越性。生產(chǎn)實例驗證結(jié)果表明，優(yōu)化后的裝配線生產(chǎn)周期縮短為50.4 s，線平衡率提升至93.52%，顯著提升了農(nóng)機(jī)企業(yè)裝配線的效率。

［關(guān)鍵詞］ 裝配線平衡； 生產(chǎn)節(jié)拍； 負(fù)載標(biāo)準(zhǔn)差； 混合遺傳模擬退火算法

［中圖分類號］ TH181 ［文獻(xiàn)標(biāo)識碼］ A

裝配生產(chǎn)線是制造企業(yè)生產(chǎn)活動的核心。然而，如何具體合理地安排各道工序的生產(chǎn)順序，以提升裝配線的效率和穩(wěn)定性，是一個被稱為裝配線平衡問題（assembly line balancing problem， ALBP）的挑戰(zhàn)。根據(jù)不同的優(yōu)化目標(biāo)，ALBP可以分為3種類型[1]：第Ⅰ類旨在優(yōu)化工作站的數(shù)量，第Ⅱ類為關(guān)注優(yōu)化生產(chǎn)節(jié)奏，第Ⅲ類則為均衡各工作站的工作負(fù)載。本文重點探討第Ⅱ類裝配線平衡問題（ALBP-2），這是一種典型的NP-hard（non-deterministic polynomial hard）問題。近年來，許多學(xué)者對ALBP-2進(jìn)行了廣泛的研究。方喜峰等[2]為了使裝配線在最短時間內(nèi)達(dá)到最優(yōu)，建立了裝配線平衡模型，以某產(chǎn)品的裝配線為案例進(jìn)行了分析，并通過采用遺傳算法，結(jié)合蟻群算法對該問題進(jìn)行了求解。實驗結(jié)果表明，這種改進(jìn)的遺傳算法能夠有效解決ALBP-2，而且與蟻群算法相比，在求解精度和收斂速度上均有所提高。Wang等[3]針對裝配線部分拆卸和并行布局的特點，設(shè)計了一種新的編碼和解碼策略。Krenczyk等[4]在針對汽車工業(yè)的大型產(chǎn)品裝配線平衡問題建模時，考慮了汽車裝配線額外的位置限制，并以裝配線占用的空間最小和工位數(shù)量最小為優(yōu)化目標(biāo)，提出了一種啟發(fā)式工作站任務(wù)分配與回溯技術(shù)相結(jié)合的混合優(yōu)化方法。趙乾宏等[5]通過改進(jìn)果蠅算法，解決了某企業(yè)風(fēng)電制動器裝配線的工位負(fù)載不均衡問題，并在Plant Simulation仿真軟件中驗證了其優(yōu)越性。趙文燕等[6] 考慮了工作站數(shù)量約束的多目標(biāo)裝配線平衡優(yōu)化，并設(shè)計了混合遺傳算法來求解。肖暉等[7]針對粒子群算法容易陷入局部最優(yōu)的問題，將反向?qū)W習(xí)策略融至算法中，通過案例驗證了改進(jìn)PSO算法比標(biāo)準(zhǔn)PSO算法具有更好的求解能力。以上研究方法雖然能夠有效求解ALBP-2，但其算法參數(shù)多，且算法的尋優(yōu)能力有待提高。

在經(jīng)典的遺傳算法（genetic algorithm， GA）[8-9]中，種群中的個體基于一定的概率執(zhí)行交叉和變異操作產(chǎn)生新個體。該算法雖然能夠在較短的時間內(nèi)獲得可行解，但是全局搜索能力較弱，容易陷入局部最優(yōu)解。模擬退火算法（simulated annealing， SA）[10-11]是一種局部優(yōu)化算法，能夠概率性地跳出局部最優(yōu)。因此，本文結(jié)合兩種算法的搜索能力，設(shè)計了一種混合遺傳模擬退火算法（genetic-simulated annealing algorithm， GASA），以有效避免算法“早熟”，從而使算法具有更強(qiáng)的尋優(yōu)能力。

1 問題描述和數(shù)學(xué)模型

1.1 問題描述與假設(shè)

ALBP-2可被描述為一個任務(wù)集，任務(wù)之間存在特定的加工順序約束。給定裝配線的工作站數(shù)量，目的是將任務(wù)集中的所有作業(yè)元素分配至各個工作站，以實現(xiàn)最小的生產(chǎn)節(jié)拍，并確保各個工作站的負(fù)載盡可能均衡。

為減小理論優(yōu)化模型與實際生產(chǎn)應(yīng)用的偏差，還需作如下假設(shè)：

1）任務(wù)集中的每個作業(yè)元素加工時間已知，且作業(yè)元素的先后加工關(guān)系已知；

2）不考慮工作站之間的運輸時間；

3）所有操作工人并無差別；

4）每個作業(yè)只能被分配一次，且無并行工作站；

5）不考慮在制品的傳遞時間。

1.2 數(shù)學(xué)模型

在實踐中，可能存在多種最小生產(chǎn)節(jié)拍的情況。為了從諸多方案中甄選出最優(yōu)解，不僅要關(guān)注最小化生產(chǎn)節(jié)拍，還應(yīng)兼顧工作站的負(fù)載均衡。因此，在評估不同裝配方案時，本文綜合考慮裝配線的最小生產(chǎn)節(jié)拍和工作站負(fù)載分配情況這兩個優(yōu)化目標(biāo)。

在評價裝配線平衡問題時，常用裝配線的平衡率φ表示裝配線的平衡狀況，φ越大表示裝配線的平衡效果越好：

當(dāng)工作站工作負(fù)載與生產(chǎn)節(jié)拍差距越小時，裝配線堵塞和閑置的時間越小，裝配效率越高。為了平衡裝配線上工作站之間的作業(yè)負(fù)載程度，每個工作站分配的作業(yè)負(fù)載應(yīng)盡量均等，即

因此，本文研究的ALBP-2是由最小化生產(chǎn)節(jié)拍TC、最小化工作站間的作業(yè)負(fù)載標(biāo)準(zhǔn)差B共同組成，采用加權(quán)法將多目標(biāo)優(yōu)化問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，而加權(quán)由決策者根據(jù)實際情況決定，其中α1，α2分別代表上述兩個優(yōu)化目標(biāo)的權(quán)重：

式（5）表示所有作業(yè)都必須分配給工作站；式（6）表示每個工作站至少有一個作業(yè)任務(wù)；式（7）表示每個作業(yè)只允許至一個工作站上；式（8）表示各個工作站之間沒有重復(fù)分配的作業(yè)任務(wù)，且所有作業(yè)分配完畢。

2 算法設(shè)計

2.1 編碼與種群初始化

常用的編碼方式有二進(jìn)制編碼、自然數(shù)編碼和浮點數(shù)編碼。針對ALBP-2的求解結(jié)果，需要包含工作站的工序分配和工作站內(nèi)的工序排序。本文采用基于優(yōu)先級的自然數(shù)編碼解碼方案，避免了算法進(jìn)制轉(zhuǎn)換運算量大的弊端。以某裝配線為例，圖1中圓圈數(shù)字代表裝配作業(yè)序號，圖圈外數(shù)字為對應(yīng)工序的裝配時間，圖2為一種具體的染色體編碼方案。

種群初始化按照每個作業(yè)的工序約束隨機(jī)生成，各工位分配得到的所有工序作業(yè)總時間不大于生產(chǎn)節(jié)拍。采用基于布爾優(yōu)先關(guān)系矩陣的方法隨機(jī)生成初始種群，可以避免非法解的產(chǎn)生。具體過程如下：

步驟1，根據(jù)布爾優(yōu)先關(guān)系矩陣從集合A中找出無緊前工序的作業(yè)任務(wù)，并放入集合T1中，并在作業(yè)順序圖中刪除選出的任務(wù)i和與優(yōu)先關(guān)系矩陣有關(guān)的邏輯關(guān)系；

步驟2，從集合T1中選取優(yōu)先級較高的作業(yè)任務(wù)，放入到相應(yīng)的基因位；

步驟3：從集合A找出已被分配的緊前工序放入集合T1中，根據(jù)選取優(yōu)先級較高的作業(yè)任務(wù)，放入到相應(yīng)的基因位；

步驟4：判斷集合A所有任務(wù)是否分配完畢，若是，則分配結(jié)束，否則重復(fù)執(zhí)行步驟1—步驟3。

2.2 選擇操作

常用選擇操作有輪盤賭法、錦標(biāo)賽法。本文在輪盤賭的基礎(chǔ)上引入精英保留策略，直接將上一代適應(yīng)度值最高的個體復(fù)制到下一代中，且采用種群分離策略避免算法陷入局部最優(yōu)，將適應(yīng)度值前n/2（n為種群所有個體的數(shù)目）的個體劃為優(yōu)質(zhì)種群，余下的劃為劣質(zhì)種群。具體操作如圖3所示。

2.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)決定著種群的進(jìn)化方向。本文的目標(biāo)函數(shù)是最小化裝配線的生產(chǎn)節(jié)拍和最小化工作站分配的作業(yè)負(fù)載標(biāo)準(zhǔn)差。最小生產(chǎn)節(jié)拍表征企業(yè)的生產(chǎn)效率，其重要性不言而喻，而作業(yè)負(fù)載標(biāo)準(zhǔn)差決定了生產(chǎn)系統(tǒng)的平穩(wěn)運行，決策者可以根據(jù)不同的實際情況進(jìn)行賦值。本文通過對實際案例的分析，將兩個目標(biāo)權(quán)重都設(shè)為0.5[7]，適應(yīng)度值越小代表個體越優(yōu)秀。適應(yīng)度值函數(shù)

2.4 交叉操作

交叉操作是遺傳算法中產(chǎn)生新個體的主要方式。本文設(shè)計了一種自適交叉概率

式中：M為算法的最大迭代次數(shù)；m為當(dāng)前迭代次數(shù)；PC，min為最小交叉概率；PC，max為最大交叉概率。

交叉操作可以隨機(jī)從種群中選取兩個染色體作為父代1、父代2，并在兩條父代染色體相同的基因位上隨機(jī)生成兩個交叉點，取出父代2的前部分和后部分，同時在父代1中獲取中間部分基因的排列順序，按順序填充至子代1的中間部分。同理生成子代2，具體的交叉操作如圖4所示。

2.5 變異操作

對于變異操作，可維持種群的多樣性以防止算法陷入局部最優(yōu)。變異操作可隨機(jī)選取染色體中的某一基因片段，然后根據(jù)優(yōu)先關(guān)系矩陣分別找出緊前工序和緊后工序的基因位置，隨機(jī)生成一個基因片段并插入至該位置。交叉操作如圖5所示，變異概率

式中：M為算法的最大迭代次數(shù)；m為當(dāng)前迭代次數(shù)；Pm，min為最小變異概率；Pm，max為最大變異概率。

2.6 Metropolis準(zhǔn)則

盡管在選擇操作時對種群進(jìn)行了種群分離，增強(qiáng)了算法的全局搜索能力，但算法還是容易陷入局部最優(yōu)解。因此，通過嵌入模擬退火算法，進(jìn)一步提高算法的尋優(yōu)能力；通過采用Metropolis準(zhǔn)則，算法以一定的概率接受新個體，從而保證種群的多樣性。設(shè)定初始溫度為t0，終止溫度為tend，F(xiàn)a（t）為個體變換前的個體適應(yīng)度，F(xiàn)b（t）則為變換后的個體適應(yīng)度：

步驟1：算法的參數(shù)設(shè)置。

步驟2：根據(jù)裝配順序的前后加工關(guān)系約束進(jìn)行種群初始。

步驟3：評價種群中每個個體的適應(yīng)度值。

步驟4：對種群執(zhí)行選擇操作，并按適應(yīng)度值的大小進(jìn)行升序排序，將適應(yīng)度值最高的個體運用精英保留策略進(jìn)行保留，然后將排序后的種群平均分成兩等份得到“優(yōu)質(zhì)子種群”和“劣質(zhì)子種群”。

步驟5：對“優(yōu)質(zhì)子種群”執(zhí)行自適應(yīng)交叉操作[LL]和自適應(yīng)變異操作，對“劣質(zhì)子種群”重新生成新個體，然后合并新種群。

步驟6：執(zhí)行模擬退火操作，并根據(jù)Meteropolis準(zhǔn)則接受新個體。

步驟7：重復(fù)執(zhí)行步驟3—步驟6，直至算法滿足終止條件，并輸出最優(yōu)解。

3 實例分析

3.1 基準(zhǔn)實例測試比較

采用文獻(xiàn)[7]和文獻(xiàn)[12]的數(shù)據(jù)集，用標(biāo)準(zhǔn)GA算法與改進(jìn)的GASA算法進(jìn)行對比，每個算例用MATLAB測試20次，并記錄GASA的平均值與最優(yōu)值。本文算法參數(shù)查閱文獻(xiàn)[8，10]，并通過多次試驗得：種群規(guī)模N=50，PC，max=0.6，PC，min=0.3，Pm，max=0.2，Pm，min=0.01，終止溫度Fend=1000，初始溫度Fs=0.001，溫度冷卻系數(shù)Δ=0.9，其他算法參數(shù)選用相關(guān)文獻(xiàn)參數(shù)設(shè)置。對比結(jié)果如表1所示。

從對比結(jié)果可以看出，除小規(guī)模Mitchell案例外，其他案例求解結(jié)果GASA均優(yōu)于GA，達(dá)到了理想的生產(chǎn)節(jié)拍和負(fù)載標(biāo)準(zhǔn)差，即充分做到了作業(yè)分配的負(fù)載平衡，說明GASA在求解不同規(guī)模問題時具有很強(qiáng)的可靠性及準(zhǔn)確性。

3.2 實例驗證

為了驗證算法的有效性和優(yōu)越性，以某青貯機(jī)裝配線為例，青貯機(jī)裝配線（圖6）39個作業(yè)任務(wù)，分配至11個工作站。求得GASA的作業(yè)分配方案如表2所示，并與文獻(xiàn)[7]、文獻(xiàn)[13]進(jìn)行對比，結(jié)果如表3所示。

通過算法對比分析，驗證了GASA在處理裝配線平衡問題時的優(yōu)越性，所求得的最小生產(chǎn)節(jié)拍和負(fù)載標(biāo)準(zhǔn)差均優(yōu)于其他改進(jìn)算法，生產(chǎn)節(jié)拍降至50.4 s，工作站負(fù)載標(biāo)準(zhǔn)差降至4.43，裝配線的平衡率提升至93.52%，提高了青貯機(jī)裝配線的生產(chǎn)效率。

4 結(jié)論

1）本文以第Ⅱ類裝配線的生產(chǎn)節(jié)拍、負(fù)載標(biāo)準(zhǔn)差最小為優(yōu)化目標(biāo)建立數(shù)學(xué)模型，為提高算法的尋優(yōu)能力嵌入了模擬退火算法的隨機(jī)搜索操作；通過引入種群分離策略改進(jìn)選擇操作，并使用精英保留策略以加快算法的收斂速度，而基于模擬退火的隨機(jī)搜索操作有助于算法跳出局部最優(yōu)，從而增強(qiáng)了算法的全局搜索能力。

2）通過求解標(biāo)準(zhǔn)案例驗證了混合遺傳模擬退火算法有更強(qiáng)的求解能力，且以某青貯機(jī)裝配線為實例，采用遺傳算法、改進(jìn)遺傳算法、改進(jìn)粒子群算法與混合遺傳模擬退火算法進(jìn)行求解分析，并驗證了混合遺傳模擬退火算法相比其他算法具有更強(qiáng)的全局尋優(yōu)能力。

3）生產(chǎn)實例驗證表明，優(yōu)化后的裝配線生產(chǎn)節(jié)拍為50.4 s，線平衡率達(dá)到93.52%，有效提高了農(nóng)機(jī)企業(yè)裝配線的生產(chǎn)效率。

［ 參 考 文 獻(xiàn) ］

［1］ 原丕業(yè)， 管夢竹. 基于改進(jìn)果蠅優(yōu)化算法的第Ⅰ類雙邊裝配線平衡問題研究[J]. 現(xiàn)代制造工程， 2022， 499（04）：29.

[2] 方喜峰， 章振， 張勝文， 等. 基于混合優(yōu)化算法的裝配線平衡問題[J]. 現(xiàn)代制造工程， 2021（04）：20-25，32.

[3] WANG K， LI X， GAO L， et al. A genetic simulated annealing algorithm for parallel partial disassembly line balancing problem[J]. Applied Soft Computing， 2021， 107：107404.

[4] KRENCZYK D， DZIKI K. Heuristic and backtracking algorithm for multimanned assembly line balancing problem with location constraints[J]. Cybernetics and Systems， 2020， 51（07）： 698-713.

[5] 趙乾宏， 朱成順， 張輝， 等. 仿真環(huán)境下混流裝配線平衡和排序的優(yōu)化研究[J]. 制造技術(shù)與機(jī)床， 2023（05）：166-172.

[6] 趙文燕， 張世哲， 師柳柳. 具有工作站數(shù)量約束的多人工作站混合裝配線平衡問題研究[J]. 運籌與管理， 2022， 31（04）：41-48.

[7] 肖暉， 鄭巧仙. 面向第二類裝配線平衡問題的改進(jìn)粒子群算法[J]. 湖北大學(xué)學(xué)報（自然科學(xué)版）， 2023， 45（02）：164-170.

[8] ALAVIDOOST M H， TARIMORADI M， ZARANDI M H F. Fuzzy adaptive genetic algorithm for multi-objective assembly line balancing problems[J]. Applied soft computing， 2015， 34：655-677.

[9] KUCUKKOC I， ZHANG D Z. A mathematical model and genetic algorithm-based approach for parallel two-sided assembly line balancing problem[J]. Production Planning amp; Control， 2015， 26（11）：874-894.

[10] ROSHANI A， GIGLIO D. Simulated annealing algorithms for the multi-manned assembly line balancing problem： minimising cycle time[J]. International Journal of Production Research， 2017， 55（10）：2731-2751.

[11] ROSHANI A， GHAZI NEZAMI F. Mixed-model multi-manned assembly line balancing problem： a mathematical model and a simulated annealing approach[J]. Assembly Automation， 2017， 37（01）：34-50.

[12] JONNALAGEDDA V， DABADE B. Application of simple genetic algorithm to U-shaped assembly line balancing problem of type II[J]. IFAC proceedings volumes， 2014， 47（03）：6168-6173.

[13] 李明， 包建軍， 袁逸萍. 基于改進(jìn)遺傳算法的多目標(biāo)裝配線平衡優(yōu)化研究[J]. 機(jī)械設(shè)計與制造， 2022， 374（04）：204-207.

Research on the Type-Ⅱ of Assembly Line Balancing OptimizationBased on Hybrid Genetic Simulated Annealing ALGORITHM

WANG Ke， LI Xixing

（School of Mechanical Engineering， Hubei Univ. of Tech.， Wuhan 430068， China）

Abstract： For the Type-Ⅱ of assembly line balancing problem in discrete manufacturing enterprises， a mathematical model with minimum production beat and minimum load standard deviation as the optimization objectives has been established. Based on the classical genetic algorithm， a population separation mechanism based on elite retention strategy has been designed to retain the genetic diversity of the population， and adaptive crossover and adaptive variable probability has been introduced according to the number of iterations of the algorithm; the Metropolis criterion of simulated annealing has been embedded to prevent the algorithm from falling into local optimum， which makes the hybrid genetic simulated annealing algorithm designed in this paper have stronger global search capability. Finally， taking the silage machine assembly line of an enterprise as an example， the hybrid genetic simulated annealing algorithm has been used to solve the problem. Compared with the genetic algorithm， the improved genetic algorithm and the improved particle swarm optimization algorithm. The validity of the model and the superiority of the hybrid genetic simulated annealing algorithm have been verified by the comparison results. The production example shows that the optimized assembly line production beat was 50.4s， and the line balance rate reaches 93.52%， which effectively improves the production efficiency of the assembly line of agricultural machinery enterprises.

Keywords： balancing assembly line; production beat; load standard deviation; local optimum; hybrid genetic simulated annealing algorithm

［責(zé)任編校： 張 眾］

［收稿日期］ 2023-07-31

［第一作者］ 王 科（1997-）， 男， 湖北黃岡人， 湖北工業(yè)大學(xué)碩士研究生， 研究方向為生產(chǎn)調(diào)度與優(yōu)化。

［通信作者］ 李西興（1990-）， 男， 河南信陽人， 工學(xué)博士， 湖北工業(yè)大學(xué)副教授， 研究方向為生產(chǎn)調(diào)度與優(yōu)化、 制造業(yè)信息化。