電子裝配物聯制造中智能排程算法研究

蔣 城，蔡晉輝

（1.杭州鴻雁智能科技有限公司，浙江 杭州 310007；2.中國計量大學，浙江 杭州 310018）

0 引言

隨著物聯制造車間的發展，智能排程算法受到重視，產生了很多新的算法，如：領域搜索技術[1]、模擬退火算法（SA）[2]、禁忌搜索算法[3]、遺傳算法[4]、神經網絡技術[5]、蟻群算法[6]、粒子群算法[7]、蜂群算法[8]、螢火蟲算法[9]、蛙跳算法[10]等。

其中，遺傳算法（GA）以其全體搜索策略和群體中個體信息交換特點，被廣泛應用于求解車間調度問題。國內外學者對遺傳算法做了大量的研究，在Reeves[11]驗證了遺傳算法的優越性后，Murata[12]將局部搜索引入遺傳算法中，形成基于遺傳算法求解車間調度問題的框架。之后遺傳算法的調度優化成為研究重點。例如，王金鵬[13]運用最優子群遺傳算法來求解柔性流水車間問題，王軍強[14]設計了多樣性判定增強算子，分析算子時間復雜度，對自適應遺傳算法進行優化求解。王蕾等[15]以加工完成時間、機器損耗、員工操作舒適度為多目標函數，改進遺傳算法。

但遺傳算法存在局部搜索能力較差，易產生“早熟”收斂的問題，單純對遺傳算法進行優化很難解決這些問題，研究人員將遺傳算法與其他算法結合，以取得更好調度結果。程子安等[16]提出雙種群機制，分別負責全局搜索和局部搜索，并設計相關遺傳算法來彌補局部搜索能力不足的問題。趙詩奎[17]設計了一種兩級領域搜索混合算法，利用遺傳算法搜索全局變量，對兩級領域算法進行改進，實現局部搜索。但這些改進算法存在設計復雜，耗時長等問題，且多針對機械化調度排程，本文以電子企業裝配車間為研究對象，針對員工車間排程設計了改進遺傳退火算法（GASA），在算法中加入了最優解存儲器，能夠保證適應度值一直往最優化方向發展，克服遺傳算法易早熟，以及模擬退火算法波動幅度大、搜索速度慢的缺點。

1 車間排程數學模型建立

本文智能排程的實質是對電子企業車間裝配生產線員工的生產調度分配。假設生產線加工裝配過程共有m位員工，加工的產品共有n種，形成產品集合J，員工集合M，工序集合O。所有產品加工時間可以用時間矩陣T來表示，矩陣T每一行代表一種產品，每一列代表一道加工工序，未經過的工序用0表示，矩陣T可以表示為：

上式中，產品1生產過程共需要n1道工序，每道工序的加工時間分別為T11、T12…T1n，產品i生產過程共需要ni道工序。因為各道工序在不同員工Mk加工時間不同，所以各加工時間值不固定，因此才有生產調度的必要，以期求出最優解。

本文首先在滿足約束條件并且不考慮其他擾動因素的情況下，建立裝配生產車間調度模型。為追求所有產品的最大完成時間最短，產品的總加工時長可以用T1表示，表達式為：

其中，Ciek表示產品Ji在最后一道工序加工完成的時間，即該產品總加工時間。在實際應用中，還需將滿足交貨期限的指標放入模型中。客戶對產品交貨期的需求，可以用滿意度指標E/T指標T2表示，表達式為：

要使產品交貨期控制在客戶期望交貨區間內，提前和延后都會使調度結果不能最優化，所以設定產品i的提前懲罰系數αi和延后懲罰系數βi。T2值越小，表明產品交貨期越接近客戶期望交貨區間，客戶滿意度越高。生產調度的總目標函數可以表示為： min[T1，T2]

2 改進遺傳退火算法設計

傳統遺傳算法為保證基因的多樣性，引入變異操作以避免某些基因缺失。但實驗證明遺傳退火算法在進化后期，進化會因變異操作而出現較大的波動。而遺傳退火算法中模擬退火可以保證基因的多樣性，而不需引入變異操作。遺傳退火算法可以分為以下四個步驟：確定問題的編碼方案、確定適應度函數、設計遺傳退火算子、設置算法參數。

2.1 染色體編碼和解碼設計

表1 3×3調度問題基礎數據表

假設給定染色體[2 3 1 3 2 2 1 3 1]，數字表示產品J1，每個數字產生幾次表明該產品有幾道工序。再根據表1基礎數據表的對應關系，可得到其加工所需時間。以此類推，最終得到該染色體對應的員工列表為[M2M1M3M3M1M3M1M2M2]和對應的時間列表，最終得到染色體解碼操作表，如表2所示。

