基于改進(jìn)的多目標(biāo)PSO算法的離散型FJSP的研究*

張 博，梁艷艷

(平頂山工業(yè)職業(yè)技術(shù)學(xué)院機(jī)械工程學(xué)院，平頂山 467001)

0 引言

現(xiàn)代制造業(yè)是制造業(yè)未來的發(fā)展方向[1]，已向柔性化、自動化方向發(fā)展[2]，并最終實(shí)現(xiàn)高效、柔性的智能化生產(chǎn)模式[3]。作業(yè)車間調(diào)度是生產(chǎn)企業(yè)面臨的復(fù)雜問題，特別是涉及多品種、小批量個性化定制的智能化生產(chǎn)[4]，其生產(chǎn)過程具有復(fù)雜性、離散型和動態(tài)性，需要給工序分配設(shè)備，其FJSP問題屬于NP-hard問題，是國內(nèi)外學(xué)者研究的焦點(diǎn)[5]。

目前，已有較多用于求解JSP問題的優(yōu)化方法和調(diào)度模型被提出，針對優(yōu)化方法的研究主要有遺傳算法[6]、拉格朗日松弛法[7]、模擬退火法[8]、遺傳算法[9-10]等。針對調(diào)度模型的研究主要是根據(jù)工件工序存在的不足設(shè)計(jì)最小化完工時間的調(diào)度模型，且考慮了加工設(shè)備的柔性[11]，以及考慮設(shè)備的惡化特性[12]、冗余特性[13]，分別建立滿足魯棒性和調(diào)度次序約束的多加工調(diào)度模型，獲得較好的調(diào)度效果。但是FJSP問題比一般的JSP問題具有更復(fù)雜、更困難性，且多品種、小批量智能生產(chǎn)過程具有離散型、多目標(biāo)和不確定性，面臨多機(jī)器選擇的問題，現(xiàn)有的研究主要集中在經(jīng)典的JSP問題設(shè)計(jì)優(yōu)化算法，以及作業(yè)加工順序是預(yù)先設(shè)計(jì)、加工設(shè)備是預(yù)先指定，不能很好的滿足離散型FJSP問題。且傳統(tǒng)算法求解時存在收斂速度慢、陷入局部最優(yōu)解等缺點(diǎn)。針對上述問題，將速度松弛迭代策略引入更新工序排序和設(shè)備分配粒子中，采用帶有壓縮因子和慣性權(quán)重相結(jié)合的策略改進(jìn)學(xué)習(xí)因子，以及將基于工序和機(jī)器的兩級基因策略引入粒子的編碼和解碼操作。最后利用離散制造業(yè)智能生產(chǎn)過程的FJSP算例進(jìn)行分析，驗(yàn)證了改進(jìn)粒子群算法的優(yōu)越性和求解效率。

1 離散型FJSP模型的建立

1.1 離散型FJSP的約束矩陣

在具體的智能制造生產(chǎn)模式下，柔性作業(yè)車間調(diào)度問題具有復(fù)雜性、動態(tài)性、多約束和多目標(biāo)等特點(diǎn)。按照復(fù)雜程度可分為單機(jī)和多機(jī)并行調(diào)度，按照性能指標(biāo)目標(biāo)可分為調(diào)度費(fèi)用和性能的優(yōu)化，按照生產(chǎn)環(huán)境可分為確定性和隨機(jī)性調(diào)度，按照加工特點(diǎn)可分為靜態(tài)和動態(tài)調(diào)度。

在柔性作業(yè)車間調(diào)度問題中，設(shè)有n個待加工工件，m臺機(jī)床設(shè)備，每個工件需要Pi道工序，每臺機(jī)床上共有Lj道工序，則：

工件集合N={N1,N2,…,Nn}；機(jī)床設(shè)備集合M={M1,M2,…,Mm}；工件Ni的工序集合PNi={PNi1,PNi2,…,PNipi}。

(1)

式中，P為n×max{P1,…,Pn}的工序矩陣；P(i,j)為第i個工件的第j道工序：

(2)

式中，JM為n×max{P1,…,Pn}的機(jī)器編號矩陣；JM(i,j)為第i個工件的第j道工序在機(jī)床上加工的編號。

