歐陽飛羽 王 巍

（東北林業(yè)大學(xué)機(jī)電工程學(xué)院，黑龍江 哈爾濱 150040）

裝配線平衡優(yōu)化問題是指在裝配線上的工作站間合理分配任務(wù)，最大程度地提高生產(chǎn)效率和資源利用率[1]。但隨著產(chǎn)品不斷創(chuàng)新，裝配線的復(fù)雜程度也不斷提高，引起了學(xué)者們的廣泛關(guān)注。為解決裝配線平衡問題，常用的方法包括數(shù)學(xué)求解法、工業(yè)工程方法和智能算法等。在智能算法中，最常見的是啟發(fā)式算法。

田廣東等人以提高拆卸效率為目標(biāo)，提出一種社會(huì)工程算法，結(jié)果表明該算法能有效優(yōu)化拆解線平衡率[2]。李明等人通過改進(jìn)遺傳算法對(duì)多目標(biāo)的裝配線平衡問題進(jìn)行求解，不僅考慮產(chǎn)線平衡率，還對(duì)平衡指數(shù)和生產(chǎn)節(jié)拍進(jìn)行尋優(yōu)[3]。

啟發(fā)式算法雖然能對(duì)裝配線平衡問題進(jìn)行求解，但其運(yùn)算速度較慢，求解過程中容易陷入某一個(gè)虛假的最優(yōu)解中，導(dǎo)致結(jié)果并不理想。

基于此，該文對(duì)傳統(tǒng)的單種群遺傳算法進(jìn)行改進(jìn)，擴(kuò)展單一種群成為雙種群遺傳算法，并在此基礎(chǔ)上引入自適應(yīng)算子改進(jìn)遺傳算法中的交叉過程，避免遺傳算法在解決裝配線平衡問題時(shí)無法精確尋優(yōu)，以期能更好地解決實(shí)際問題。

1 問題描述與模型構(gòu)建

可以根據(jù)不同的評(píng)價(jià)指標(biāo)評(píng)估裝配線平衡狀況，并根據(jù)評(píng)估結(jié)果決定是否進(jìn)行改善，針對(duì)不同的生產(chǎn)需求，選擇的評(píng)估指標(biāo)也不同[4]。

生產(chǎn)平衡率為實(shí)際生產(chǎn)時(shí)間與總可用時(shí)間的比率，表示任務(wù)在各工作站間的分配效率。生產(chǎn)平衡率越高，說明資源分配越有效，閑置時(shí)間越少，生產(chǎn)率越高，如公式（1）所示。

式中：P為生產(chǎn)平衡率；ti為完成每道工序所需要的標(biāo)準(zhǔn)時(shí)間；q為工作站的個(gè)數(shù)；CT為節(jié)拍時(shí)間，是每個(gè)工作站完成一個(gè)單位產(chǎn)品需要的最長(zhǎng)時(shí)間。減少節(jié)拍時(shí)間，能最大限度地減少瓶頸，提高生產(chǎn)平衡率。

生產(chǎn)平衡率可以反映裝配線的平衡狀態(tài)。當(dāng)生產(chǎn)平衡率低于60%時(shí)，說明整條裝配線均未采用科學(xué)管理的生產(chǎn)方式，必須進(jìn)行改進(jìn)。當(dāng)生產(chǎn)平衡率在60%～80%時(shí)，說明整條裝配線采用了一定的科學(xué)管理方式，但平衡狀態(tài)并不好。當(dāng)生產(chǎn)平衡率在80%～90%時(shí)，整條產(chǎn)線的平衡狀態(tài)已經(jīng)有很大的改善，當(dāng)生產(chǎn)平衡率大于90%時(shí)，說明裝配線的平衡狀態(tài)較好，能以最高的生產(chǎn)效率完成生產(chǎn)。

平滑指數(shù)可以量化不同工作站間周期時(shí)間的差異，通過工作站間工作時(shí)間的差異程度衡量平衡性。平滑指數(shù)越小，說明裝配線越平衡；平滑指數(shù)越大說明裝配線不平衡，工作站間的工作負(fù)載不均衡。

