基于粒子群優(yōu)化算法的柔性生產(chǎn)線排產(chǎn)方法

玉海龍，何 陶

（航空工業(yè)成都飛機(jī)工業(yè)（集團(tuán)）有限責(zé)任公司，成都 610092）

根據(jù)前瞻產(chǎn)業(yè)研究院的研究報(bào)道[1]，在未來十年期間，絕大部分的老舊機(jī)型將會(huì)在更新?lián)Q代中退役，新一代的先進(jìn)機(jī)型也將會(huì)隨之列裝。在軍工產(chǎn)品型號(hào)升級(jí)換代速度快、生產(chǎn)效率要求高、飛機(jī)數(shù)量需求大的當(dāng)下，根據(jù)長期經(jīng)驗(yàn)進(jìn)行生產(chǎn)排產(chǎn)的傳統(tǒng)排產(chǎn)方式很難使車間的生產(chǎn)效率達(dá)到最優(yōu)。

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

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

經(jīng)過實(shí)際應(yīng)用測試分析發(fā)現(xiàn)，傳統(tǒng)的遺傳算法和粒子群算法并不能實(shí)際解決本文生產(chǎn)線排產(chǎn)問題，為此，本文對(duì)粒子群算法進(jìn)行求解優(yōu)化，最終實(shí)現(xiàn)對(duì)文中排產(chǎn)問題的求解。

1 柔性生產(chǎn)線分析與建模

1.1 柔性生產(chǎn)線分析

零部件加工柔性生產(chǎn)線由物料庫、物料機(jī)器人及導(dǎo)軌、上下料工位、加工機(jī)床、測量機(jī)、總控臺(tái)、刀具機(jī)器人及導(dǎo)軌、刀具更換工位、刀具庫組成，如圖1所示。其中MT1、MT2是4軸數(shù)控加工機(jī)床，MT3、MT4是5軸數(shù)控加工機(jī)床。

圖1 柔性生產(chǎn)線布局圖Fig.1 Layout drawing of flexible production line

該生產(chǎn)線中的機(jī)床和測量機(jī)均具備雙工作臺(tái)，即加工區(qū)和準(zhǔn)備區(qū)，通過雙工作臺(tái)可以實(shí)現(xiàn)機(jī)床和測量機(jī)不間斷更換工件，減少物料更換與等待時(shí)間。但在以下情況發(fā)生時(shí)，需要考慮物料機(jī)器人搬運(yùn)時(shí)間，即當(dāng)某工件剛完成加工且該工件需要測量，而此時(shí)測量機(jī)處于空閑狀態(tài)，物料機(jī)器人將直接從機(jī)床上取料，然后送往測量機(jī)進(jìn)行測量，此時(shí)需要考慮物料機(jī)器人搬運(yùn)時(shí)間，該時(shí)間平均約為1 min。機(jī)器人給各個(gè)機(jī)床和測量機(jī)上料與下料的時(shí)間大約也是1 min。

根據(jù)柔性生產(chǎn)線的實(shí)際生產(chǎn)任務(wù)，其調(diào)度需求如下。

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

（2）任務(wù)指定機(jī)床。在進(jìn)行生產(chǎn)計(jì)劃制定的時(shí)候，將某一個(gè)加工任務(wù)指定到某一臺(tái)或者一類機(jī)床上進(jìn)行加工，指定到某一臺(tái)機(jī)床通常適用于操作人員調(diào)試新品工藝參數(shù)，而指定到某一類機(jī)床適用于只能使用某類機(jī)床進(jìn)行加工的工件。

（3）機(jī)床熱拔插。一種情況是在某一臺(tái)機(jī)床不執(zhí)行任務(wù)時(shí)，將該機(jī)床退出該生產(chǎn)線，通常適用于對(duì)機(jī)床的維修等工作；另一種情況是在需要增加生產(chǎn)線的產(chǎn)能時(shí)，新增機(jī)床。

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

（5）工件暫停生產(chǎn)。根據(jù)生產(chǎn)或者用戶的需要停止某些工件的生產(chǎn)。

（6）任務(wù)指定期限。有一些特定的工件，其需求時(shí)間是有要求的，針對(duì)這種情況，生產(chǎn)線在排產(chǎn)時(shí)需要實(shí)現(xiàn)其在指定期限內(nèi)完成加工。

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

1.2 生產(chǎn)線建模