(3)

式中，T為n×max{P1,…,Pn}的加工時間矩陣；T(i,j)為第i個工件的第j道工序在機(jī)床JM(i,j)上的加工時間。

車間柔性作業(yè)調(diào)度函數(shù)的最優(yōu)解表達(dá)式為：

(4)

式中，Mj為n×max{P1,…,Pn}的工件排列矩陣；Mj(i,j)為在機(jī)床i上排在第j個加工的工件序號。

離散型FJSP的目標(biāo)就是在滿足約束條件的情況下，選擇最合適的機(jī)床以及確定每臺機(jī)床上的最佳加工工序，最后使得調(diào)度系統(tǒng)的某些性能指標(biāo)最優(yōu)，約束條件如下[14-15]：

(1)所有機(jī)床一開始都處于空閑狀態(tài)；

(2)不同工件之間具備相同的優(yōu)先級，在0時刻，所有工件都可被加工；

(3)工件的工序之間沒有固定的先后順序，工序一旦進(jìn)行不能中斷；

(4)各工件的準(zhǔn)備時間和移動時間一起計(jì)入加工時間；

(5)每臺設(shè)備在同一時刻只能加工一道工序。

隨著車間智能化水平的提高及客戶個性化定制需求增多，柔性作業(yè)車間調(diào)度問題也由最開始的單目標(biāo)優(yōu)化變成現(xiàn)在的多目標(biāo)優(yōu)化，如最大完工時間和加工成本的最小化等。

表1描述了3種待加工工件和3臺機(jī)床設(shè)備的小批量的車間作業(yè)柔性調(diào)度問題，表中數(shù)據(jù)表示機(jī)床加工時間，“-”表示該設(shè)備不能完成本道工序的加工任務(wù)，機(jī)床設(shè)備M后的數(shù)據(jù)表示該設(shè)備單位時間的加工成本、工作能耗和閑置能耗。

表1 多品種小批量柔性作業(yè)調(diào)度示例

由表1可得到，柔性調(diào)度車間作業(yè)和工序之間的關(guān)聯(lián)矩陣為：

(5)

車間柔性作業(yè)調(diào)度時間矩陣為：

(6)

1.2 離散型FJSP的優(yōu)化目標(biāo)函數(shù)

本文構(gòu)建的離散型FJSP為多目標(biāo)動態(tài)調(diào)度模型，在實(shí)際生產(chǎn)中主要關(guān)心的調(diào)度優(yōu)化目標(biāo)有總加工時間T，總加工成本C，總能源消耗E，總加工質(zhì)量Q，工件加工過程負(fù)載平衡B。

(1)總加工時間T。生產(chǎn)過程的總加工時間T可用最大完工時間表示，實(shí)際生產(chǎn)取最小值。

T=max(Ti)

(7)

式中，Ti為機(jī)床設(shè)備M總體加工任務(wù)結(jié)束時間，i=1,2,…,m。

(2)總加工成本C。工件的加工成本C一般由原材料成本CM和工序加工成本CP組成。

(8)

式中，mci為工件i的原材料成本；Oijk為工件i的第j到工序在設(shè)備k上加工；Tijk為工件i的第j道工序在設(shè)備k上的加工時間；Pck為機(jī)床設(shè)備k單位時間的加工成本。

(3)工件加工過程負(fù)載平衡B。工件加工過程負(fù)載平衡E包括機(jī)床設(shè)備總負(fù)荷和瓶頸設(shè)備負(fù)荷。

(9)

綜上可知，柔性作業(yè)車間的多目標(biāo)動態(tài)調(diào)度目標(biāo)函數(shù)為：

F=(T,C,E,Q,B)

(10)

(4)總能源消耗E?？偰茉聪腅為完成所有加工任務(wù)所有機(jī)床設(shè)備耗能的總和，包括設(shè)備啟動能耗Es，加工能耗Ep和設(shè)備空載能耗Ee。

E=∑Es+∑Ep+∑Ee

(11)

