面向混流生產線排序問題的改進回溯搜索算法*

張天瑞，王譯可，謝 薇，徐佳楠，王瑞麟

(1.沈陽大學機械工程學院，沈陽 110044；2.烏普薩拉大學土木與工業工程系，烏普薩拉 75261)

0 引言

多品種、小批量混流生產方式能快速響應市場需求[1]，但由于復雜的工藝和產品的多樣性增加了生產系統的復雜性，導致混流生產線生產效率低下[2]。混流生產線高效生產過程中工件排序最為重要，計算過程的復雜性極高[3]。早期，學者們主要采用線性規劃等方法求解，但由于其解決能力有限，僅能解決小規模排序問題[4]。近來，學者們以禁忌粒子群等智能算法對生產排序優化[5]， Tahriri F等[6]將遺傳算法用于設置最小化混合模型裝配線中的時間和成本；采用根據隨蜂形式的精英保留策略，保證了一定的全局收斂能力[7]；劉瓊等提出了一種改進的基于貓的行為模式線性混合比率的多個目標貓群體優化[8]；Zandieh M等[9]采用一種新的帝國主義競爭算法，確定最小完工時間和加工成本的混流生產排序問題；季樹榮提出了一種基于混合蛙跳算法裝配線排序研究[10]；劉冬等提出了一種改進粒子群算法[11]。

以上文獻中，平衡和生產排序是混流生產的核心問題。在解決實際問題時，傳統的優化方法面臨解決求解時間過長的瓶頸，所以目前主流方向使用粒子群等啟發式算法解決該類問題，但此類算法在求解過程中也存在收斂速度慢或全局搜索能力不足的局限性[12]。然而，回溯搜索算法因其較快的搜索速度和較強的全局搜索能力被廣泛應用于各個領域[13-14]，但在混流生產平衡排序研究應用較少。綜上所述，本文考慮組件消耗平衡，完成時間和產品切換調整時間構建以各個工作站的零件數使用率的最大化和總體的均準化為目標的函數模型，引入相應的系數，對模型進行加權求解；同時提出一種改進多目標回溯搜索算法，引入自適應變異尺度系數和數值擾動變領域搜索方法提高算法的收斂速度和搜索能力。

1 混流裝配線排序問題描述與分析

企業在選擇混裝線投產順序的優化目標時，應從實際出發進行有針對性考察，以免計算結果出現偏差[15]。目前主流投產排序目標包括：①保持各部件消耗率均衡；②單個工作站實現最少裝配時間。本文以前者為排序目標。

本文假設已經解決混流裝配線平衡問題，只分析產品的交付順序，以達到各個工作站的零件數使用率的最大化和總體的均準化的目標。為了便于模型建立與分析，給定圖1所示裝配工序示意圖。

圖1 產品相應映射位置示意圖

2 問題模型構建

T表示每天生產的車型種類，Di為每天各車型的需求量，d表示每種車型的最大公因數，ri在一次生產中第i種車型生產的投產數量。

(1)

所以得到各個車型投產數量比為r1:r2:r3:…:rT，每T種車型的需求總數為：

(2)

在最小生產周期中，不同的型號要求在生產裝置中使用組件j的總和為：

(3)

為了使各個零件j的消耗速度保持平衡，有必要在以前的k輛汽車生產中制定以前的調度計劃，對零件j的實際需求量Vjk與理論上生產k輛汽車時零件j的需求量k·Q/R盡可能一致。使差異值最小化，定義操作差異值為：

(4)

車輛類型數量及零件清單如表1所示。

表1 車型數量及零件清單

續表

nij：表示在周期內，生產車型為i的車輛所需的組件j的數目；

Qj：表示裝配全部車型一共需要組件j的數量，比如Q1表示在全部T種車型對零件1的需求總量；

ri：指一個最小單位中不同種車型的數目，其中i表示車型的類別，因此Qj用公式表示為：

Qj=n1j·r1+n2j·r2+…+nTj·rT

(5)

一個最小生產x循環中對零件j的理想用量為：

(6)

假設生產線上第一批k臺車零件j的實際需求為Vjk，然后，可以表示為前k-1輛汽車對零件j的實際總需求量加上第k個車型i時對零件j的總需求量，用數學表達式表示為：

