混合離散粒子群算法在混流裝配線生產調度中的應用

周康渠，趙慧真

(重慶理工大學 機械工程學院，重慶 400054)

?

混合離散粒子群算法在混流裝配線生產調度中的應用

周康渠，趙慧真

(重慶理工大學 機械工程學院，重慶 400054)

為使混流裝配線有效運作，研究了混流裝配線的生產調度問題。以最小化最大完工時間為優化目標，建立了調度模型。針對算法中存在的“早熟”現象，提出了一種與基于NEH方法的領域搜索策略結合的混合離散粒子群算法，并通過實例驗證了算法的有效性。經與其他算法比較后發現：混合離散粒子群算法在求解摩托車混流裝配線生產調度問題上具有優勢，能快速搜索到最優解，具有較好的收斂性。

混合離散粒子群算法；混流裝配線；生產調度

混流裝配線可以在基本不改變生產組織方式的前提下，同時生產出多種不同型號、不同數量的產品，是應對大規模定制生產的一種有效的組織方式[1]。目前，為滿足顧客的多樣化和個性化需求，我國的摩托車企業采用按訂單生產(MTO)方式。訂單多品種、小批量的特點決定企業必須采用混流裝配線組織生產，增加了生產調度的難度。混流裝配線的生產調度合理與否直接影響企業的生產效率，本文對混流裝配線的生產調度問題進行研究。

混流裝配線的成功應用得到了企業界和學術界的極大關注，混流裝配線的生產調度問題也成為研究熱點。文獻[2]對混流裝配線生產調度問題的研究現狀進行了綜述，指出了啟發式算法的缺陷；文獻[3]分析了混流裝配線生產調度問題的幾種優化目標，并對最優解算法、試探算法、循環改進算法進行了對比研究；文獻[4]建立了JIT環境下以混流裝配線停線時間最小為調度優化目標的數學模型；文獻[5]建立了以零部件使用速率均勻化為調度優化目標的單級混流裝配線生產調度模型，并嘗試用目標追隨法求解。總的來說，混流生產線調度問題考慮的優化目標主要有作業域負荷均衡化[6-7]、零部件使用速率均勻化[8-9]、最小更換工裝夾具次數[10-11]、流水線最短停線時間等[12-13]。混流裝配線的生產調度問題是組合優化問題，是一類典型的NP難題，目前有很多種方法來研究這個問題，如最優解算法、啟發式算法、智能優化算法、混合算法等。由于各種算法本身的局限性，出現了很多混合、改進的算法。本文主要研究混合離散粒子群算法在混流裝配線生產調度中的應用，并與其他算法進行比較。

1 粒子群算法

粒子群優化算法(PSO)是一種有效的全局尋優算法，最早由美國的Kenedy和Eberhart于1995年提出，設想模擬鳥群覓食的過程，后來從這種模型中得到啟示，并將粒子群算法用于解決優化問題。該算法保留了種群的全局搜索策略，避免了復雜的遺傳操作，具有不依賴問題信息、通用性強、原理簡單、易于實現等優點。同時，粒子群算法具有較強的擴展性，容易與其他算法結合，將其進行離散化適合于求解混流裝配線的生產高度問題。

粒子群算法把每一個優化問題的解看作是搜索空間中的一只鳥，即“粒子”。首先生成初始種群，即在可行解空間中隨機初始化一群粒子，每個粒子都為優化問題的一個可行解，并由目標函數評價其適應度值。每個粒子都在解空間中運動，并由一個速度決定其飛行方向和距離，通常粒子追隨當前的最優粒子在解空間中進行搜索。每經一次迭代，粒子將跟蹤2個“極值”來更新自己，一個是粒子本身找到的最優解，另一個是整個種群當下找到的最優解，即為全局最優解[14]。

2 混流裝配線生產調度模型

摩托車混流裝配線的生產調度問題屬于一種典型的PFSP問題，可以描述為：n輛摩托車在m個工位上進行裝配，確定車輛的排產順序，使某項調度性能最優。如果不同型號的產品之間具有很高的工藝相似性，則可將問題簡化為單級混流調度問題。為簡化運算，模型只考慮一個MPS內待裝配產品的優化。為應對市場競爭，摩托車生產企業應盡可能提高生產率，縮短生產時間，減少交貨延遲，因此，最大完工時間是摩托車裝配車間必須考慮的一項重要優化指標之一，其計算公式如下：

