基于粒子群優化算法的柔性生產線排產方法

玉海龍，何 陶

（航空工業成都飛機工業（集團）有限責任公司，成都 610092）

根據前瞻產業研究院的研究報道[1]，在未來十年期間，絕大部分的老舊機型將會在更新換代中退役，新一代的先進機型也將會隨之列裝。在軍工產品型號升級換代速度快、生產效率要求高、飛機數量需求大的當下，根據長期經驗進行生產排產的傳統排產方式很難使車間的生產效率達到最優。

為了適應中小批多品種的生產線排產與調度需求，在20世紀70年代，柔性制造系統 （Flexible manufacturing system，FMS）[2]應運而生。其中最關鍵的便是作業車間調度問題 （Job-shop scheduling problem，JSP），該問題的定義為：有一組機器需加工一組工件，每一個工件的加工由具有先后順序約束的加工工序組成，每一個工序只需要一臺機器來加工，且機器一直可用，機器可以在不被中斷的情況下一次處理一個工序。在這樣的條件下，決策的內容為如何對機器上的工序進行排序，使得完工時間最短[3]。在JSP的基礎上，還有柔性作業車間調度問題[4]（Flexible job-shop scheduling problem，FJSP），其減少了工序對機器的約束，即每一個工序可以由一臺或者多臺機器進行加工，更加貼近實際生產，同時也增加了問題的復雜度，是一個更加難求解的非確定性多項式時間難題[5]。

為了解決調度問題，國內外學者研究并提出了多種算法，較早研究FJSP問題的是Bruker[5]，他于1990年提出了求解只有2個工件的簡單FJSP的多項式算法；Lin等[6]將遺傳算法與粒子群算法相結合，提出混合演化算法；Xia等[7]采用粒子群算法與模擬退火算法相結合的方法對多目標FJSP進行求解，不僅提高了算法的效率，還提高了求解的質量；Teekeng等[8]提出一種改進的遺傳算法，他們采用“模糊輪盤賭選擇”的方式改進交叉算子和變異算子的計算，使遺傳的種群保持了種群的多樣性，克服了收斂過早的問題。

經過實際應用測試分析發現，傳統的遺傳算法和粒子群算法并不能實際解決本文生產線排產問題，為此，本文對粒子群算法進行求解優化，最終實現對文中排產問題的求解。

1 柔性生產線分析與建模

1.1 柔性生產線分析

零部件加工柔性生產線由物料庫、物料機器人及導軌、上下料工位、加工機床、測量機、總控臺、刀具機器人及導軌、刀具更換工位、刀具庫組成，如圖1所示。其中MT1、MT2是4軸數控加工機床，MT3、MT4是5軸數控加工機床。

圖1 柔性生產線布局圖Fig.1 Layout drawing of flexible production line

該生產線中的機床和測量機均具備雙工作臺，即加工區和準備區，通過雙工作臺可以實現機床和測量機不間斷更換工件，減少物料更換與等待時間。但在以下情況發生時，需要考慮物料機器人搬運時間，即當某工件剛完成加工且該工件需要測量，而此時測量機處于空閑狀態，物料機器人將直接從機床上取料，然后送往測量機進行測量，此時需要考慮物料機器人搬運時間，該時間平均約為1 min。機器人給各個機床和測量機上料與下料的時間大約也是1 min。

根據柔性生產線的實際生產任務，其調度需求如下。

（1）緊急插單。即在原定的計劃中添加新的訂單，并且該訂單需要被優先加工。

（2）任務指定機床。在進行生產計劃制定的時候，將某一個加工任務指定到某一臺或者一類機床上進行加工，指定到某一臺機床通常適用于操作人員調試新品工藝參數，而指定到某一類機床適用于只能使用某類機床進行加工的工件。

（3）機床熱拔插。一種情況是在某一臺機床不執行任務時，將該機床退出該生產線，通常適用于對機床的維修等工作；另一種情況是在需要增加生產線的產能時，新增機床。

