改進離散粒子群算法及其在飛機裝配任務調度中的應用研究

韓鵬飛 ， 孫占磊， 趙 罡

（北京航空航天大學，北京 100191）

改進離散粒子群算法及其在飛機裝配任務調度中的應用研究

韓鵬飛 ， 孫占磊， 趙 罡

（北京航空航天大學，北京 100191）

論文闡述了飛機裝配過程中任務調度的重要意義，介紹了當前調度算法的研究現狀，對離散粒子群優化算法進行研究并在此基礎上提出一種基于激勵原則的改進離散粒子群優化算法。最后以某型飛機尾段裝配流程為對象對改進后的算法進行驗證，得到良好效果。

飛機裝配；任務調度；改進離散粒子群優化算法；激勵原則

裝配是飛機制造的重要環節，它是將大量的飛機零部件按圖紙、技術條件進行組合、連接的過程，具有生產周期長、工藝難度高、零部件及連接件數量多等特點，其質量、效率直接影響著整機的性能指標和生產成本。近年來，為滿足國防戰略需要和市場競爭要求，飛機結構日趨復雜，導致裝配復雜度不斷提高、作業數量日益增加，批量裝配階段訂單無法按時交付、現場生產能力不足等情況時有發生。究其原因，是在現場控制上缺乏有效的任務調度方法。

裝配車間中的操作人、工裝夾具、加工設備、操作空間等可統稱為“資源”，裝配任務可以作為一個整體被資源執行。任務調度的目標是實現資源與任務的優化配置，將不同批次裝配任務限定在訂單規定的時間范圍內并且最大程度地提高資源利用率。而決定任務調度方法優劣的核心是優化算法的設計。目前常用算法有：① 運籌學方法，如 Tozkapan等人建立的兩階段裝配調度問題的分支界定算法[1]；② 基于規則的方法，如Jeffcoat等人總結的113條調度規則[2]；③ 排序方法，包括局部探索、模擬退火、遺傳算法、離散粒子群算法、神經網絡優化算法等[3-4]。其中，離散粒子群算法收斂速度快、調整參數少、易實現、易理解，在解決組合優化問題上已經取得一些成果[5]。而飛機裝配流程具有多批次、多任務、裝配資源成本高昂等特點，對任務調度的優化實際是將任務與資源進行合理地排序和組合的過程，故可以借鑒離散粒子群算法的思想進行解決。

本文對離散粒子群優化算法進行研究，并在此基礎上提出一種基于激勵原則的改進離散粒子群優化算法，最后以某型飛機尾段裝配流程為對象對改進后的算法進行驗證，得到良好效果。

1 粒子群算法

1.1 粒子群算法

Kennedy和Ebelltart從鳥群覓食的行為中得到啟示，提出了粒子群優化算法(Particle Swarm Optimization，PSO)[6]，算法尋優的過程模擬鳥群的覓食過程。算法應用時，鳥群中的每一只鳥被抽象為粒子群中的一個粒子，食物抽象為問題的解，使用速度位移更新公式模擬鳥群的信息共享機制。距離食物最近的距離被抽象為全局最優解，每一只鳥對食物最好位置的理解抽象為局部最優解。算法運行時，在每一次迭代過程中，每一個粒子通過跟蹤全局最優和局部最優解兩個值，使用速度和位移更新公式，不斷更新自身的位置和速度，直至整個粒子群找到最優解。粒子群算法的形式化描述如下：在N維搜索空間中，存在m個粒子組成的種群，種群中的第i個粒子的位置表示一個N維向量i= 1,2,… ,m。第 i個粒子的速度表示為速度和位移的更新公式如式(1)

其中 c1、 c2為學習因子，分別控制粒子的當前速度向局部最優和歷史最優解進化的程度。為（0，1）間的常數。為局部最優解，為全局最優解。

1.2 離散粒子群算法

上述粒子群優化算法是為解決連續空間上的問題而設計，但是現實生活中依然存在大量的基于離散領域的問題需要解決，這時傳統的粒子群優化算法就不再適用。為此學者們對其做了進一步的改進，定義了基于置換因子概念的離散粒子群算法(Discrete Particle Swarm Optimization，DPSO)[7-8]。

在該算法中粒子的位置 X定義為解序列＜n1, n2,… ,nn＞,n =1,2,… ,n 。速度定義為置換因子的集合 V = {( ni, nk),…} 。定義置換因子表示交換序列中第i、k位置上的元素為局部最優解，為全局最優解。速度和位移的更新公式被重新定義，如式（2）

公式中的相關運算說明如下：