平滑指數(shù)能幫助識(shí)別裝配線上的瓶頸工作站或不平衡因素，從而引導(dǎo)制定優(yōu)化策略；通過調(diào)整工作任務(wù)分配，使平滑指數(shù)變小，可以讓工作站間負(fù)載均衡，提高生產(chǎn)效率和質(zhì)量穩(wěn)定性。通過監(jiān)控和調(diào)整平滑指數(shù)可以促進(jìn)裝配線的可持續(xù)發(fā)展，減少資源浪費(fèi)，提高生產(chǎn)系統(tǒng)的整體效益。計(jì)算平滑指數(shù)如公式（2）所示。

式中：q為工作站數(shù)目；Ti為完成每個(gè)工作站內(nèi)所有工序需要的標(biāo)準(zhǔn)時(shí)間；CT為節(jié)拍時(shí)間。

生產(chǎn)平衡率P為問題模型中對(duì)生產(chǎn)效率進(jìn)行評(píng)估的指標(biāo)，平滑指數(shù)SI用于評(píng)估負(fù)荷狀態(tài)。為最大化生產(chǎn)平衡率且不損失生產(chǎn)效率，保證各作業(yè)工作站間生產(chǎn)負(fù)荷均衡，該文將生產(chǎn)平衡率和平滑指數(shù)2 個(gè)指標(biāo)相結(jié)合，提出多目標(biāo)的裝配線平衡問題模型。該模型的目標(biāo)函數(shù)如公式（3）所示。

式中：P0為未改進(jìn)前的生產(chǎn)平衡率；SI0為未改進(jìn)前的平滑指數(shù)。

通過多目標(biāo)的裝配線平衡問題模型，可以兼顧裝配線的平衡狀態(tài)和各工位的作業(yè)負(fù)荷，提高生產(chǎn)率。

2 描述雙種群遺傳算法

2.1 遺傳算法改進(jìn)策略

遺傳算法是一種基于生物進(jìn)化思想的優(yōu)化算法，通過模擬自然選擇、交叉和變異等操作搜索最優(yōu)解。最早由John Holland 于1975 年提出，后來經(jīng)過研究者們改進(jìn)和擴(kuò)展，成為一種強(qiáng)大的全局優(yōu)化工具。

遺傳算法的優(yōu)點(diǎn)是不僅可以處理高維復(fù)雜問題，還可以并行計(jì)算，加速求解過程。然而，遺傳算法也有缺點(diǎn)，其算法的性能高度依賴參數(shù)設(shè)置和編碼方式，因此可能會(huì)陷入局部最優(yōu)解，無法保證找到全局最優(yōu)解[5]。

為改進(jìn)遺傳算法，研究者們提出許多改進(jìn)策略。其中，雙種群遺傳算法是一種基于遺傳算法的改進(jìn)版本，引入2個(gè)種群，分別用于全局搜索和局部搜索，同時(shí)兼顧全局和局部搜索的能力，有效地平衡了搜索的廣度和深度。由于雙種群遺傳算法在2 個(gè)并行的種群間進(jìn)行交叉、突變和選擇操作，因此可以更好地保持種群多樣性，從而提高全局搜索能力，同時(shí)在2 個(gè)種群中搜索最優(yōu)解，很大程度提高了計(jì)算效率。雙種群遺傳算法使用了2 個(gè)并行的種群，即使其中一個(gè)種群出現(xiàn)問題（例如喪失多樣性），另一個(gè)種群也可以繼續(xù)搜索。

雙種群遺傳算法通過引入雙種群結(jié)構(gòu)和相應(yīng)的搜索策略，利用一種有效的方式改進(jìn)標(biāo)準(zhǔn)的遺傳算法，可以處理復(fù)雜、非線性、離散以及含有許多局部最優(yōu)解的問題。