（4）工件測量。在某些工件完成加工后，需要對其進行測量，通常適用于對精度、質量要求較高的產品，或者是首批加工的產品。

（5）工件暫停生產。根據生產或者用戶的需要停止某些工件的生產。

（6）任務指定期限。有一些特定的工件，其需求時間是有要求的，針對這種情況，生產線在排產時需要實現其在指定期限內完成加工。

（7）加工效率最高。在滿足所有加工條件約束的前提下，實現所有工件以最高效率完成加工與測量，即所有的加工任務完工時間最短。

1.2 生產線建模

1.2.1 通過任務優先級解決緊急插單問題

為實現有特殊工期要求的工件可以提前加工，對進入柔性生產線加工的工件設立優先級，在排產時，優先加工優先級高的工件。本文為工件設計3個優先級：普通等級、優先等級、緊急等級，對應的編碼為1、2、3，其加工的優先級為緊急等級>優先等級>普通等級。

在排產時，為減少排產復雜度，提高資源利用率，僅考慮同一臺機床上所加工的零件的優先級。例如A號機床分配到TK1、TK2、TK3、TK4 4個工件進行加工，它們的優先級依次為3、2、1、1；B號機床分配到4個工件TK5、TK6、TK7、TK8進行加工，它們的優先級依次為1、1、1、1。

本文僅單獨考慮A號、B號機床上的4個零件，其優先級滿足要求即可，并不要求B號機床上加工的第1個工件的優先級高于A號機床上加工的第2個工件。

1.2.2 機床約束

根據生產線的實際情況，工件任務對機床的約束可以分為4種情況：（1）只能在4軸機床上加工； （2）只能在5軸機床上加工； （3）可以在4、5軸機床上加工；（4）指定在某臺機床上加工。

對于可以在兩類機床上加工的工件，本文認為其在不同機床上加工的時間是相同的。

為了明確表示工件任務對應的機床以及加工時間信息，工件任務信息中關于設備屬性的信息如表1所示。

表1 工件任務設備信息表Table 1 Workpiece task equipment information table

1.2.3 刀具更換與沖突時間

一個工件的加工通常需要一個刀具集才能完成，為了方便分析，本文對刀具做如下設定。

（1）將工件任務所需的刀具集作為一個整體，在需要刀具時，將其以一個整體為單位運送到機床上。

（2）當下一個加工任務所需的刀具集不同時，需要將當前的刀具集全部移出，并換上新的刀具集。因此加工第1個工件時，默認需要進行一次刀具更換。

（3）當相鄰的兩個工件使用的刀具集相同時，無須更換刀具。

（4）由于刀具數量有限，設定一個刀具集只有一套，當某刀具集正在被使用，其他機床的工件若需要使用此刀具集，需等待該刀具集使用完畢。

（5）由于只有一個刀具更換機械手，當刀具更換時間沖突時，計算沖突機床的剩余加工時間，先給剩余加工時間最長的機床換刀；若剩余加工時間相同，則任務號小的先進行換刀。

（6）根據現場測試情況，刀具更換時間約為4 min。

1.2.4 工件測量順序

柔性生產線上只有1臺測量機，因此，本文設定所有工件均可以在該測量機上進行測量，工件測量順序計算規則如下：

（1）首先根據任務完工時間對加工完成后的工件測量順序進行排序；

（2）如果完工時間相同，則根據工件加工優先級進行排序；

（3）若完工時間與優先級均相同，則根據任務單的序號進行排序。

1.2.5 任務總超期時間

工件超期是針對完成時間有限定的工件任務而言的，任務總超期時間是所有任務超期時間的總和，設任務i的計劃完工時間為Tpi，若無計劃完成時間，則令Tpi=0。假設實際完成時間為Ti，則任務i超期時間TOi為

任務總超期時間Tover為

1.2.6 調度的目標