Vjk=Vj,k-1+Xik×nij

(7)

由上可得，該混合生產線前k輛汽車車型對零件j實際與理想使用量差值的二次方求和，目標函數如下式所示：

(8)

(9)

(10)

(11)

其中，式(9) 表示排序中，只能在前k個位置中的任何一個位置進行組裝生產一輛汽車；式(10) 表示排序中，前k個位置對車型i的排序量不能大于最低單位巡回內i車型的總需求量；式(11) 表示在全部數量的汽車(共R輛)均參與到投產排序過程中。

3 改進的回溯搜索算法

回溯搜索算法(Backtracking Search Algorithm, BSA)，是一種基于種群的自然啟發式算法，BSA的回溯功能保證了種群多樣性和優越性，使其具有很強的全局搜索能力，但缺乏超前性，使算法后期局部挖掘能力減弱，影響收斂速度。此外，BSA變異大小系數設置范圍波動過大，如果設置不當，會導致算法過早收斂，陷入局部解。為了解決BSA算法的局限性，將BSA算法進一步進行改進。

在變異步驟中，為提升迭代后期的局部搜索能力，有學者用歷史種群中的最優個體進行引導[16]。在多目標優化問題中并沒有絕對意義上的最優個體，故本文提出使用多權重下最優個體精英化歷史種群，再用其引導當前種群進化的方法。目標函數選取最大完成時間l、總耗能m、平均完工時間n個權重值，可搭配出l×m×n種加權函數，在歷史種群中尋找每種加權目標函數下的所有最優個體替換歷史種群中其它個體，即可完成對歷史種群的精英化，且保留了歷史種群的多樣性。

3.1 自適應變異尺度系數

在變異步驟過程中，選擇較大的可控制變異程度系數F值，會導致種群形式增加，收斂速度持續降低；而選擇較小的F值則相反。為了在早期的算法種群中保證形式多樣性，同時對算法后期中的收斂速度保持增加，所以提出了自適應變尺度系數[17]。本文對其進行了簡化，使F按公式(12)隨迭代次數的增加而呈減小趨勢，其中N(0，3)為服從(0，3)正態分布的隨機數，n為迭代次數，C為常數。

F=N(0,3)×exp(-n/C)

(12)

3.2 變鄰域搜索

本文提出一種數值擾動變鄰域搜索方法，使算法在局部搜索中能力增強，并對算法交叉步驟中生成的試驗種群V使用這兩種方法進行變鄰域搜索。

首先，對原序列上的實數編碼加入數值擾動，使其產生與原解碼結果相鄰的解碼結果。生成一個h×(1+m+w)×N的服從(0，3)正態分布的隨機數矩陣R和一個(H-h)×N的零矩陣Z。將其合成為H×(1+m+w)×N的擾動矩陣D，則擾動后的種群Q*和原種群Q的關系為：

Q*=Q+D

(13)

其次，從工序排序、機器選擇和工人指派問題上，隨機從種群中選取個別個體，各隨機選擇兩道工序，交換其在生產線上對應的編碼，如圖2所示。

圖2 混流生產線上交換工序位置編碼示意圖

3.3 按非支配等級更新當前種群

基于精英策略的非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm II，NSGAII)[18]采用快速非支配排序，選擇一個非支配水平低的個體可以保證種群精英化。依據非支配等級確保優秀個體更新至當前種群。具體步驟如下：

步驟1：將種群P和種群V混合；

步驟2：將其中所有個體按其ID分組；

步驟3：對各ID進行快速非支配排序；

步驟4：按非支配等級從低到高逐層將各ID對應的個體更新至當前種群，待更新個體數小于當前所在支配等級數時，每從該層非支配等級的各ID中選出一個個體更新到當前種群，直到更新完成。

3.4 算法流程

改進多目標回溯搜索算法(Improved Muti-Objective Backtracking Search Algorithm，IMOBSA)的算法流程如圖3所示。

4 混流裝配線實例問題研究

4.1 某汽車公司混流裝配線分析

B公司的整車混流裝配生產線及其所在的生產系統均推行豐田生產方式滿足個性化制造以及多車型共線生產的需求，且所有生產流水線生產類型、組織方式均一樣。

圖3 IMOBSA流程圖