該文采用雙種群遺傳算法求解裝配線平衡問題，同時(shí)在交叉和變異環(huán)節(jié)引入自適應(yīng)算子，進(jìn)一步對(duì)雙種群遺傳算法進(jìn)行優(yōu)化，更好地求解線平衡問題。

2.2 雙種群遺傳算法改進(jìn)策略

為在搜索過程中更好地適應(yīng)問題空間的特性，該文在雙種群遺傳算法的基礎(chǔ)上引入了自適應(yīng)算子，對(duì)遺傳算法中的交叉和變異操作進(jìn)行動(dòng)態(tài)調(diào)整。

交叉是一種模擬生物繁殖的操作，通過從父母染色體中選取部分基因來產(chǎn)生新的后代。將自適應(yīng)算子引入雙種群遺傳算法后，交叉概率不再固定，而是動(dòng)態(tài)調(diào)整的，即自適應(yīng)交叉率。自適應(yīng)交叉率通常利用種群的平均適應(yīng)度或最優(yōu)個(gè)體的適應(yīng)度。當(dāng)種群的平均適應(yīng)度較高時(shí)，可能需要降低交叉率保持當(dāng)前的優(yōu)解；反之，如果種群的平均適應(yīng)度較低，可能就需要提高交叉率增加種群的多樣性。

變異是通過隨機(jī)改變?nèi)旧w上的一個(gè)或多個(gè)基因產(chǎn)生新的解。引入自適應(yīng)算子，變異率也會(huì)變成動(dòng)態(tài)調(diào)整。自適應(yīng)突變率通常利用種群的多樣性。當(dāng)種群有較高多樣性時(shí)，可能需要降低突變率保證搜索的穩(wěn)定性；反之，如果種群的多樣性較低，可能需要提高突變率增加種群的多樣性。

在遺傳算法中，常用方法是基于種群的適應(yīng)度值，引入自適應(yīng)算子對(duì)交叉率和突變率進(jìn)行動(dòng)態(tài)更新[6]。關(guān)于染色體，該文采用公式（4）更新每個(gè)染色體的交叉率和突變率。

式中：ci為染色體的交叉率；cmin和cmax分別為交叉率的最小和最大允許值，一般來說為預(yù)先設(shè)定的常數(shù)，染色體變異率如公式（5）所示。

式中：mi為染色體的變異率；mmin和mmax分別為允許變異率動(dòng)態(tài)調(diào)整的最小值和最大值，同樣也是預(yù)先設(shè)定的常數(shù)。

公式（4）和公式（5）中的f1是染色體i的適應(yīng)度值，用適應(yīng)度函數(shù)直接計(jì)算得出；fmin和fmax分別為當(dāng)前種群中的最小和最大適應(yīng)度值。

高適應(yīng)度值染色體為優(yōu)秀解，為確保有效傳遞給后代，采用較低的交叉率和變異率，有助于保留優(yōu)秀解，提高算法性能。相反，適應(yīng)度較低的染色體可能需要更高的交叉率和變異率，增加多樣性和搜索空間探索，提高發(fā)現(xiàn)更優(yōu)解的概率。這樣的策略平衡了保留優(yōu)質(zhì)解與探索搜索空間的需求，優(yōu)化遺傳算法的全局搜索性能。

同時(shí)，在問題求解初期，可以增加自適應(yīng)算子的調(diào)節(jié)系數(shù)，以便能更好地提高算法的求解能力，在后期可以適當(dāng)降低調(diào)節(jié)系數(shù)，增加收斂速度，提高算法的求解效率。

綜上所述，引入自適應(yīng)算子的遺傳算法能更好地平衡搜索的全局性和局部性，從而提升搜索性能。

2.3 改進(jìn)后的雙種群遺傳算法

