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

韓鵬飛 ， 孫占磊， 趙 罡

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

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

韓鵬飛 ， 孫占磊， 趙 罡

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

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

飛機裝配；任務調(diào)度；改進離散粒子群優(yōu)化算法；激勵原則

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

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

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

1 粒子群算法

1.1 粒子群算法

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

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

1.2 離散粒子群算法

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

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

公式中的相關(guān)運算說明如下：

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

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

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

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

6）1c、2c為（0,1）間的常數(shù)。

2 算法分析與改進

2.1 DPSO物理模型抽象映射

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

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

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

2.2 傳統(tǒng)DPSO算法缺陷

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

圖2 常數(shù)的選值對收斂速度的影響

圖3 速度截取規(guī)則對收斂速度的影響

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

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

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

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

2.4 飛機裝配任務調(diào)度算法

在SMDPSO的基礎(chǔ)上，提出飛機裝配任務調(diào)度算法，描述如下：

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

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

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

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

5） 若達到最大迭代次數(shù)或完成調(diào)度目標，則轉(zhuǎn)6），否則執(zhí)行3）。

6） 得到調(diào)度方案，分配任務到資源隊列。

3 算例分析

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

圖5 尾段結(jié)構(gòu)圖

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

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

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

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

表1 DPSO與SMDPSO算法優(yōu)化結(jié)果對比(a)

表2 DPSO與SMDPSO算法優(yōu)化結(jié)果對比(b)

表3 DPSO與SMDPSO算法優(yōu)化結(jié)果對比(c)

圖6 迭代平均解對比圖

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

圖7 任務分配甘特圖

4 結(jié) 論

本文針對飛機裝配過程中的任務調(diào)度問題，對離散粒子群優(yōu)化算法展開分析研究，然后在此基礎(chǔ)上提出一種基于激勵原則的改進離散粒子群優(yōu)化算法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] 劉 風. 粒子群優(yōu)化算法在TSP問題中的研究與應用[D]. 無錫: 江南大學, 2008.

[8] 陳震亦. 粒子群優(yōu)化算法的研究及其在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] 劉環(huán)宇. 工作流系統(tǒng)中任務調(diào)度策略研究[D]. 長春: 長春工業(yè)大學, 2010.

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

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

[13] 鄧偉林, 胡桂武. 一種求旅行商問題的離散粒子群算法[J]. 計算機與現(xiàn)代化, 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-），男，山東煙臺人，碩士研究生，主要研究方向為飛機數(shù)字化裝配。E-mail：163heanas@163.com

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