(5)總加工質(zhì)量Q。總加工質(zhì)量Q采用工序成本加權(quán)質(zhì)量不穩(wěn)定系數(shù)來表示，則總的成本加權(quán)不穩(wěn)定系數(shù)為：

(12)

式中，Lijk表示設(shè)備k加工工件i的第j道工序的成本加權(quán)質(zhì)量不穩(wěn)定系數(shù)。

則調(diào)度的優(yōu)化目標(biāo)可表示為：

MinF=min(T,C,E,Q,B)

(13)

2 多目標(biāo)PSO算法的基本原理與改進(jìn)

2.1 車間調(diào)度問題優(yōu)化方法的對比分析

離散型FJSP作為多目標(biāo)優(yōu)化問題，其求解方法有多種，主要分為傳統(tǒng)方法和智能算法兩大類，如表2所示。

表2 柔性作業(yè)車間調(diào)度算法分類

由表2可知，傳統(tǒng)方法通過加權(quán)求和，將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)函數(shù)求解，這種方法對于復(fù)雜問題的處理響應(yīng)慢，容易出現(xiàn)局部最優(yōu)解現(xiàn)象，無法滿足實(shí)際生產(chǎn)需求，而智能算法使得離散型FJSP的求解易于獲得最優(yōu)解。多目標(biāo)粒子群優(yōu)化算法(particle swarm optimization,PSO)是一種群體智能算法，可通過粒子的位置和速度得到一組候選解決方案，并通過迭代來改進(jìn)候選方案，具有獨(dú)特的搜索機(jī)理和很好的收斂性，廣泛應(yīng)用于求解柔離散型FJSP領(lǐng)域。

2.2 多目標(biāo)PSO算法基本原理與流程

多目標(biāo)PSO算法來源于鳥群捕食行為的啟發(fā)，是一種群體智能的進(jìn)化計(jì)算技術(shù)。其基本思想是在觀察粒子集群行為的基礎(chǔ)上，利用個體粒子的信息共享使整個粒子群體的運(yùn)動在求解空間中產(chǎn)生最優(yōu)解的演化過程。

多目標(biāo)PSO算法在可行解空間中初始化一群粒子，每個粒子代表極值優(yōu)化問題的潛在最優(yōu)解，可用速度V、位置P和適應(yīng)度值F三項(xiàng)指標(biāo)表示每個粒子的特征。粒子在可行解空間中運(yùn)動，通過追蹤個體粒子適應(yīng)度最優(yōu)值Pbest的位置以及群體粒子適應(yīng)度最優(yōu)值Gbest的位置來更新個體位置。粒子每更新一次位置就計(jì)算一次適應(yīng)度值，個體極值和群體極值會隨著他們的位置變化而更新。

假設(shè)有M個粒子組成一個N維目標(biāo)的搜索空間，用第i個粒子表示一個N維向量，則，

第i個粒子的位置Pi為：

Pi=(Pi1,Pi2,…,PiN),i=1,2,…,M

第i個粒子移動的速度Vi為：

Vi=(Vi1,Vi2,…,ViN),i=1,2,…,M

第i個粒子搜索的個體最優(yōu)位置Ebest為：

Ebest=(Pi1,Pi2,…,PiN),i=1,2,…,M

群體粒子搜索的全局最優(yōu)位置Gbest為：

Gbest=(Pg1,Pg2,…,PgN)

(14)

多目標(biāo)PSO算法采用學(xué)習(xí)因子及慣性權(quán)重來更新速度和位置，其公式為：

(15)

式中，C1和C2是學(xué)習(xí)因子，一般取C1=C2∈[0,4]；ωk是慣性常量；R1和R2是[0,1]范圍內(nèi)的隨機(jī)數(shù)。

多目標(biāo)PSO算法主要分為：①初始化粒子群；②評價粒子(計(jì)算適應(yīng)度值)；③尋找個體最優(yōu)解值Pbest；④尋找全局的最優(yōu)解值Gbest；⑤修改粒子的速度和位置。其程序流程圖如圖1所示。

圖1 PSO算法的基本流程圖

2.3 改進(jìn)的多目標(biāo)PSO算法在離散型FJSP中的設(shè)計(jì)