(1)

(2)

(3)

(4)

其中：n為一個MPS內生產的摩托車數；m為摩托車混流裝配線的工位數；cmax為最大完工時間，即最后一輛摩托車在最后一個工位完成裝配的時間；ci,j為摩托車i在工位j上的裝配時間；c為摩托車混流裝配線的生產節拍；ti,j為摩托車i在工位j上的裝配時間。

在以上公式基礎上，增加以下新的變量：

k:一個MPS中摩托車的位置編號，k=1,2,…,n；

u：一個MPS中生產的車型數，u=1,2,…,U；

du：一個MPS中待生產u型車的數量；

令決策變量為

最大完工時間計算邏輯圖如圖1所示。

圖1 最大完工時間計算邏輯圖

圖1中，Q(n)表示摩托車一個生產序列Q(1,2,…,n) 中第n個產品。 則摩托車混流裝配線的最小化最大完工時間調度模型如下：

目標函數為

(5)

約束條件為：

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

目標函數(5)保證最大完工時間最小；約束條件(6)和(7)保證在生產循環中各摩托車出現并且只能出現一次；約束條件(8)為第一輛車在首個工位上的裝配完成時間；約束條件(9)和(10)保證每輛車不能同時在多個工位上裝配且每個工位在某個時刻僅裝配一輛車；約束條件(11)表示在一次生產循環中所有車型的數量和等于摩托車總數；約束條件(12)限定所有工位的裝配完成時間均大于零；約束條件(13)為決策變量的取值范圍。

3 混合離散粒子群算法在混流裝配線中的應用

3.1 混合離散離子群算法設計

一般粒子群算法多用于求解連續最優化問題，而生產調度屬于離散性問題，必須將其進行離散化，建立粒子群的位置向量與摩托車混流裝配線的調度排序方案之間的映射關系。本文將摩托車排隊序列作為粒子群的位置矢量，利用遺傳算法的交叉和變異操作實現粒子群的位置更新，通過一種混合離散粒子群算法(HDPSO)進行求解，最后得到最優的生產調度方案。

1) 解的表達

解的表達是設計和操作粒子群算法的關鍵，決定了算法的復雜程度和解的質量。本文采用基于車型的實數編碼，即用數字1，2，3分別表示車型u1，u2，u3。粒子的每一維分量表示一輛在制摩托車，一個粒子矢量代表一個車輛隊列。

2) 基于NEH算法的初始解改造

初始解的好壞和分散度決定著混合離散粒子群算法的搜索效率。NEH算法是解決PFSP問題最有效的啟發式方法之一，常被用于群體搜索的初始化。本文首先采用NEH算法產生一個或多個初始粒子，其余粒子隨機產生，從而實現快速收斂。

NEH算法的流程如下：

② 根據總加工時間TTi非遞增的順序排列，計算得到一個初始化的序列：Q0={Q0(1),Q0(2),…,Q0(n)}；

③ 取出Q0的前兩輛車Q0(1)，Q0(2)，將其排序得：{Q0(1),Q0(2)}、{Q0(2)，Q0(1)}，得出最大完工時間最小的作為當前調度，記為Q={Q(1),Q(2)}；

④ 令i=3，取出Q0的第三輛車，將其插入Q所有可能的位置，可得到i個部分排列的調度，得出最大完工時間最小的一個作為當前調度；

⑤ 令i=i+1，如果i≤n，重復④，直到所有輛車全部取出，輸出最大完工時間最小的調度方案，作為NEH算法的最優解。

3) 粒子群的位置更新

由于標準粒子群算法在迭代時受當前速度、自身認知和社會認知的影響，加之粒子群算法的速度和位置更新策略無法直接用于摩托車混流裝配線調度問題中，因此本文借鑒遺傳算法中的交叉和變異操作，通過粒子當前位置與個體極值或群體極值之間的交叉實現更新迭代，完成進化搜索。

4) 局部搜索策略