本文生產排產的調度目標是：在滿足機床約束、工件任務優先級約束及所有工件不超期的情況下，任務總完工時間最短。

任務總完工時間Ttotal為所有任務完成加工與測量后的時間。假設任務i的完成時間Ti對應的機床加工完成時間為Pi，測量完成時間為Mi，對于不進行測量的工件，令Mi= 0。任務總完工時間是最后一個工件完工時間。有

式中，n為任務數量。

2 排產算法設計與優化

2.1 工件任務信息描述

有20個工件加工任務，需要將其分配到柔性生產線的4臺機床和測量機中進行加工和測量，其機床加工約束要求、加工時間、測量要求以及測量時間、加工刀具集合類型、完工時間要求以及加工優先級見表2。

表2 工件任務信息表Table 2 Job task information table

2.2 排產算法設計

2.2.1 粒子群算法簡介

粒子群優化 （Particle swarm optimization，PSO）算法在連續域內尋優表現出良好的求解性能[9]，通過適當的編碼規則，PSO同樣也可以應用在某些離線域的尋優求解上，例如調度問題[10-12]。因此，本文選用粒子群算法作為核心算法，求解柔性生產線排產調度問題。

粒子群優化算法流程圖如圖2所示，其種群迭代退出條件是達到最大的迭代次數或者全局最優位置滿足最小界限。

圖2 粒子群優化算法流程圖Fig.2 Particle swarm optimization algorithm flow chart

其中粒子速度和位置的更新公式為

2.2.2 粒子編碼

針對柔性生產線實際排產任務，可進行粒子編碼，即假設總加工任務為N，則其可行解為一個2N的行向量，向量中包含了N個任務的加工順序及各個任務對應的N個加工機床。粒子群優化算法中，將該可行解定義為粒子P，其包含PMT[N]以及Ptask[N]。其中Ptask[N]是任務向量，由N個1～N之間的不重復的正整數組成；PMT[N]是機床向量，是由N個1～M（不包括測量機在內的機床總數）之間的正整數組成。

為了說明粒子含義，本文隨機構造一個粒子，即

Ptask[N]：[4，5，9，10，1，2，3，6，8，12，7，15，11，13，16，17，18，20，19，14]

PMT[N]：[1，2，4，2，3，2，1，4，2，3，1，4，2，3，4，2，1，3，1，4]

Ptask[N]中各個序號代表任務數，PMT[N]中各個序號代表加工的機床。由此可以得到任務與機床的對應關系如表3所示。

表3 通過粒子獲取的機床與任務的對應關系表Table 3 Correspondence between machine tools and tasks obtained through particles

2.2.3 適應度定義

根據生產線模型可知，本文對任務的要求是多方面的，它包括任務總完工時間Ttotal、任務總超期時間Tover、機床約束積分SMT以及任務優先級約束積分SPr。本文根據生產實際需要，將這4個要求定義了如下的重要等級：SMT（x）>Tover（x）>SPr（x）>Ttotal（x） 。

設定粒子x的適應度函數為F（x），則有

F（x）=SMT（x）/Tover（x）/SPr（x）/Ttotal（x）

適應度函數值越小，則該粒子的解越好。

根據粒子假設和對應關系可對任務增加機床約束，本文對機床約束采用積分方式判斷排產后機床約束符合情況，當發現有一項任務不滿足要求時，積分加1，可得表4所示對照表。

表4 任務與排產機床對照信息Table 4 Control information between tasks and production scheduling machines

只有當排產積分S= 0時，該排產才是有效的，才是可行解。

同時任務還有優先級順序，因此對每一個機床上加工任務采用積分SPr的方式進行驗證，最后將所有機床的積分相加，得到的分值為該排產計劃的任務優先級約束積分。

積分規則為：設第j個機床上的第i個任務的優先級為，第j個機床的積分為。將與（0時，積分加上（-）；當≤時，積分加上0分，公式為