1.2.1 通過任務(wù)優(yōu)先級(jí)解決緊急插單問題

為實(shí)現(xiàn)有特殊工期要求的工件可以提前加工，對(duì)進(jìn)入柔性生產(chǎn)線加工的工件設(shè)立優(yōu)先級(jí)，在排產(chǎn)時(shí)，優(yōu)先加工優(yōu)先級(jí)高的工件。本文為工件設(shè)計(jì)3個(gè)優(yōu)先級(jí)：普通等級(jí)、優(yōu)先等級(jí)、緊急等級(jí)，對(duì)應(yīng)的編碼為1、2、3，其加工的優(yōu)先級(jí)為緊急等級(jí)>優(yōu)先等級(jí)>普通等級(jí)。

在排產(chǎn)時(shí)，為減少排產(chǎn)復(fù)雜度，提高資源利用率，僅考慮同一臺(tái)機(jī)床上所加工的零件的優(yōu)先級(jí)。例如A號(hào)機(jī)床分配到TK1、TK2、TK3、TK4 4個(gè)工件進(jìn)行加工，它們的優(yōu)先級(jí)依次為3、2、1、1；B號(hào)機(jī)床分配到4個(gè)工件TK5、TK6、TK7、TK8進(jìn)行加工，它們的優(yōu)先級(jí)依次為1、1、1、1。

本文僅單獨(dú)考慮A號(hào)、B號(hào)機(jī)床上的4個(gè)零件，其優(yōu)先級(jí)滿足要求即可，并不要求B號(hào)機(jī)床上加工的第1個(gè)工件的優(yōu)先級(jí)高于A號(hào)機(jī)床上加工的第2個(gè)工件。

1.2.2 機(jī)床約束

根據(jù)生產(chǎn)線的實(shí)際情況，工件任務(wù)對(duì)機(jī)床的約束可以分為4種情況：（1）只能在4軸機(jī)床上加工； （2）只能在5軸機(jī)床上加工； （3）可以在4、5軸機(jī)床上加工；（4）指定在某臺(tái)機(jī)床上加工。

對(duì)于可以在兩類機(jī)床上加工的工件，本文認(rèn)為其在不同機(jī)床上加工的時(shí)間是相同的。

為了明確表示工件任務(wù)對(duì)應(yīng)的機(jī)床以及加工時(shí)間信息，工件任務(wù)信息中關(guān)于設(shè)備屬性的信息如表1所示。

表1 工件任務(wù)設(shè)備信息表Table 1 Workpiece task equipment information table

1.2.3 刀具更換與沖突時(shí)間

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

（1）將工件任務(wù)所需的刀具集作為一個(gè)整體，在需要刀具時(shí)，將其以一個(gè)整體為單位運(yùn)送到機(jī)床上。

（2）當(dāng)下一個(gè)加工任務(wù)所需的刀具集不同時(shí)，需要將當(dāng)前的刀具集全部移出，并換上新的刀具集。因此加工第1個(gè)工件時(shí)，默認(rèn)需要進(jìn)行一次刀具更換。

（3）當(dāng)相鄰的兩個(gè)工件使用的刀具集相同時(shí)，無須更換刀具。

（4）由于刀具數(shù)量有限，設(shè)定一個(gè)刀具集只有一套，當(dāng)某刀具集正在被使用，其他機(jī)床的工件若需要使用此刀具集，需等待該刀具集使用完畢。

（5）由于只有一個(gè)刀具更換機(jī)械手，當(dāng)?shù)毒吒鼡Q時(shí)間沖突時(shí)，計(jì)算沖突機(jī)床的剩余加工時(shí)間，先給剩余加工時(shí)間最長的機(jī)床換刀；若剩余加工時(shí)間相同，則任務(wù)號(hào)小的先進(jìn)行換刀。

（6）根據(jù)現(xiàn)場測試情況，刀具更換時(shí)間約為4 min。

1.2.4 工件測量順序

柔性生產(chǎn)線上只有1臺(tái)測量機(jī)，因此，本文設(shè)定所有工件均可以在該測量機(jī)上進(jìn)行測量，工件測量順序計(jì)算規(guī)則如下：

（1）首先根據(jù)任務(wù)完工時(shí)間對(duì)加工完成后的工件測量順序進(jìn)行排序；

（2）如果完工時(shí)間相同，則根據(jù)工件加工優(yōu)先級(jí)進(jìn)行排序；