一些研究表明，粒子群算法有很好的并行性和全局粗搜索能力，收斂速度快，但在實驗中發現其在計算過程中，局部精搜索能力較弱，使得算法不能向最優解方向進化，在進化后期易陷入“早熟”現象。基于NEH方法的領域搜索以種群最優值gBk作為操作對象，根據NEH算法原理，有較高的局部開發能力，可以平衡粒子群算法的收斂性和搜索精度，其基本步驟如下：

① 取gBk為初始序列，記為Q0={Q0(1),Q0(2),…,Q0(n)}；

② 取出Q0的前兩輛車Q0(1),Q0(2)，將其排序得{Q0(1),Q0(2)}、{Q0(2)，Q0(1)}，得出最大完工時間最小的作為當前調度，記為Q={Q(1),Q(2)}；

③ 令i=3，取出Q0的第三輛車，將其插入Q所有可能的位置，可得到i個部分排列的調度，評價各個調度方案，將最大完工時間最小的一個作為當前調度；

④ 令i=i+1，如果i≤n，重復③，直至所有輛摩托車全部取出，輸出最大完工時間最小的調度方案，更新gBk。

綜上所述，解決摩托車混流裝配線最小完工時間生產調度的混合離散粒子群算法的流程如下：

① 設置混合離散粒子群算法參數：種群規模SwarmSize、粒子維數ParticleSize、運行時間trun、慣性權重ω和學習因子c1，c2；

② 對粒子群進行初始化，采用NEH算法產生一個初始序列，其余粒子隨機產生；

③ 計算每輛車排列的最大完工時間，作為每個粒子的適應度值；

④ 根據每個粒子的適應度值更新個體最佳位置pBk和種群最佳位置gBk；

⑤ 更新粒子群的位置矢量；

⑥ 對種群最佳位置gBk執行基于NEH方法的局部搜索策略，更新gBk值；

⑦ 判斷是否滿足迭代終止條件(達到預設的迭代次數或在一定的迭代次數中未發現更好的解)。若是，則輸出最優解gB；若不是，則返回③；

混合離散粒子群算法的流程如圖2所示。

圖2 混合離散離子粒算法流程

3.2 實例計算及分析

為驗證混合離散粒子群算法解決混流裝配線調度問題的有效性和實用性，通過下面的實例進行驗證。實例數據采集來源于某摩托車企業，由于摩托車裝配工藝較復雜，現簡化其工藝，只就主要車型及其關鍵工序來考慮。采用Matlab R2012b進行算例相關計算。

本算例需要驗證兩部分：一是調度模型的有效性；二是本文提出的基于NEH的局部搜索策略的HDPSO算法的有效性。采用Taillard測試基準進行驗證。

3.2.1 調度模型的有效性

某摩托車混流裝配線的生產節拍c為140 s，有3種主要車型u1，u2，u3待進行生產，一個MPS中3種車型的個數如表1所示。摩托車裝配線有10個工位，各個車型在各工位的裝配時間矩陣如表2所示。

表1 MPS構成

表2 裝配時間矩陣

實驗時，設置HDPSO算法的參數分別為：種群規模SwarmSize=20；粒子維數ParticleSize=n(n為車輛數)；運行時間trun=10*n*m(ms)；慣性權重ω=0.8；學習因子c1=c2=0.5。經運行得到的最優解為2 974 s，對應的摩托混流裝配線車排產序列為：112312233112。

3.2.2 混合離散粒子群算法的有效性

選取12組不同規模(即n·m)的Taillard PFSP問題作為測試基礎，其規模分別為：20×5，20×10，20×20，50×5，50×10，50×20，100×5，100×10，100×20，200×10，200×20和500×20。對各算法不同規模下的算例均運行5次，分別得出其平均偏差和均方差，并給出各算法不同規模下的算例的不同指標值。

定義相對偏差(average relative deviation，ARD)：

(14)

其中：N為運行次數，本例中取N=5；S為算例集合，根據規模不同共有12組；Bi,j為第j次運算時，算例i的最優解；Bi為算例i的最優解。ARD表示計算所得最優解與已知最優解的相對偏離程度。ARD的值越小，表明所得最優解越接近已知最優解。當ARD=0時，表示所得最優解與已知最優解一致。

1) 算法設置及其性能比較

