增強分布估計算法求解雙邊裝配線第二類平衡問題

張騰飛，胡 蓉,，錢 斌,，張梓琪，呂 陽

（1.昆明理工大學信息工程與自動化學院,云南昆明 650500；2.昆明理工大學機電工程學院,云南昆明 650500）

1 引言

雙邊裝配線是新能源汽車、軍工等制造業(yè)中廣泛采用的生產(chǎn)方式.雙邊裝配線平衡程度決定制造系統(tǒng)生產(chǎn)率［1］，該平衡程度由生產(chǎn)節(jié)拍（Cycle Time，CT）內(nèi)各工作站的繁忙狀態(tài)決定.研究求解雙邊裝配線平衡問題的高效算法對于制造業(yè)提高生產(chǎn)效率具有實際意義［2］.

雙邊裝配線第二類平衡問題（Two-side Assembly Line Balancing Problem of type-Ⅱ，TALBP-Ⅱ）研究給定工作站前提下如何最大化生產(chǎn)效率.針對TALBP-Ⅱ，唐等［3］設計一種新穎的離散人工蜂群（Discrete Artificial Bee Colony，DABC）算法進行求解.Li［4］等利用改進迭代貪婪（Iterative Greed，IG）算法對其求解.此外，變鄰域搜索算法［5］、殖民競爭算法［6］、蟻群算法［7］等應用于TALBP-Ⅱ也取得不同程度的優(yōu)化效果.上述研究主要以CT 為優(yōu)化目標對TALBP-Ⅱ進行建模和求解.當CT 達到最優(yōu)值時，并不能保證工作站的平滑指數(shù)（Smoothing Index，SI）同時最優(yōu).由于SI 影響雙邊裝配線的負載均衡，進而影響生產(chǎn)效率.因此有必要將SI作為次級優(yōu)化目標對TALBP-Ⅱ進行建模與求解.

分布估計算法是一種基于概率統(tǒng)計的新型智能算法［8］，目前已成功用于求解傳統(tǒng)ALBP［9］、機器人作業(yè)的ALBP［10，11］、含生產(chǎn)與裝配過程的集成調(diào)度問題［12～14］.分布估計算法利用針對問題結構特點設計的概率模型來學習和積累優(yōu)質(zhì)解中的結構信息，通過采樣概率模型可生成問題的新優(yōu)質(zhì)解.這種“學習-采樣”的方法能引導算法較快地搜索到解空間中的優(yōu)質(zhì)區(qū)域.

綜上，本文針對TALBP-Ⅱ，建立以CT和SI 為主次優(yōu)化目標的排序模型，提出增強分布估計算法進行求解.在算法初始化階段，設計一種自適應策略生成初始節(jié)拍來提升初始解質(zhì)量.在全局搜索階段，設計符合問題結構特點的概率模型來學習生成解的信息，使算法能夠快速搜索到優(yōu)質(zhì)解區(qū)域.在局部搜索階段，設計適合主次目標的局部搜索策略，提升算法局部搜索能力.此外，提出利用空閑時間最大值對新解可行性進行快速判斷的方法，節(jié)省較多評價解的時間，從而提升算法搜索效率.

2 問題模型

2.1 問題描述及相關符號

TALBP-Ⅱ描述如下：在擁有m組工作站的雙邊裝配線上裝配一件包含n項工序的產(chǎn)品.同一工作站可裝配多項工序.L（R）型工序只能由工作站左側（右側）裝配.E 型工序由任意側裝配.裝配過程須滿足裝配順序約束.在此條件下，尋找使生產(chǎn)效率最大的可行解.表1為本模型中所用符號及說明.

表1 符號及說明

2.2 TALBP-Ⅱ排序模型

設集合Π中包含所有滿足TALBP-Ⅱ問題約束的可行解.優(yōu)化目標為在Π中找到一個最優(yōu)解，使該解滿足最小CT且該CT下SI也最小，即：

式（1）用于計算工作站中各工序的完工時間.式（2）用于計算生產(chǎn)節(jié)拍，iˉ表示工作站中最后一項工序.式（3）用于計算工作站的實際工作量.式（4）計算實際工作量最多工作站的工作時間.式（5）用于計算平滑指數(shù).式（6）表示在解空間中找到滿足CT最優(yōu)的解集合.式（7）表示在CT 最優(yōu)的解集合中找到滿足SI 最優(yōu)的解.

3 TALBP-Ⅱ中SI的分析與證明

在雙邊裝配線中可推導如下性質(zhì)：

性質(zhì)1給定工作站數(shù)目和生產(chǎn)節(jié)拍，若x是可行解，且工序間空閑時間為零，則CT和SI可同時優(yōu)化.

性質(zhì)3給定工作站數(shù)目和生產(chǎn)節(jié)拍，x是可行解.在滿足約束條件下，將工作站j中工作量較多側工序i移入對側.若滿足，則SI得到優(yōu)化.