（3）若完工時(shí)間與優(yōu)先級(jí)均相同，則根據(jù)任務(wù)單的序號(hào)進(jìn)行排序。

1.2.5 任務(wù)總超期時(shí)間

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

任務(wù)總超期時(shí)間Tover為

1.2.6 調(diào)度的目標(biāo)

本文生產(chǎn)排產(chǎn)的調(diào)度目標(biāo)是：在滿足機(jī)床約束、工件任務(wù)優(yōu)先級(jí)約束及所有工件不超期的情況下，任務(wù)總完工時(shí)間最短。

任務(wù)總完工時(shí)間Ttotal為所有任務(wù)完成加工與測量后的時(shí)間。假設(shè)任務(wù)i的完成時(shí)間Ti對(duì)應(yīng)的機(jī)床加工完成時(shí)間為Pi，測量完成時(shí)間為Mi，對(duì)于不進(jìn)行測量的工件，令Mi= 0。任務(wù)總完工時(shí)間是最后一個(gè)工件完工時(shí)間。有

式中，n為任務(wù)數(shù)量。

2 排產(chǎn)算法設(shè)計(jì)與優(yōu)化

2.1 工件任務(wù)信息描述

有20個(gè)工件加工任務(wù)，需要將其分配到柔性生產(chǎn)線的4臺(tái)機(jī)床和測量機(jī)中進(jìn)行加工和測量，其機(jī)床加工約束要求、加工時(shí)間、測量要求以及測量時(shí)間、加工刀具集合類型、完工時(shí)間要求以及加工優(yōu)先級(jí)見表2。

表2 工件任務(wù)信息表Table 2 Job task information table

2.2 排產(chǎn)算法設(shè)計(jì)

2.2.1 粒子群算法簡介

粒子群優(yōu)化 （Particle swarm optimization，PSO）算法在連續(xù)域內(nèi)尋優(yōu)表現(xiàn)出良好的求解性能[9]，通過適當(dāng)?shù)木幋a規(guī)則，PSO同樣也可以應(yīng)用在某些離線域的尋優(yōu)求解上，例如調(diào)度問題[10-12]。因此，本文選用粒子群算法作為核心算法，求解柔性生產(chǎn)線排產(chǎn)調(diào)度問題。

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

圖2 粒子群優(yōu)化算法流程圖Fig.2 Particle swarm optimization algorithm flow chart

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

2.2.2 粒子編碼

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

為了說明粒子含義，本文隨機(jī)構(gòu)造一個(gè)粒子，即

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]中各個(gè)序號(hào)代表任務(wù)數(shù)，PMT[N]中各個(gè)序號(hào)代表加工的機(jī)床。由此可以得到任務(wù)與機(jī)床的對(duì)應(yīng)關(guān)系如表3所示。

表3 通過粒子獲取的機(jī)床與任務(wù)的對(duì)應(yīng)關(guān)系表Table 3 Correspondence between machine tools and tasks obtained through particles

2.2.3 適應(yīng)度定義

根據(jù)生產(chǎn)線模型可知，本文對(duì)任務(wù)的要求是多方面的，它包括任務(wù)總完工時(shí)間Ttotal、任務(wù)總超期時(shí)間Tover、機(jī)床約束積分SMT以及任務(wù)優(yōu)先級(jí)約束積分SPr。本文根據(jù)生產(chǎn)實(shí)際需要，將這4個(gè)要求定義了如下的重要等級(jí)：SMT（x）>Tover（x）>SPr（x）>Ttotal（x） 。

設(shè)定粒子x的適應(yīng)度函數(shù)為F（x），則有

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

適應(yīng)度函數(shù)值越小，則該粒子的解越好。

根據(jù)粒子假設(shè)和對(duì)應(yīng)關(guān)系可對(duì)任務(wù)增加機(jī)床約束，本文對(duì)機(jī)床約束采用積分方式判斷排產(chǎn)后機(jī)床約束符合情況，當(dāng)發(fā)現(xiàn)有一項(xiàng)任務(wù)不滿足要求時(shí)，積分加1，可得表4所示對(duì)照表。

表4 任務(wù)與排產(chǎn)機(jī)床對(duì)照信息Table 4 Control information between tasks and production scheduling machines

只有當(dāng)排產(chǎn)積分S= 0時(shí)，該排產(chǎn)才是有效的，才是可行解。