粒子群算法中粒子更新位置的方法有插入、互換、逆序3種變異操作和單點交叉、兩點交叉、次序交叉、單點相似工件交叉及兩點相似工件交叉5種交叉操作，一共有15種不同的HDPSO算法。對這15個組合算法采用Taillard算例進行仿真實驗，并計算其平均偏差，結果如表3所示。通過表3可以得出以下結論：

① HDPSO1～HDPSO15相對于NEH算法，ARD性能在一定程度上均有所改善，證明HDPSO算法在解決生產調度問題的有效性。

② 3種變異操作中逆序變異最優，插入變異次之，互換變異最差。

③ 交叉操作中兩點交叉優于單點交叉，兩點相似工件交叉優于單點相似工件交叉，次序交叉性能最差。

④ 從總體來看，HDPSO15得到了最小的平均相對偏差，說明其性能最優。

⑤ 從數據分析結果可以看出，不同的位置更新方式對HDPSO算法的性能影響較大，因此，設計最優的粒子群位置更新方式可提升HDPSO算法的性能。

2) HDPSO與其他算法的比較

為了驗證HDPSO算法在求解摩托車混流裝配線調度問題上的有效性，將其與模擬退火算法(simulated annealing，SA)、禁忌搜索算法(taboo search，TS)、貪婪算法(greedy algorithm，GrA)、蟻群算法(ant colony optimization，ACO)和遺傳算法進行比較，計算其平均偏差，結果如表4所示。對比表3和表4，得出如下結論：

① HDPSO2，HDPSO5，HDPSO7，HDPSO12，HDPSO14的性能略優于GA，與SA，TS，GrA和ACO相比，均優于所選的對比算法；

② HDPSO1，HDPSO4，HDPSO10，HDPSO11，HDPSO14的平均相對偏差GA稍大，但優于SA，TS，GrA和ACO；

③ 平均偏差最大的HDPSO(2.971%)也優于ACO(3.005%)，SA(3.295%)和GrA(3.409%)算法；

④ 綜上，對于摩托車混流裝配線調度問題，HDPSO是一種有效的優化算法，其性能明顯優于ACO，SA，GrA算法。

表3 HDPSO算法的性能比較

表4 各算法的性能比較

3) 初始化方法對算法性能的影響

以性能最優的HDPSO15算法為例，分析初始化方法對HDPSO算法性能的影響。在HDPSO15算法中，用NEH方法產生初始粒子，其余粒子隨機產生。同時，設計一個對比算法HDPSO15C，初始粒子隨機產生。通過在相同的仿真環境下設置相同的實驗參數、測試算例和運行時間，記錄最大偏差MAX和最小偏差MIN并按式(14)計算其平均偏差，結果如表5所示。從數據可看出：HDPSO15的各項性能優于HDPSO15C，說明NEH方法對部分初始解改造策略的有效性。隨著運算時間的增加，算法的優越性逐漸減弱，初始化方法對執行后期的影響越來越小。考慮到摩托車混流裝配線生產調度的實時性特點，基于NEH方法的初始化策略能較好地滿足實際生產調度的需求。

表5 初始化方法對算法性能的影響

4) 局部搜索策略對算法性能的影響

在HDPSO15中采用NEH領域搜索方法對種群最優值進行更新，對比算法HDPSO15U對種群最優值不作處理。采用相同的仿真環境、實驗參數、測試算例和運行時間，記錄最大偏差MAX和最小偏差MIN并按式(14)計算得平均偏差，結果如表6。從表6中數據可看出：HDPSO15的各項性能均優于對比算法，具有較小的相對偏差，說明基于NEH算法的局部搜索策略具有較好的有效性。

表6 局部搜索策略對算法性能的影響

4 結束語

本文通過分析摩托車混流裝配線生產調度問題的優化目標和約束條件，建立以最小化最大完工時間為優化目標的數學模型。在此基礎上，設計了一種混合離散粒子群算法HDPSO，對初始化方法、粒子位置更新和局部搜索策略進行了設計。HDPSO算法是在粒子群算法的基礎上設計的，粒子群算法自身具有較好的全局搜索能力，可避免局部最優。然后通過對種群最佳位置執行基于NEH方法的局部搜索策略，使HDPSO算法在局部搜索中具有優勢，平衡了粒子群算法的收斂性和搜索能力，避免了“早熟”現象。仿真實驗的結果表明：該算法在求解摩托車混流裝配線最小完工時間調度問題時具有較強的優勢，能快速搜索到最優解，具有較好的收斂性，是解決混流裝配線優化調度問題的一種理想方法。