該公司現有3系標準軸版轎車和長軸版轎車與5系標準軸版轎車和長軸版轎車在裝配線上混流生產組裝，在本文中將這三種類型的汽車編號為A、B、C、D，現己明確在一個生產周期內要生產裝配出A型車4臺，B型車3臺，C型車2臺以及D型車3臺，(即A：B：C：D=4：3：2：3)，如表2表示某天某批次生產計劃。

表2 某天某批次生產計劃

給定兩個方案：12輛汽車在總裝線上需要的主要結構部件有5種，同時安排5個工作站進行裝配生產，每個作業站僅對應一種零件；12輛汽車在5個作業站上依次進行裝配工作。在一個最小生產周期內，5種主要構件的總需求量分別為：74、74、73、54、52，每當需要某個零件時，5種主要零部件能夠準時送達各個工作站的零件緩存區。

模型假設：

(1) 這兩種方案都確保各方同時組裝的汽車數量相等；

(2) 每個作業站上安裝不同種類的汽車的時間都相同；

(3) 不會出現作業超時的情況。即在各個工作站里每個組件都能夠在計劃的時間點里安裝完成。

B公司對該系列4種車型進行總裝，每種車型所必須的種類元件的數量如表3所示。

表3 種類元件的數目

4.2 IMOBSA的排序方案

根據目標函數(8)可知，目標函數越小表示排序方案越合理。根據約束函數，編碼方案為[ 1 1 1 1 2 2 2 3 3 4 4 4 ]。在一個最小生產循環中，全部產品A(i=1 , . . . ,T)的總產量為：

求得dj：

將數據帶入回溯搜索算法求得，當k=1，i=3時Dij值最小，即首先將C車型在這個最小生產循環內進行投產排序。表4表現了最小生產循環內各個目標值。

表4 最小生產循環內各個目標值

5 算法驗證

本文根據 Python 2.7 編程進行建模，所使用計算機的處理器型號為Intel(R)Core(TM) i5-5200U CPU 2.2 GHz，內存8.0 GB。為了與其他算法在同一水平上進行比較，本文的大部分主要參數都與傳統的遺傳算法中的部分參數一致。算法參數具體設置：種群個數設置為10，交叉概率Pc=0.8，變異概率Pm=0.1，其中歷史種群、父代種群、實驗種群的個數相等，最大迭代次數設置為5000。如下結果分別為IMOBSA、BSA和GA，算法計算10次并進行比較的適應度值結果如圖4所示。

圖4 IBSA、BSA、GA 算法運行10次的適應度值結果

由圖4可知，在解決裝配線問題上，BSA和IMOBSA算法的收斂效果比GA算法的好，而IMOBSA算法運行10次的結果大部分都比BSA算法的要好，證明了改進后的BSA算法具有更好的收斂效果。IMOBSA算法第7次的運算結果是最好的，BSA算法的第10次運算結果是最好的，GA算法的第 9 次運算結果最好。

根據3種算法計算所得的最優解適應度值收斂曲線如圖5所示，由圖可知，GA算法在圖中顯示雖然具有很快的收斂速度，但是最優適應度值不理想。而改進后的IMOBSA算法比未改進的BSA算法更有優勢且效果更好，既避免了算法的早熟收斂，也提高了收斂速度。

圖5 三種算法的最優解適應度值的收斂曲線

6 結論

本文針對復雜產品混流生產線生產效率低下的問題，考慮組件消耗平衡、完成時間和產品切換的調整時間等因素，以各個工作站的零件數使用率的最大化和總體的均準化為優化目標，對某汽車制造企業的混流生產線排序進行優化。

(1) 針對BSA存在隨機性強導致算法后期局部挖掘能力變弱，以及變異尺寸系數設置范圍波動過大的特點，應用自適應變尺度系數和數值擾動變領域搜索方法對BSA進行了改進，設計了IMOBSA算法流程，提高了算法的搜索能力。

(2) 將改進多目標回溯搜索算法用于某混流裝配線的作業排序問題，得到了較好的排產結果，可為混流生產線排序提供參考依據。

(3) 采用Python 2.7編程，將改進算法與回溯搜索算法、遺傳算法生成的排產方案進行比較，結果表明，改進算法效率更高，早熟收斂程度低，收斂速度快。