雙種群遺傳算法是遺傳算法的一種改進(jìn)形式，設(shè)置2個(gè)并行的種群，在這2 個(gè)種群間進(jìn)行交叉、突變和選擇操作，提高搜索性能[8]。雙種群遺傳算法的具體運(yùn)行過程如下：1）初始化。生成種群1 和種群2，對(duì)這2 個(gè)種群進(jìn)行初始化，每個(gè)種群都由若干個(gè)染色體組成，這些染色體為可能的解決方案。該文采用順序編碼的方式，對(duì)裝配線平衡問題進(jìn)行種群初始化，將裝配線的加工順序初始化為種群中的染色體。2）適應(yīng)度評(píng)估。計(jì)算2 個(gè)種群中的每個(gè)染色體對(duì)應(yīng)的適應(yīng)度值。適應(yīng)度函數(shù)通常取決于特定的問題域，度量了一個(gè)染色體（或解決方案）的質(zhì)量或優(yōu)越性。該文采用復(fù)合的目標(biāo)函數(shù)作為適應(yīng)度值，如公式（3）所示。3）選擇。根據(jù)染色體的適應(yīng)度選擇2 個(gè)種群中的染色體。該文采用輪盤賭作為選擇策略，模擬自然界中適者生存的原則。在輪盤賭選擇過程中，每個(gè)染色體被選中的概率與其適應(yīng)度函數(shù)值成正比。計(jì)算染色體i被選中的概率Pi，如公式（6）所示。

式中：fi是染色體i的適應(yīng)度值；∑fj是種群中所有染色體的適應(yīng)度之和。

每個(gè)染色體占據(jù)的“輪盤”面積與其適應(yīng)度值成正比。因此，適應(yīng)度值較高的染色體有更大被選中的概率。該方式既能保證遺傳優(yōu)良基因，又能為低適應(yīng)度的染色體提供生存機(jī)會(huì)，從而保證種群的多樣性，避免算法過早陷入局部最優(yōu)。4）交叉和變異。從2 個(gè)種群中選擇的染色體經(jīng)過交叉和變異操作生成新的染色體。該文引入自適應(yīng)算子進(jìn)行交叉和變異操作，更好地提升了算法的性能[9]。5）替換。在新一代中，使用新產(chǎn)生的染色體替換原來種群中一些適應(yīng)度較低的染色體，達(dá)到不斷優(yōu)化種群的目的。6）遷移。在達(dá)到指定的迭代次數(shù)后，其中一個(gè)種群中適應(yīng)度值最大的染色體會(huì)復(fù)制到另一個(gè)種群中，該群間染色體交換的過程被稱為遷移。在種群1 中選取適應(yīng)度值最高的染色體，染色體包括種群1 最好的基因信息，將選定的染色體從種群1 復(fù)制到種群2，使種群2 獲得種群1 的優(yōu)秀基因信息，同時(shí)，刪除種群2 中適應(yīng)度值最低的染色體，并計(jì)算種群2 中所有染色體的適應(yīng)度值，更新種群狀態(tài)。該文采用種群1、2 間的雙向遷移，更好地促進(jìn)種群間的基因信息交流，加快全局優(yōu)化的進(jìn)程。雙種群遺傳算法的遷移環(huán)節(jié)明顯優(yōu)于傳統(tǒng)遺傳算法，其目標(biāo)是在2 個(gè)并行執(zhí)行搜索過程的種群間進(jìn)行基因信息的交流，以提高全局搜索能力，避免陷入局部最優(yōu)的困局中。7）終止條件檢查。如果滿足終止條件，即達(dá)到最大迭代次數(shù)或找到滿意解后，算法結(jié)束。否則，返回步驟2，并在新的種群重復(fù)上述過程。

改進(jìn)后的雙種群遺傳算法流程如圖1 所示。

圖1 改進(jìn)后雙種群遺傳算法流程圖

3 裝配線平衡優(yōu)化驗(yàn)證

3.1 案例描述

裝配線平衡優(yōu)化問題的目標(biāo)是使各工作站的負(fù)荷盡可能均衡，減少空閑時(shí)間和過載情況，從而提高整個(gè)裝配線的生產(chǎn)效率[7]。通過改進(jìn)雙種群遺傳算法對(duì)裝配線問題進(jìn)行求解，該文以某公司手機(jī)裝配線為案例，驗(yàn)證改進(jìn)后算法是否有效。