[1] 邵新宇,饒運清.制造系統運行優化理論與方法[M].北京：科學出版社,2010:91-93.

[2] KUBIAK W.Minimizing variation of production rates in just-in-time systems:a survey [J].European Journal of Operational Research,1993,66(3):259-271.

[3] 趙曉波,周兆英.混合車型組裝線的投入順序問題[J].中國機械工程,1998,9(3):28-31.

[4] ZHAO X B,KATSUHISA O.Algorithms for sequencing mixed models on an assembly line in a JIT production system[J].Computers and Industry Engineering,1997,32(1):47-56.

[5] LEU Y,MATHESON L A,RESS L P.Sequencing mixed model assembly lines with genetic algorithms [J].Computers & Industry Engineering,1996,30(4):1027-1036.

[6] BOYSEN N,FLIEDNERB.Review and comparison of three methods for the solution of the car sequencing problem [J].Journal of the Operational Research,2006,57:1497-1498.

[7] SCHOLL A,KLEIN R.Pattern based vocabulary building for effectively sequencing mixed-model assembly lines [J].Journal of Heuristics,1998(4):359-381.

[8] SCHOLL A,KLEIN R.Pattern based vocabulary building for effectively sequencing mixed-model assembly lines [J].Journal of Heuristics.1998(4):359-381.

[9] MILTENBURG J.Level schedules for mixed-model assembly lines in just-in-time Production systems [J].Management Science,1989,35:192-207.

[10]SUMICHRAST R T,RUSSELL R S.Evaluating mixed-model assembly line sequencing heuristics for just-in-time production systems [J].J.Operational.Manage,1990,9:371-389.

[11]LAHMAR M,ERGAN H,BENJAAFAR S.Resequencing and feature assignment on an automated assembly line [J].IEEE Transactions on Robotics and Automation,2003,19(1):89-102.

[12] MANSOURI.A Multi-Objective Genetic Algorithm for mixed-model sequencing on JIT assembly lines [J].European Journal of Operational Research,2004,167:696-716.

[13]MCMULLEN P R,PETER T.A beam search heuristic method for mixed-model scheduling with setups [J].International Journal of Production Economics,2005,96:273-283.

[14]楊淑瑩,張樺.群體智能與仿生計算—Matlab技術實現[M].北京:電子工業出版社,2012:157-161.

(責任編輯 楊黎麗)

Application on Scheduling of Mixed Model Assembly Lines with Hybrid Distribution Particle Swarm Optimization Algorithm

ZHOU Kang-qu, ZHAO Hui-zhen

(College of Mechanical Engineering, Chongqing University of Technology,Chongqing 400054, China)

To realize the effective operation of mixed assembly line, the mixed scheduling problem was studied. The objective of minimizing the make-span was considered and its mathematical model was described. To avoid premature convergence in particle swarm optimization algorithm, a hybrid distribution particle swarm optimization algorithm (HDPSO) was proposed. This algorithm was based on the Nawaz-Enscore-Ham algorithm of neighborhood searching strategy. The HDPSO was effective by an instance. Compared with other algorithm, the optimization results showed that the HDPSO had the advantage on the scheduling of motorcycle mixed model assembly lines. It could get the best method and had the better Astringency.

hybrid distribution particle swarm optimization algorithm; mixed model assembly; scheduling

2014-11-25 基金項目：重慶市科委基礎與前沿研究項目(CSTC2013jcyjA0564)

周康渠(1967—)，女，四川達州人，博士，教授，主要從事生產系統優化技術、制造業信息化等方面研究。

周康渠，趙慧真.混合離散粒子群算法在混流裝配線生產調度中的應用[J].重慶理工大學學報：自然科學版，2015(3):58-64.

format：ZHOU Kang-qu, ZHAO Hui-zhen.Application on Scheduling of Mixed Model Assembly Lines with Hybrid Distribution Particle Swarm Optimization Algorithm[J].Journal of Chongqing University of Technology:Natural Science,2015(3):58-64.

10.3969/j.issn.1674-8425(z).2015.03.012

TP393；TH165

A

1674-8425(2015)03-0058-07