1） 位置與速度的加操作：速度的置換序列作用于位置，結果為一個新的位置。如

2） 位置與位置的減操作：結果為一組置換序列，表示為速度。如：則 Xi要變換為 Xj需執行減法操作

3） 實數與速度的乘法：形如c? V。速度的長度為置換序列的個數，表示為乘法操作是從左至右截取置換因子，使得新速度的長度，結果取整數。如則

5） ω為慣性權重。研究表明其按下式進行變化比較可行[9]。其中為慣性權重的組最大值為慣性權重的組最小值0.4，L表示當前迭代次數，表示最大迭代次數。

6）1c、2c為（0,1）間的常數。

2 算法分析與改進

2.1 DPSO物理模型抽象映射

DPSO算法是將某一解序列中的離散元素（本文中每個元素為一條任務流程）不斷調整排序，每一次排序后依據預先設定的目標函數和約束條件計算函數值，直到滿足預期要求，從而達到優化目的。雖然由式（2）可知DPSO算法不再像PSO算法具有明顯的幾何意義，但其核心思想仍然類似。為了易于理解和分析后文的算法改進思路，本文仍以鳥群覓食行為為原型，將DPSO算法進行物理模型抽象映射，過程如下：

每一個解序列 Xi抽象為鳥群中的一只鳥，對解序列中的元素進行排序抽象為鳥從當前位置沿某方向運動了一段位移，排序后計算得出的目標函數值與預期要求的差值則抽象為該鳥的新位置與食物的距離。式（2）中，由3項的置換因子組合而成，每項的模長即置換因子的數量可視為對的影響程度。故將抽象為鳥的單次運動，該運動的位移由 3個模長分別為、的速度矢量合成，鳥隨矢量的變化不斷運動至新位置，直至找到食物。模型抽象結果如圖1所示。

圖1 DPSO物理模型抽象映射圖

2.2 傳統DPSO算法缺陷

DPSO算法使用置換因子及置換序列的概念使PSO算法適用于離散問題的求解，并取得很好的成果，但仍存在以下缺陷：

圖2 常數的選值對收斂速度的影響

圖3 速度截取規則對收斂速度的影響

2.3 基于激勵原則的改進算法SMDPSO

通過上述分析，本文對DPSO算法做出如下改進：

1） c1、 c2動態取值。在對分別進行計算時， c、 c的取值根據12進行動態調整。依據“影響大多截取，影響小少截取”的激勵原則，按比例分配 c1、 c2的取值，使“鳥”始終選擇最優運動方向，加快收斂速度。經過改進后的速度和位移更新公式如式(4)，運算法則不變。中，若大于，則對中的置換因子進行按比例截取。假設= k，則從中去除屬于的置換因子的個數為，結果四舍五入取整。同理可得從中去除屬于、的置換因子的個數。采用此改進方法后的效果如圖4所示。

本文在上述改進過程中借鑒了人力資源管理中的自我激勵（Self Motivation）原則，故稱改進后的離散粒子群優化算法為SMDPSO。

2.4 飛機裝配任務調度算法

在SMDPSO的基礎上，提出飛機裝配任務調度算法，描述如下：

1） X定義為裝配流程實例序列 ＜ap1, a p2,… ,a pn＞，表示n個裝配流程實例的一個調度序列。將每個實例劃分k個任務，確定任務間的邏輯關系、觸發條件及各個任務的參考執行時間，定義目標函數為總裝配時間。

2） 初始化粒子數n和位置向量Xi（隨機）。粒子Xi的局部最優解為其本身，全局最優解為n個局部最優解中目標函數值最好的粒子。

3） 對于每一個粒子根據式（4），計算新的位置和速度。

4） 對于每個粒子計算其總裝配時間。若優于其局部最優解，將局部最優解更新。再將每個粒子的局部最優解進行比較，更新全局最優解。

5） 若達到最大迭代次數或完成調度目標，則轉6），否則執行3）。

6） 得到調度方案，分配任務到資源隊列。

3 算例分析

本文使用某型飛機尾段裝配業務作為任務調度的實驗流程，如圖5所示為尾段結構。假設車間內當前存在5個裝配流程：尾椎裝配、總裝框裝配、梁組件裝配、肋板裝配和前緣裝配。每個流程中又包含編制工藝文件、工藝審核、裝配、質檢4個任務，分別由工藝員、技術廠長、裝配員和質檢員來完成。對算法初始化如下：分別對應5個裝配流程，分別對應某個流程中的具體任務，其中taskij(1 ≤ i≤ 5,1≤j≤ 4)表示第i個裝配流程中的第j個任務。每個任務的完成時間 Tij如下（單位為天）。