同時(shí)任務(wù)還有優(yōu)先級(jí)順序，因此對(duì)每一個(gè)機(jī)床上加工任務(wù)采用積分SPr的方式進(jìn)行驗(yàn)證，最后將所有機(jī)床的積分相加，得到的分值為該排產(chǎn)計(jì)劃的任務(wù)優(yōu)先級(jí)約束積分。

積分規(guī)則為：設(shè)第j個(gè)機(jī)床上的第i個(gè)任務(wù)的優(yōu)先級(jí)為，第j個(gè)機(jī)床的積分為。將與（0時(shí)，積分加上（-）；當(dāng)≤時(shí)，積分加上0分，公式為

其中，

n為j機(jī)床上加工分配到的任務(wù)數(shù)量。

排產(chǎn)計(jì)劃的總得分SPr為

式中，NMT為機(jī)床數(shù)量。

根據(jù)式 （9）可分別計(jì)算得到MT1～MT4機(jī)床的任務(wù)優(yōu)先級(jí)積分，即

總積分為9。

2.2.4 更新策略設(shè)計(jì)

根據(jù)更新公式 （式 （5）和 （6））及機(jī)床約束、任務(wù)優(yōu)先級(jí)約束，可得具體迭代過程如下。

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

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

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

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

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

（1）記錄原各個(gè)任務(wù)對(duì)應(yīng)的向量序號(hào)；

（2）根據(jù)更新公式，計(jì)算獲取下一代任務(wù)序列；

（3）將任務(wù)序列從低到高進(jìn)行排序；

（4）提取排序后的任務(wù)序列對(duì)應(yīng)的向量序號(hào)，作為新的任務(wù)序列。

2.3 算法性能測試

通過MATLAB對(duì)粒子群算法以及生產(chǎn)線模型進(jìn)行實(shí)際測試的種群數(shù)量為80個(gè)，迭代次數(shù)為50次，學(xué)習(xí)因子c1= 2，c2= 2，慣性權(quán)重w= 0.75，運(yùn)算10次，測試結(jié)果如表5所示。

表5 測試結(jié)果Table 5 Test results

由運(yùn)算結(jié)果可以看出，使用沒有經(jīng)過改進(jìn)的粒子群算法對(duì)工件任務(wù)進(jìn)行排產(chǎn)，所有的排產(chǎn)結(jié)果均不能滿足機(jī)床約束和任務(wù)優(yōu)先級(jí)約束的要求。

2.4 排產(chǎn)算法優(yōu)化

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

根據(jù)上述分析可知，求解失敗是因?yàn)榍蠼饽繕?biāo)過多，導(dǎo)致問題規(guī)模過大，最終在局部極值時(shí)收斂。因此，可通過減少粒子群優(yōu)化算法的求解目標(biāo)來降低問題規(guī)模，實(shí)現(xiàn)對(duì)FJSP問題的求解。

本文減少的求解目標(biāo)為機(jī)床約束積分與任務(wù)優(yōu)先級(jí)約束積分，保留任務(wù)總完工時(shí)間和任務(wù)總超期時(shí)間。

生成粒子時(shí)，工件將會(huì)分配到機(jī)床上，此時(shí)通過查詢工件任務(wù)信息表即可知道工件是否符合機(jī)床約束的條件，若不符合約束要求，則對(duì)粒子進(jìn)行調(diào)整，使其滿足要求。調(diào)整規(guī)則如下：

（1）工件任務(wù)對(duì)機(jī)床的約束為“只能在4軸機(jī)床上加工”時(shí)，隨機(jī)選取一個(gè)4軸機(jī)床作為工件任務(wù)的加工機(jī)床；

（2）工件任務(wù)對(duì)機(jī)床的約束為“只能在5軸機(jī)床上加工”時(shí)，隨機(jī)選取一個(gè)5軸機(jī)床作為工件任務(wù)的加工機(jī)床；

（3）工件任務(wù)對(duì)機(jī)床的約束為“指定在某臺(tái)機(jī)床上加工”時(shí)，將工件任務(wù)的加工機(jī)床設(shè)置為指定的機(jī)床。

通過上述規(guī)則調(diào)整后獲得粒子的機(jī)床約束都滿足要求，以此減少了“機(jī)床約束積分”求解目標(biāo)。

為使工件的優(yōu)先級(jí)滿足要求，通過以下規(guī)則對(duì)機(jī)床的加工任務(wù)序列進(jìn)行調(diào)整：