表2 染色體解碼操作表

根據該解碼操作表可得到可行調度方案如圖1所示。

圖1 基于工序編碼的可行調度

2.2 適應度函數設計

本文選用倒數選取法構造適應度函數。目標函數為最小值問題的適應度函數為：

式（1）中，T（t）為關于種群中第 i個優化方式總加工時間的函數。

2.3 遺傳退火算子設計

遺傳退火算子的設計包括以下部分：

2.3.1 選擇算子

選擇操作是將優良個體從父代種群中挑選出來，保留到子代，個體適應度值是判斷個體優良性的重要依據。本文采用賭輪法進行選擇操作。

遺傳選擇算子公式為：

式（2）中，f（xi）為個體適應度值，Pi為個體被選中概率。

退火選擇算子公式為：

式（3）中，t為退火溫度，favg為當前種群平均適應度值。

2.3.2 交叉算子

本文設計了一種以產品工序作為基因片段的交叉方式，具體步驟如下：

步驟一：首先隨機選擇兩個個體P1、P2，隨機選擇個體中兩個產品J1、J2將個體染色體中兩個產品所有基因按照原順序重新組成新基因片段A1、A2，在P1、P2中被提取的位置用0代替，如下所示：

步驟二：將新基因片段調換順序，依次替換掉對方個體中為0的基因片段，產生新的子代個體B1和 B2，如下所示：

步驟三：把子代B1、B2所有基因反序排列，得到最終個體C1、C2，以提高種群多樣性，避免遺傳算法早熟收斂，如下所示：

2.3.3 最優解存儲器

最優解存儲器用來記錄調度過程中遇到的最優解，存儲器主要包括兩個部分p*和f*，p*用來存儲最優解，f*用來存儲該最優解的目標函數值。在算法運行過程中，產生的優秀個體目標函數值f與存儲器中已有最優解目標函數值f*比較，若f優于f*，則p*=p，f*=f，以此保證優化結果為最優解。

2.4 算法參數設置

在調度算法開始運行之前，需要對算法參數進行設置，主要包括以下幾個方面：

（1）種群大小 N

（2）編碼串長度 l

（3）交叉概率 pc

本文設計的交叉概率與適應度值相關聯，當個體適應度值大于種群平均適應度值時，應盡量保留該優秀個體，pc值應較小，反之則應較大，具體計算公式為：

式（4）中，fmax為種群最佳個體適應度值，favg為種群平均適應度值，f為兩個要交叉個體中較大的適應度值，k1、k2為交叉概率調整系數，取k1=k2=1。

（4）終止條件

設定如果進化達到最大代數N或者當溫度降低到給定終止溫度Te時，算法終止，停止進化，返回最優解。

（5）初始溫度 T0

初始溫度影響全局搜索能力，溫度越高搜索能力越強，但所用時間也越長。在實際車間調度問題中，T0的取值公式為：

式中，fmax、fmin分別為初始種群中個體適應度值的最大值和最小值，r取10。

（6）退溫函數

退溫函數采用指數函數的方式進行退溫，能夠保證后期緩慢降溫，退溫函數為：

式中，T0為初始溫度，降溫系數a取0.9，k為循環次數。

2.5 遺傳退火算法流程

遺傳退火算法的設計步驟如下：

步驟一：建立目標函數，確定適應度函數。

步驟二：初始化算法參數：種群大小N、交叉概率 pc、初始溫度 T0、降溫系數 a。

步驟三：編碼產生初始種群P0，令i=0，k=0。

步驟四：采用賭輪法選擇個體，按照自適應交叉概率pc執行交叉操作，更新存儲器中的f*和p*，生成新的臨時種群S。

步驟五：新的臨時種群S作為模擬退火算法的初始種群，對種群中各個個體進行模擬退火操作，計算種群中染色體適應度，更新存儲器中的f*和p*。

步驟六：判斷是否滿足終止條件，如是，則輸出最優解并結束算法；否則轉步驟四。

遺傳退火算法的流程如圖2所示。

圖2 遺傳退火算法流程

3 實驗結果及分析

3.1 調度問題理想狀態甘特圖

為驗證算法的有效性，采用Job-shop benchmark基準問題做對比。本文采用FT06基準問題數據來驗證遺傳退火算法的有效性。算法初始運行參數設置為：種群規模N=50，交叉概率pc=0.7，初始溫度T0=100℃，終止溫度Te=0.01℃，降溫系數a=0.9，最大迭代次數G=100。整理后得到6×6調度問題基礎數據，整理后數據如表3所示。

