韓鵬飛 ， 孫占磊， 趙 罡

（北京航空航天大學(xué)，北京 100191）

改進(jìn)離散粒子群算法及其在飛機(jī)裝配任務(wù)調(diào)度中的應(yīng)用研究

韓鵬飛 ， 孫占磊， 趙 罡

（北京航空航天大學(xué)，北京 100191）

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

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

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

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

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

1 粒子群算法

1.1 粒子群算法

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

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

1.2 離散粒子群算法

上述粒子群優(yōu)化算法是為解決連續(xù)空間上的問題而設(shè)計(jì)，但是現(xiàn)實(shí)生活中依然存在大量的基于離散領(lǐng)域的問題需要解決，這時(shí)傳統(tǒng)的粒子群優(yōu)化算法就不再適用。為此學(xué)者們對(duì)其做了進(jìn)一步的改進(jìn)，定義了基于置換因子概念的離散粒子群算法(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)運(yùn)算說明如下：

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

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

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

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

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

2 算法分析與改進(jìn)

2.1 DPSO物理模型抽象映射

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

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

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

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

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

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

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

2.3 基于激勵(lì)原則的改進(jìn)算法SMDPSO

通過上述分析，本文對(duì)DPSO算法做出如下改進(jìn)：

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

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

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

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

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

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

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

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

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

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

3 算例分析

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

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

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

resource2=＜ 2,{R1, R2},廠長(zhǎng)＞

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

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

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

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

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

圖6 迭代平均解對(duì)比圖

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

圖7 任務(wù)分配甘特圖

4 結(jié) 論

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

[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] 劉 風(fēng). 粒子群優(yōu)化算法在TSP問題中的研究與應(yīng)用[D]. 無錫: 江南大學(xué), 2008.

[8] 陳震亦. 粒子群優(yōu)化算法的研究及其在TSP問題中的應(yīng)用[D]. 福州: 福州大學(xué), 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)中任務(wù)調(diào)度策略研究[D]. 長(zhǎng)春: 長(zhǎng)春工業(yè)大學(xué), 2010.

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

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

[13] 鄧偉林, 胡桂武. 一種求旅行商問題的離散粒子群算法[J]. 計(jì)算機(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

國(guó)家“863”重點(diǎn)資助項(xiàng)目（2009AA043302）

韓鵬飛（1986-），男，山東煙臺(tái)人，碩士研究生，主要研究方向?yàn)轱w機(jī)數(shù)字化裝配。E-mail：163heanas@163.com

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