圖5 尾段結構圖

resource1=＜ 3,{R1, R2, R3},工藝員＞

resource2=＜ 2,{R1, R2},廠長＞

resource3=＜ 2,{R1, R2},裝配員＞

resource4=＜ 2,{ R1, R2},質檢員 ＞，分別表示裝配資源（在這里是人員）。

表1 DPSO與SMDPSO算法優化結果對比(a)

表2 DPSO與SMDPSO算法優化結果對比(b)

表3 DPSO與SMDPSO算法優化結果對比(c)

圖6 迭代平均解對比圖

從實驗結果分析，本文改進的SMDPSO算法與DPSO算法相比，具有較好的尋優能力。在10次迭代的過程中，每一次迭代產生的平均解均優于DPSO算法，且算法穩定收斂。雖然兩個算法找到的最優解基本相同，但SMDPSO算法尋優速度更快。通過以上分析，證明本文的改進是行之有效的。

圖7 任務分配甘特圖

4 結 論

本文針對飛機裝配過程中的任務調度問題，對離散粒子群優化算法展開分析研究，然后在此基礎上提出一種基于激勵原則的改進離散粒子群優化算法SMDPSO，并以某型飛機尾段裝配流程為對象對改進后的算法進行驗證，得到良好效果。

[1] Tozkapan A, Kirca O, Chung C S. A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem [J]. Computers & Operations Research, 2003, 30(2): 309-320.

[2] Jeffcoat, David E, Bulfin, el at. Simulated annealing for resource-constrained scheduling [J]. European Journal of Operational Research, 1993, 70(1): 43-51.

[3] Sun X, Morizawa K, Nagasawa H. Powerful heuristics to minimize makespan in fixed 3-machine assemblytype flow shop scheduling [J]. European Journal of Operational Research, 2003, 146(3): 498-516.

[4] Pongcharoen, Hicks P. Determining optimum genetic algorithm parameters for scheduling the manufacturing and assembly of complex products [J]. International Journal of Production Economics, 2002, 78(3): 311-322.

[5] Cagnina L, Esquive S, Gallard R. Particle swarm optimization for sequencing problerms: a case study [C]//Proc of the Congress on Evolutionary Computation. Oregon, Portland: [s.n.], 2004: 536-541.

[6] Kennedy J, Ebethar R C. Particle swarm optimization [C]// Proceedings of IEEE International Conference on Neural Networks, 1995: 1942-1948.

[7] 劉 風. 粒子群優化算法在TSP問題中的研究與應用[D]. 無錫: 江南大學, 2008.

[8] 陳震亦. 粒子群優化算法的研究及其在TSP問題中的應用[D]. 福州: 福州大學, 2004.

[9] Shi Y, Eberhart R C. A modified particle swarm optimizer [C]//Proc. of the 1998 IEEE International Conference on Evolutionary Computation. Piscataway, NJ: IEEE Press, 1998: 69-73.

[10] 劉環宇. 工作流系統中任務調度策略研究[D]. 長春: 長春工業大學, 2010.

[11] 曾 樑. 多品種小批量生產模式下的智能調度方法研究[D]. 北京: 中國工程物理研究院, 2011.

[12] 郭文忠, 陳國龍, 陳 振. 離散粒子群優化算法研究綜述[J]. 福州大學學報, 2011, 39(5): 631-638.

[13] 鄧偉林, 胡桂武. 一種求旅行商問題的離散粒子群算法[J]. 計算機與現代化, 2012, 199: 1-4.

Aircraft assembly task scheduling based on improved discrete particle swarm optimization

Han Pengfei, Sun Zhanlei, Zhao Gang
( Beijing University of Aeronautics and Astronautics, Beijing 100191, China )

The importance of task scheduling in aircraft assembly process and the current research status of scheduling algorithm is introduced. The discrete particle swarm optimization is analyzed, and an improvement of the algorithm based on self motivation principle is proposed. The improved algorithm has been well verified by the actual assembly process of an aircraft’s tail section.

aircraft assembly; task scheduling; improved DPSO; self motivation principle

V 19

A

2095-302X (2013)01-0060-06

2012-05-29；定稿日期：2012-07-02

國家“863”重點資助項目（2009AA043302）

韓鵬飛（1986-），男，山東煙臺人，碩士研究生，主要研究方向為飛機數字化裝配。E-mail：163heanas@163.com

趙 罡（1972-），男，河北文安人，教授，主要研究方向為CAD/CAM，幾何造型，虛擬現實。zhaog@buaa.edu.cn