(1)初始化參數(shù)。由基礎(chǔ)粒子群算法思想可知，學(xué)習(xí)因子C1、C2以及慣性權(quán)重因子ωk的取值對多目標(biāo)PSO算法的性能有較大影響。因此，通過改進(jìn)學(xué)習(xí)因子和慣性權(quán)重達(dá)到改善多目標(biāo)PSO算法的目的。

采取帶有壓縮因子的方式來改進(jìn)學(xué)習(xí)因子，使粒子的更新公式為：

(16)

隨著迭代次數(shù)的增加，慣性權(quán)重從最大變化到最小，改進(jìn)后慣性權(quán)重的表達(dá)式為：

(17)

(2)粒子編碼方法設(shè)計(jì)。在智能加工過程中，工序和機(jī)器的選擇順序十分重要，可將加工工序和加工機(jī)器看著兩級基因的策略進(jìn)行編碼，加工工序基因可確定作業(yè)在備選設(shè)備上對應(yīng)的加工順序，加工機(jī)器基因可確定作業(yè)加工順序?qū)?yīng)的加工機(jī)器的使用編號。

表1中所示的多品種小批量柔性作業(yè)車間調(diào)度模型包含4種產(chǎn)品、3臺加工機(jī)器、8道工序，基因編碼長度為8，根據(jù)上述編碼策略形成的粒子編碼序列如圖2所示。

圖2 粒子編碼方法

因此，圖2中所示的粒子編碼基因?qū)?yīng)的工序和機(jī)器順序?yàn)椋篬(O31,M2),(O11,M3),(O21,M1),(O12,M2),(O22,M2),(O23,M3),(O13,M2),(O32,M1)]。

多目標(biāo)PSO算法的解碼過程是為了尋找多目標(biāo)優(yōu)化問題的可行解，進(jìn)而得到車間調(diào)度方案。假設(shè)工件i的第j道工序開始加工時間為Sijk，加工時間為Tijk，則染色體解碼時工序Oij開始加工時間為：

Sijk=max(Si[j-i]+Ti[j-1],Sk[q-1]+Tk[q-1])

(18)

式中，Si[j-1]和Sk[q-1]分別表示工件上一道工序的開始加工時間；Ti[j-1]和Tk[q-1]分別表示上一道工序的加工時間。如果按照上述方式進(jìn)行編碼，解碼后得到的只是染色體對應(yīng)的半主動調(diào)度解。此時，需要按照工序的排序進(jìn)行編碼，然后盡可能早的將開始加工時刻往前移動到對應(yīng)的加工設(shè)備上，直至所有工序都被合理的安排到最佳加工位置。

(3)粒子更新和條件設(shè)置。加工工序基因和加工機(jī)器基因采取隨機(jī)的方式進(jìn)行，設(shè)置群體規(guī)模為m。需要設(shè)置最大的速度區(qū)間，防止超出最大的區(qū)間。位置信息即為整個搜索空間，在速度區(qū)間和搜索空間上隨機(jī)設(shè)置初始化速度和位置。

為了獲得全局最優(yōu)解，將速度松弛迭代策略和引入多目標(biāo)PSO算法中，不僅可以減小更新速度時的運(yùn)算量還可以增強(qiáng)粒子的局部搜索能力，加快運(yùn)算的收斂性。速度松弛迭代策略定義如下：

(19)

在更新粒子位置時，需要對粒子的邊界進(jìn)行限定，設(shè)置粒子尋優(yōu)空間的上限和下限。

(4)算法終止條件。最大迭代次數(shù)Gmax滿足設(shè)定的要求時，算法停止，輸出最優(yōu)解。

3 改進(jìn)的多目標(biāo)PSO算法在離散型FJSP中的應(yīng)用案例分析

某智能化生產(chǎn)車間有6臺加工設(shè)備，加工有工序間相互約束關(guān)系的6個加工工件，共有17道加工工序的離散型FJSP實(shí)例，所需部分初始數(shù)據(jù)如表3所示。根據(jù)第1.2節(jié)構(gòu)建離散型FJSP優(yōu)化模型，優(yōu)化目標(biāo)為：總加工時間T、總加工成本C、總能源消耗E、總加工質(zhì)量Q和工件加工過程負(fù)載平衡B。為了簡化分析過程，只考慮機(jī)床一種資源，且不考慮機(jī)床故障和急件等非確定性因素。