（1）將工件優(yōu)先級(jí)從高到低重新排序，生成新的序列；

（2）當(dāng)前后工件的優(yōu)先級(jí)相同時(shí)，不對(duì)工件的前后位置關(guān)系進(jìn)行調(diào)整。

通過上述規(guī)則調(diào)整后獲得的粒子的優(yōu)先級(jí)約束都滿足要求，以此減少了“任務(wù)優(yōu)先級(jí)約束積分”求解目標(biāo)。

3 算法仿真結(jié)果

通過MATLAB對(duì)優(yōu)化后的粒子群算法進(jìn)行實(shí)現(xiàn)，以上述任務(wù)為對(duì)象，進(jìn)行算法的性能、效率與可行性驗(yàn)證。

第1次測試的種群數(shù)量為60個(gè)，迭代次數(shù)為50次，學(xué)習(xí)因子c1= 2，c2= 2，慣性權(quán)重W= 0.75，運(yùn)算10次，結(jié)果如表6所示。

表6 優(yōu)化后的算法第一次測試結(jié)果Table 6 First test results of optimized algorithms

表6中運(yùn)算結(jié)果按照“任務(wù)總超期時(shí)間/任務(wù)總完工時(shí)間”進(jìn)行呈現(xiàn)，如“0/152”表示任務(wù)總超期時(shí)間為0 min，任務(wù)總完工時(shí)間為152 min；其中的最優(yōu)解任務(wù)向量與最優(yōu)解機(jī)床向量共同構(gòu)成一個(gè)解向量。

10次運(yùn)算中的最優(yōu)結(jié)果為“0/143”，其收斂過程如圖3（a）所示，可以看出，總完工時(shí)間最初為163 min，經(jīng)過27次迭代后，收斂到143 min。

圖3 最優(yōu)結(jié)果“0/143”的收斂過程和排產(chǎn)計(jì)劃Fig.3 Convergence process and production schedule of the optimal result "0/143"

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

第2次測試的種群數(shù)量為100個(gè)，迭代次數(shù)為100次，學(xué)習(xí)因子c1= 2，c2= 2，慣性權(quán)重w= 0.75，運(yùn)算10次。其最優(yōu)結(jié)果為“0/146”，收斂過程如圖4所示,可以看出，總完工時(shí)間最初為163 min，經(jīng)過37次迭代后，收斂到146 min。

圖4 最優(yōu)結(jié)果“0/146”的迭代收斂過程Fig.4 Convergence process of the optimal result "0/146"

通過對(duì)比算法優(yōu)化前與優(yōu)化后的運(yùn)算結(jié)果發(fā)現(xiàn)，優(yōu)化后的所有最優(yōu)解的超期時(shí)間均為0，因此所有的解均為有效解，獲得有效解的概率為100%，而優(yōu)化前的算法獲得有效解的概率為0。由此可見通過較少求解目標(biāo)以降低問題規(guī)模的優(yōu)化方法對(duì)求解本文中生產(chǎn)線排產(chǎn)問題是可行的。

4 算法性能對(duì)比分析

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

表7 算法性能對(duì)比結(jié)果Table 7 Comparison results of algorithm performance

從測試結(jié)果來看，文獻(xiàn)[14-15]中算法的計(jì)算結(jié)果與改進(jìn)前的PSO算法計(jì)算結(jié)果類似，均不能求解出滿足機(jī)床約束和工件優(yōu)先級(jí)約束的最優(yōu)解。

5 結(jié)論

（1）以實(shí)際生產(chǎn)線為研究對(duì)象，分析調(diào)度需求，考慮工況中緊急插單、指定機(jī)床、任務(wù)優(yōu)先級(jí)等情況，對(duì)生產(chǎn)線進(jìn)行建模。

（2）提出一種帶粒子調(diào)整環(huán)節(jié)的粒子群優(yōu)化算法，在種群粒子初始化以及種群粒子更新后，新增粒子調(diào)整環(huán)節(jié)，在調(diào)整環(huán)節(jié)對(duì)粒子進(jìn)行局部范圍的定向編排優(yōu)化，得到求解結(jié)果。

（3）設(shè)計(jì)了兩組對(duì)比試驗(yàn)，試驗(yàn)結(jié)果表明，調(diào)整環(huán)節(jié)極大提高了排產(chǎn)算法的求解速度與求解質(zhì)量，求解成功率為100%。