表3 6×6調度問題基礎數據表

根據本文設計的GASA算法運行結果，得到其中一個最優染色體為[5 6 1 2 6 3 4 1 6 4 3 5 1 4 5 6 4 1 5 2 6 5 1 3 2 4 5 6 1 2 3 2 3 4 2 3]。通過GASA算法得到的最優染色體需要的加工時間為55秒，對于FT06問題，6×6規模的最優目標函數值f*=55，因此達到該問題最優解，驗證了算法的有效性。最優解調度甘特圖如圖3所示。算法收斂曲線如圖4所示。

圖3 最優解調度甘特圖

圖4 算法收斂曲線

從圖4中可以看出，經過50次迭代后，遺傳退火算法最終收斂，得到的最優適應度值為55。表明改進遺傳退火算法有較快的搜索速度和較高的搜索精度。為更直觀的比較GASA算法、GA算法和SA算法，分別對基準問題進行求解，得到它們的收斂曲線，如圖5所示。

圖5 三種算法收斂對比圖

從圖5可看出，SA算法和GASA算法都能達到最優解，但分別在76代和50代時完成收斂找到最優值，表明改進模擬退火算法收斂速度更快，并且SA算法在迭代初期波動幅度很大，而GASA算法由于在算法中加入了最優解存儲器，能夠保證適應度值一直往最優化方向發展。對比GA算法和GASA算法，可以看出GA算法在19代時完成收斂，但并未達到全局最優解，表明GA算法在進化過程中容易陷入“早熟”，得到局部最優解。綜上所述，遺傳退火算法在進化過程中收斂平滑，收斂速度適中，全局最優解搜索能力強，能夠克服遺傳算法易早熟的缺點，又能克服模擬退火算法波動幅度大搜索速度慢的缺點，驗證了算法的有效性和優越性，符合本文設計目標。

3.2 實際情況下調度甘特圖

上文給出的最優解是在理想狀態下得到的，但在實際生產過程中經常出現各種干擾因素，如電子企業經常出現臨時插單的情況。為應對該情況，本文將臨時訂單到來時刻作為再調度的初始時刻，將臨時插單數據輸入到初始時刻，對于在此刻加工的產品及工序不做打擾，對產品未完成的工序進行再調度。例如，在圖3理想狀態調度甘特圖時刻為30min時，出現臨時訂單，需要優先加工產品J7，要求該產品必須在30分鐘之內加工完成，其基礎數據如表4所示。

表4 臨時插單產品基礎數據表

按照臨時插單調度優先的規則，若不采取再調度，則每位員工在該產品經過自己工序時，需要優先加工該產品，此時的總加工時間為66min，產品J7加工完成時刻為56min，加工用時26分鐘，其甘特圖如圖6所示。采取臨時插單再調度后，產品總加工時間為63min，產品J7加工完成時刻為60min，加工用時30分鐘，在滿足30分鐘內加工完成這一約束性目標的前提下，使各產品總加工時間最小化，其甘特圖如圖7所示。

圖6 未采用臨時插單的調度甘特圖

圖7 采用臨時插單的調度甘特圖

理想狀態最優調度甘特圖適用于客戶對交貨期不做更改的情況，但在實際生產過程中，部分客戶可能在加工階段對產品交貨期做出改變，此時需要在原調度方案的基礎上，改變員工加工產品的順序，以滿足產品交貨期更改需求。例如客戶在時刻為30min時對產品J3期望交貨期提出修改，將該產品交貨期提前至[45，50]之間，進行再調度后，產品J3的加工完成時刻提前至46min，其調度甘特圖如圖8所示。

圖8 交貨期提前的調度甘特圖

4 總結

本文針對電子裝配車間自動化水平低、生產以人工加工裝配為主的實際生產情況，適應物聯制造建設需要，研適用于人工生產的智能排程方法。首先對車間生產調度問題進行分析并建立多目標調度模型。其次根據模型設計了改進遺傳退火算法，研究了算法實現的過程以及各參數的設定，并給出了遺傳退火算法的具體流程。最后利用Job-shop benchmark FT06基準問題作對比，驗證了改進算法的有效性，給出了最優解調度結果及其甘特圖。同時針對實際生產過程中出現的臨時插單和交貨期提前事件，給出了再調度方法及其甘特圖。排程計劃最終通過生產任務的派工執行實現電子裝配企業員工生產效率的提升。