表3 車間柔性作業(yè)調(diào)度實(shí)例分析

試驗(yàn)環(huán)境在Windows 10平臺(硬件參數(shù)：CPU Intel(R) Core(M) 2.30 GHz 8 GB)，編程環(huán)境：MATLAB R2018a。參數(shù)設(shè)置：粒子個數(shù)PN=1000，IN=200，初始慣性權(quán)重ω0=0.8，最終慣性權(quán)重ωk=0.2，初始學(xué)習(xí)因子C1=3.5，初始學(xué)習(xí)因子C2=0.5。

求解后，得到的最優(yōu)目標(biāo)為：最優(yōu)化最大加工時間為29 h，最優(yōu)加工成本為704元，最優(yōu)加工過程負(fù)載平衡為32.8 W，最優(yōu)化能源消耗為23J，最優(yōu)化加工質(zhì)量為260。離散型FJSP的Pareto前沿解如圖3和圖4所示。

圖3 Pareto前沿解(加工時間/機(jī)床負(fù)荷/加工成本) 圖4 Pareto前沿解(加工時間/機(jī)床負(fù)荷)

輸出的一組工序?qū)?yīng)的機(jī)床加工分配情況，如表4所示。在表4中，用“＊”表示該工件的該道工序需要該機(jī)床設(shè)備進(jìn)行加工，空白表示改道工序暫時未用到該臺設(shè)備進(jìn)行加工。

表4 工序加工機(jī)床分配表

以工件的最優(yōu)化最大機(jī)床加工時間為決策對象，可獲得這組調(diào)度方案對應(yīng)的離散型FJSP優(yōu)化調(diào)度方案甘特圖，如圖5所示，圖中縱坐標(biāo)序號表示加工機(jī)床編號，橫坐標(biāo)表示機(jī)床加工時間，甘特圖中的文字“4,2”表示工件4的第2道工序。

圖5 考慮最優(yōu)化機(jī)床加工時間調(diào)度方案甘特圖

可以看出，此時機(jī)床總加工時間的最優(yōu)值為29 h，調(diào)度算法對工序的安排緊湊合理，有效的提高了設(shè)備利用率。并且借助計(jì)算機(jī)進(jìn)行調(diào)度可減少人工調(diào)度產(chǎn)生的誤差，因此本文提出的調(diào)度方法對求解離散型FJSP車間問題是可行且有效的，不僅提高了算法的性能，還降低了算法陷入局部最優(yōu)解的幾率。最后通過仿真實(shí)驗(yàn)和與其它實(shí)驗(yàn)的對比分析， 可以看出不管對于部分柔性和完全柔性作業(yè)車間調(diào)度， 改進(jìn)的蟻群算法均可快速求得最優(yōu)解。 證明改進(jìn)蟻群算法在求解柔性作業(yè)車間調(diào)度不同規(guī)模算例中的優(yōu)越性

4 結(jié)論

針對傳統(tǒng)的優(yōu)化算法收斂速度慢、求解效率低，無法滿足離散制造業(yè)中多品種、小批量智能生產(chǎn)過程的FJSP優(yōu)化問題，本文在粒子群算法的基礎(chǔ)上，將速度松弛迭代策略引入更新工序排序和設(shè)備分配中，且將帶有壓縮因子和慣性權(quán)重相結(jié)合的策略用于改進(jìn)粒子群的學(xué)習(xí)因子，并采用基于工序和機(jī)器的兩級基因策略進(jìn)行編碼和解碼操作，提高了算法的優(yōu)化性能，擴(kuò)大了算法的搜索范圍，避免陷入局部最優(yōu)解。最后通過實(shí)例分析，對于離散制造業(yè)智能生產(chǎn)中柔性作業(yè)車間調(diào)度問題，改進(jìn)的粒子群算法可快速獲得最優(yōu)解，說明改進(jìn)粒子群算法在求解智能生產(chǎn)的FJSP問題的優(yōu)越性。