性質(zhì)3證明同性質(zhì)2.性質(zhì)1指出，針對完成時間最大的工作站，減小該站IDTmax和STmax是優(yōu)化主要目標的兩種途徑.而性質(zhì)2和性質(zhì)3 指出，當主要目標達到最優(yōu)或近似最優(yōu)時，次要目標仍可能存在優(yōu)化空間.因此，性質(zhì)2 與性質(zhì)3 為進一步優(yōu)化TALBP-Ⅱ的次要目標提供了方法.綜合利用性質(zhì)1 至性質(zhì)3，可實現(xiàn)主次目標的整體優(yōu)化.

4 EEDA算法設計

EEDA 主要包括初始生產(chǎn)節(jié)拍設置方法、可行解快速判斷方法、全局和局部搜索方法.EEDA 求解TALBP-Ⅱ的算法流程如圖1 所示.生產(chǎn)節(jié)拍既作為優(yōu)化目標，同時又與生成解時約束條件有關.本文生產(chǎn)節(jié)拍約束的更新方式如圖1所示，當找到滿足約束條件的可行解時，生產(chǎn)節(jié)拍約束將縮減.該更新方式能夠保證生成新解時生產(chǎn)節(jié)拍約束始終小于歷史最優(yōu)生產(chǎn)節(jié)拍，進而使搜索過程始終沿著生產(chǎn)節(jié)拍最小化方向前進.

圖1 EEDA算法流程圖

4.1 生成初始CT的自適應策略

以a×LB(a∈(1，2))作為初始CT存在不足.例如，a取值偏大易使搜索過程變慢，a取值偏小則可能無法找可行解.為克服上述問題，本文提出一種自適應策略來生成初始CT，具體如算法1.其中，LB 表示CT 下界［3］.啟發(fā)式規(guī)則確定分配方向具體為，優(yōu)先選擇空閑時間較大一側工作站，僅當不存在滿足該側約束的工序時選擇對側工作站.確定分配工序具體為，在工序集中優(yōu)先選擇產(chǎn)生空閑時間最小的工序來分配，僅當存在多個優(yōu)先級相同的工序時隨機選擇工序.

4.2 快速判斷方法

快速判斷方法是基于問題特性，利用最大允許空閑時間來判斷生成解是否為可行解.最大允許空閑時間由式（8）計算.生成解過程中產(chǎn)生的空閑時間與最大允許空閑時間相比較，若前者大于后者，則生成解為不可行解.若生成完整解中前者小于等于后者，則生成解為可行解.通過提前判斷生成解的可行性能夠提高算法的執(zhí)行效率.

4.3 全局搜索策略

在EEDA中設計一種結合4.1節(jié)啟發(fā)式規(guī)則的采樣方法來生成問題的解，并基于該方法對問題解空間展開全局搜索.

4.3.1 概率模型

（1）建立概率模型

設π1，π2，…，πn為生成解時的工序分配排序.矩陣Pi，j，k表示三維概率模型.模型中記錄了排序中三個工序被連續(xù)選擇的概率.概率值越高，工序組合表現(xiàn)越好.

（2）結合啟發(fā)式規(guī)則的采樣方法

π1，π2由啟發(fā)式方法選擇，π3，…，πn由結合啟發(fā)式規(guī)則的采樣方法選擇.采樣方法選擇時，首先利用啟發(fā)式方法確定分配方向和分配工序.若存在多個優(yōu)先等級相同工序，則以輪盤賭方法采樣概率模型的Pi，j，k(i=πa，j=πa+1)得到工序πa+2.重復該過程能夠生成問題的解.

（3）更新概率模型

設πk與πk-2，πk-1組合后產(chǎn)生的空閑時間為idtk.若idtk=0，則應用式（9）獎勵若idtk＞0，則應用式（10）懲罰重復k=(3，4，…，n)能夠學習生成解中三個連續(xù)工序的組合信息.

4.3.2 生成種群

在EEDA 中，種群大小設置為PS.種群中γ%個體從工作站j繼續(xù)生成解，j為不滿足快速判斷方法時記錄的工作站.其余個體從首個工作站生成解.生成種群過程如算法2.

4.4 局部搜索策略

生成種群后，首先采用針對主要目標的搜索策略，若該策略在連續(xù)三次種群迭代間未能更新CT，則采用針對次要目標的搜索策略.兩種搜索策略的處理對象均為歷史最優(yōu)解.

4.4.1 針對主要目標的搜索策略

給定工作站數(shù)目和生產(chǎn)節(jié)拍，工序分配排列π1，π2，…，πn為滿足約束的歷史最優(yōu)解.縮減生產(chǎn)節(jié)拍使πk分配至工作站j后生成非可行解.設πt為工作站j首個工序.考慮到工作站j之前的所有工作站已取得滿足約束的部分解，為避免這種優(yōu)質(zhì)結構被破壞，隨機地從πt，…，πk中選擇工序插入其后工序來產(chǎn)生新解，并判斷新解是否為可行解.該策略如圖2所示.在每次啟用時該策略執(zhí)行10次.

圖2 針對CT的局部搜索示意圖

4.4.2 針對次要目標的搜索策略