其中，

n為j機床上加工分配到的任務數量。

排產計劃的總得分SPr為

式中，NMT為機床數量。

根據式 （9）可分別計算得到MT1～MT4機床的任務優先級積分，即

總積分為9。

2.2.4 更新策略設計

根據更新公式 （式 （5）和 （6））及機床約束、任務優先級約束，可得具體迭代過程如下。

位置向量是由任務向量Ptask[N]和機床向量PMT[N]組成，速度向量也可以表示為任務更新速度向量Vtask[N]和機床更新速度向量VMT[N]。

任務共有N個，因此任務更新速度向量Vtask[N]的最大速度取[-N/2，N/2]之間，任務更新速度向量初始值通過隨機數獲取，計算公式為

機床更新速度向量VMT[N]同理，最大速度取[-NMT/2，NMT/2]之間，NMT為機床數量，其初始值計算公式為

由于機床向量PMT[N]的取值范圍必須在[1，NMT]之間，因此對更新后的[N]向量的處理方法是首先進行四舍五入取整，再對超過邊界值的數值，取對應的邊界值。

而任務向量Ptask[N] 的取值是[1，N]之間不重復的正整數，為此采用排序映射法求取更新后的任務向量。具體過程為：

（1）記錄原各個任務對應的向量序號；

（2）根據更新公式，計算獲取下一代任務序列；

（3）將任務序列從低到高進行排序；

（4）提取排序后的任務序列對應的向量序號，作為新的任務序列。

2.3 算法性能測試

通過MATLAB對粒子群算法以及生產線模型進行實際測試的種群數量為80個，迭代次數為50次，學習因子c1= 2，c2= 2，慣性權重w= 0.75，運算10次，測試結果如表5所示。

表5 測試結果Table 5 Test results

由運算結果可以看出，使用沒有經過改進的粒子群算法對工件任務進行排產，所有的排產結果均不能滿足機床約束和任務優先級約束的要求。

2.4 排產算法優化

根據生產線模型以及適應度函數的定義，可以發現本文研究的FJSP問題屬于多目標優化問題，需要同時最小化4個目標，即任務總完工時間、任務總超期時間、機床約束積分以及任務優先級約束積分。根據文獻[13]可知，雖然PSO算法在進行搜索時，可以一次性搜索解空間中的多個解，具有較好的并行計算能力，但是PSO算法的性能會隨著問題規模的增大而降低，粒子飛行速度也會在算法的迭代過程中逐漸減小，最終會陷入局部極值而停止搜索。

根據上述分析可知，求解失敗是因為求解目標過多，導致問題規模過大，最終在局部極值時收斂。因此，可通過減少粒子群優化算法的求解目標來降低問題規模，實現對FJSP問題的求解。

本文減少的求解目標為機床約束積分與任務優先級約束積分，保留任務總完工時間和任務總超期時間。

生成粒子時，工件將會分配到機床上，此時通過查詢工件任務信息表即可知道工件是否符合機床約束的條件，若不符合約束要求，則對粒子進行調整，使其滿足要求。調整規則如下：

（1）工件任務對機床的約束為“只能在4軸機床上加工”時，隨機選取一個4軸機床作為工件任務的加工機床；

（2）工件任務對機床的約束為“只能在5軸機床上加工”時，隨機選取一個5軸機床作為工件任務的加工機床；

（3）工件任務對機床的約束為“指定在某臺機床上加工”時，將工件任務的加工機床設置為指定的機床。

通過上述規則調整后獲得粒子的機床約束都滿足要求，以此減少了“機床約束積分”求解目標。

為使工件的優先級滿足要求，通過以下規則對機床的加工任務序列進行調整：

（1）將工件優先級從高到低重新排序，生成新的序列；

（2）當前后工件的優先級相同時，不對工件的前后位置關系進行調整。