某公司手機(jī)裝配線將現(xiàn)有的37 個(gè)作業(yè)任務(wù)分配在4 個(gè)工位中，通過作業(yè)標(biāo)準(zhǔn)時(shí)間研究，得到37 個(gè)工位的標(biāo)準(zhǔn)工作時(shí)間。某公司手機(jī)裝配線的作業(yè)優(yōu)先順序關(guān)系如圖2 所示。

圖2 作業(yè)優(yōu)先順序關(guān)系圖

根據(jù)作業(yè)優(yōu)先關(guān)系順序圖，通過順序編碼的方式將各工序編碼成為初始化種群，并通過改進(jìn)后的雙種群遺傳算法進(jìn)行求解。代入公式（1）和公式（2）可以計(jì)算得出，目前手機(jī)裝配線的平衡率為388s，生產(chǎn)平衡率為68.81%，生產(chǎn)平滑指數(shù)為163.83。目前，生產(chǎn)平衡率在60%～70%，表示雖然該裝配線現(xiàn)在具有一定的科學(xué)管理能力，但是裝配線平衡狀況不樂觀，仍然需要進(jìn)一步改進(jìn)以達(dá)到產(chǎn)線平衡的狀態(tài)。同時(shí)，生產(chǎn)平滑指數(shù)略高，表示目前產(chǎn)線中，4 個(gè)工作站間的作業(yè)負(fù)荷不均衡，容易對(duì)生產(chǎn)效率造成較大的負(fù)面影響。

3.2 案例求解

對(duì)某公司手機(jī)裝配線進(jìn)行分析，需要進(jìn)一步優(yōu)化產(chǎn)線平衡。該文采用改進(jìn)后的雙種群遺傳算法對(duì)其進(jìn)行優(yōu)化，并與未改進(jìn)的算法進(jìn)行對(duì)比。所有試驗(yàn)均在Matlab 2021b中運(yùn)行，每次試驗(yàn)獨(dú)立運(yùn)行30 次，結(jié)果見表1。

表1 改進(jìn)后算法結(jié)果對(duì)比

由表1 可知，通過遺傳算法對(duì)手機(jī)裝配線進(jìn)行平衡優(yōu)化后，提升了生產(chǎn)平衡率。通過改進(jìn)后的雙種群遺傳算法對(duì)裝配線進(jìn)行進(jìn)一步優(yōu)化，裝配線的平衡率為92.86%，說明此時(shí)產(chǎn)線平衡狀態(tài)較好，與傳統(tǒng)的雙種群遺傳算法相比，改進(jìn)后的算法更能提升生產(chǎn)平衡率。平滑指數(shù)下降說明裝配線中各工作站間的工作負(fù)荷更均衡，與未改進(jìn)的算法相比，改進(jìn)后的雙種群遺傳算法使平滑指數(shù)下降更多。

因此，通過對(duì)某公司手機(jī)裝配線平衡狀況進(jìn)行分析，驗(yàn)證改進(jìn)后的雙種群遺傳算法能較好地解決裝配線平衡問題，比未改進(jìn)的算法性能更強(qiáng)。

4 結(jié)語

裝配線平衡問題是生產(chǎn)過程中的重要問題，通過研究，能更好地提升產(chǎn)品的生產(chǎn)效率和創(chuàng)新能力。該文對(duì)裝配線平衡問題進(jìn)行分析，構(gòu)建以產(chǎn)線平衡率和平滑指數(shù)為共同導(dǎo)向的問題模型，并通過改進(jìn)雙種群遺傳算法，提高遺傳算法的求解能力。通過對(duì)案例進(jìn)行求解，與未改進(jìn)的算法相比，改進(jìn)后的雙種群遺傳算法能更好地解決裝配線平衡問題。