由式（5）可知，工作量偏差較大的工作站相比偏差較小的工作站存在更大的優(yōu)化空間.因此，本策略針對偏差值最大工作站進行操作.如圖3 所示，首先計算所有工作站兩側的偏差值，隨機地從偏差值最大工作站中選取工序向后續(xù)工序做插入調(diào)整，然后判斷新解是否為可行解及是否更新SI 且不降低CT.本搜索策略在每次啟用時執(zhí)行3次.

圖3 針對SI的局部搜索示意圖

5 實驗分析與比較

實驗中問題實例源于Kim 等［15，16］的研究.所有測試由Delphi7 編程實現(xiàn).CPU 為2.33 GHz，內(nèi)存為8 GB.每種算法單次實驗的運行時間設置為n×n×15 毫秒.每種問題實例獨立地進行20 次實驗，取結果的平均值作比較.

5.1 參數(shù)設置

EEDA主要參數(shù)為種群規(guī)模PS、精英個體占比γ、獎勵系數(shù)α和懲罰系數(shù)β.采用實驗設計方法確定參數(shù)取值為PS=50，γ=0.5，α=0.7，β=0.3.

5.2 EEDA關鍵環(huán)節(jié)有效性驗證

5.2.1 驗證自適應策略生成初始CT有效性

表2為實驗結果.CTDABC表示DABC 算法在相同時間內(nèi)計算獲取的CT.DABC 算法中參數(shù)設置方法為考慮不同結構特點的問題實例將起始CT 設置較大，導致算法自較高起點“自上而下”尋優(yōu)，而EEDA中自適應策略采用“自下而上”的方式確立初始CT.在大規(guī)模問題實例上，只需百次左右迭代即可生成可行的初始CT.因此自適應策略在生成初始CT較參數(shù)設置方法有優(yōu)勢.

試驗和實際使用表明：鉆機車在坡度行駛時，可通過液力緩速器和發(fā)動機制動聯(lián)合作用使車輛在下坡過程中選擇合適檔位，降低車速。具體過程如下：首先打開緩速器開關(液力緩速器功能激活)，操縱緩速器桿，它共有7個檔位選擇，制動強度依次增加，可根據(jù)下長坡路段的駕駛操控情況選擇合適的制動檔位，該操縱桿只有在松開油門的情況下才能起作用。

表2 大規(guī)模問題實例下初始CT設置方法的實驗結果

5.2.2 驗證結合啟發(fā)式規(guī)則采樣方法的有效性

將EEDA與其變體Rand_EEDA、Heuristic_EEDA進行實驗比較，Rand_EEDA和Heuristic_EEDA 分別采用隨機方法和啟發(fā)式方法選擇工序.表3 實驗結果表明，Rand_EEDA、Heuristic_EEDA和EEDA 的性能依次增強.相比隨機方法，由于啟發(fā)式方法能從產(chǎn)生空閑時間最小工序集中隨機選擇工序，所以啟發(fā)式方法能夠生成較優(yōu)解.而EEDA 利用概率模型從產(chǎn)生空閑時間最小工序集中選擇工序，能夠生成更為合理的工序排列，從而能獲得更好的優(yōu)質(zhì)解.

表3 三種工序選擇方法的實驗結果

5.3 EEDA與其他算法對比

為進一步驗證EEDA 性能，將EEDA 與求解TALBP-Ⅱ的有效算法DABC［3］、IG［4］和GA［15］對比.表4和圖4 為實驗結果.各算法在CT 指標上性能近似，但在SI 指標上EEDA 明顯占優(yōu).其他比較算法僅在已有的進化算法框架或IG算法框架中加入一些通用搜索操作，故這些算法實際性能較為有限.EEDA 采用基于三維概率模型的EDA 算法框架，可合理學習優(yōu)質(zhì)解信息并避免其他比較算法存在的優(yōu)質(zhì)解模式破壞問題［17］，從而能更好地引導算法搜索方向.同時，EEDA 進一步考慮問題特性，設計并引入了新穎有效的新解生成方法、主次目標協(xié)同優(yōu)化的局部搜索方法、可行解快速判斷方法.這使EEDA 具有更強的搜索效率，故能在算法對比中明顯占優(yōu).

圖4 對比算法實驗結果的區(qū)間圖比較

表4 各對比算法在各種問題實例下的實驗結果

6 結論

針對雙邊裝配線第二類平衡問題（TALBP-Ⅱ），將生產(chǎn)節(jié)拍（CT）和平滑指數(shù)（SI）作為主次優(yōu)化目標，提出增強分布估計算法（EEDA）對TALBP-Ⅱ求解.具體結論如下：（1）采用自適應策略生成初始CT，可提升初始解質(zhì)量；（2）設計結合啟發(fā)式規(guī)則的采樣方法，可提高生成優(yōu)質(zhì)解的概率；（3）利用主次目標協(xié)同優(yōu)化的局部搜索方法，可增強算法局部搜索能力；（4）提出可行解快速判斷方法，能縮短算法每代的運行時間從而提升算法搜索效率.