通過上述規則調整后獲得的粒子的優先級約束都滿足要求，以此減少了“任務優先級約束積分”求解目標。

3 算法仿真結果

通過MATLAB對優化后的粒子群算法進行實現，以上述任務為對象，進行算法的性能、效率與可行性驗證。

第1次測試的種群數量為60個，迭代次數為50次，學習因子c1= 2，c2= 2，慣性權重W= 0.75，運算10次，結果如表6所示。

表6 優化后的算法第一次測試結果Table 6 First test results of optimized algorithms

表6中運算結果按照“任務總超期時間/任務總完工時間”進行呈現，如“0/152”表示任務總超期時間為0 min，任務總完工時間為152 min；其中的最優解任務向量與最優解機床向量共同構成一個解向量。

10次運算中的最優結果為“0/143”，其收斂過程如圖3（a）所示，可以看出，總完工時間最初為163 min，經過27次迭代后，收斂到143 min。

圖3 最優結果“0/143”的收斂過程和排產計劃Fig.3 Convergence process and production schedule of the optimal result "0/143"

圖3（b）中“W”表示等待時間。機床MT1在生產過程中的總使用時間為136 min，其中刀具等待時間4 min、換刀時間12 min、執行機床加工時間120 min；機床MT2在生產過程中的總使用時間為140 min，其中刀具等待時間18 min、換刀時間16 min、執行機床加工時間106 min；機床MT3在生產過程中的總使用時間137 min，其中刀具等待時間14 min、換刀時間8 min、執行機床加工時間115 min；機床MT4在生產過程中的總使用時間為142 min，其中刀具等待時間12 min、換刀時間12 min、執行機床加工時間118 min；測量機的總使用時間為143 min，其中測量等待時間38 min、執行測量時間105 min。

第2次測試的種群數量為100個，迭代次數為100次，學習因子c1= 2，c2= 2，慣性權重w= 0.75，運算10次。其最優結果為“0/146”，收斂過程如圖4所示,可以看出，總完工時間最初為163 min，經過37次迭代后，收斂到146 min。

圖4 最優結果“0/146”的迭代收斂過程Fig.4 Convergence process of the optimal result "0/146"

通過對比算法優化前與優化后的運算結果發現，優化后的所有最優解的超期時間均為0，因此所有的解均為有效解，獲得有效解的概率為100%，而優化前的算法獲得有效解的概率為0。由此可見通過較少求解目標以降低問題規模的優化方法對求解本文中生產線排產問題是可行的。

4 算法性能對比分析

為了測試改進后算法的性能，本節將改進后的算法與文獻[14-15]中提出的改進PSO-GA算法和改進遺傳算法進行比較。測試的對象為表 3所示的工件信息，優化目標同樣為任務總完工時間Ttotal、任務總超期時間Tover、機床約束積分SMT及任務優先級約束積分SPr。使用的軟件為MATLAB R2010b，系統運行環境為Windows 7 64bit，3.30 GHz CPU，20 G RAM。每個算法運行10 次，種群數量均為60個，迭代次數均為50次，其他參數采用文獻中給出的典型值或最優值。從求解結果中選出較優的滿意解。測試結果如表7所示。

表7 算法性能對比結果Table 7 Comparison results of algorithm performance

從測試結果來看，文獻[14-15]中算法的計算結果與改進前的PSO算法計算結果類似，均不能求解出滿足機床約束和工件優先級約束的最優解。

5 結論

（1）以實際生產線為研究對象，分析調度需求，考慮工況中緊急插單、指定機床、任務優先級等情況，對生產線進行建模。

（2）提出一種帶粒子調整環節的粒子群優化算法，在種群粒子初始化以及種群粒子更新后，新增粒子調整環節，在調整環節對粒子進行局部范圍的定向編排優化，得到求解結果。

（3）設計了兩組對比試驗，試驗結果表明，調整環節極大提高了排產算法的求解速度與求解質量，求解成功率為100%。