基于改進粒子群算法求解分布式多工廠生產(chǎn)調(diào)度問題

王仕存，唐敦兵，朱海華，聶慶煒，潘俊峰，楊雷

(1. 南京航空航天大學(xué) 機電學(xué)院，江蘇 南京 210016；2. 江蘇天安智聯(lián)科技股份有限公司，江蘇 無錫 214171)

0 引言

隨著云制造[1]和生產(chǎn)全球化的不斷發(fā)展，基于云平臺的大規(guī)模協(xié)同制造漸漸成為國內(nèi)外制造業(yè)研究的重點。在此背景下，傳統(tǒng)集中式制造工廠漸漸向分布式工廠轉(zhuǎn)變[2]。隨著工廠數(shù)目的增多，傳統(tǒng)的車間調(diào)度已難以滿足云平臺的需要。如何對各個分布式工廠的生產(chǎn)任務(wù)進行合理有效的調(diào)度，已成為當(dāng)前迫切需要解決的問題。

近年來，國內(nèi)外對分布式多工廠生產(chǎn)調(diào)度問題(distributed multi-plants production scheduling problem，DMPPSP)進行了相關(guān)的研究。根據(jù)車間之間是否存在交互，本文將每個工廠劃分為多個獨立的柔性制造單元(flexible manufacturing unit，F(xiàn)MU)，把DMPPSP轉(zhuǎn)化為分布式柔性車間調(diào)度問題(distributed and flexible job shop scheduling problem, DFJSP)，從而解決了DMPPSP的問題。

由于該問題包含柔性作業(yè)車間調(diào)度問題(flexible job shop scheduling problem, FJSP)，屬于NP-hard問題[3]，目前研究多采用智能優(yōu)化算法進行求解。在國外，CHAOUCH I等[4]在混合蟻群算法的基礎(chǔ)上提出了一套新型的動態(tài)調(diào)度規(guī)則，高效求解了DMPPSP；MARZOUKI B等[5]為了得到最小化、最大完工時間，采用了基于化學(xué)反應(yīng)優(yōu)化的元啟發(fā)式算法進行求解；在國內(nèi)，吳銳等[6]設(shè)計了一種包含三維向量的編碼方案，運用改進人工蟻群算法提升了算法的局部搜索能力。這些研究都在一定程度上解決了DMPPSP，但其算法多數(shù)存在不確定性大、易陷入局部最優(yōu)解的缺陷。

本文將DMPPSP轉(zhuǎn)化為DFJSP，提出了一種改進的混合粒子群算法，提高了全局搜索能力，實現(xiàn)了以最小化、最大完工時間為目標(biāo)的分布式多工廠生產(chǎn)調(diào)度問題的求解。

1 分布式柔性車間調(diào)度問題

1.1 符號描述

文中使用的符號含義如表1所示。

表1 符號含義表

1.2 問題描述

問題描述：云平臺上存在工件類型集合為T={T1，T2，…，Tt}的待加工工件集合J={J1，J2，…，Jn}，需要將J中的工件分配至FMU集合U={U1，U2，…，Ur}進行加工，其中各個FMU與倉庫中心的距離集合為H={H1，H2，…，Hr}。每個FMU有多個加工機器Mu={Mu,1,Mu,2,…,Mu,lu}，每個工件加工過程共分為pi道工序。

由上述描述可知，DFJSP分為3個子問題，即FMU選擇、機器選擇和工序選擇，如圖1所示。

圖1 DFJSP示意圖

1.3 模型建立

本文模型基于的假設(shè)如下：

假設(shè)1：在初始時刻，待加工工件集合確定，F(xiàn)MU內(nèi)任何機器都可用；

假設(shè)2：每個FMU都能加工任意類型的工件，每個工件只能分配至一個FMU；

假設(shè)3：每個機器在某一時刻只能最多加工一個工件；

假設(shè)4：每個工件的某個工序只能被某個機器連續(xù)獨立加工完成；

假設(shè)5：同一個FMU內(nèi)的同類型加工機器對同一道工序的加工效果相同。

基于以上假設(shè)，本文建立了以最小化、最大完工時間為目標(biāo)函數(shù)的模型，如下所示。

目標(biāo)函數(shù)：

(1)

約束條件：

Di,j≤Bi,j+1

(2)

Qu,m,c-Pu,m,c=tu,m,i,j

(3)

Pu,m,c+1≥Qu,m,c

(4)

(5)

(6)

(7)

其中：式(2)表示各工件工序具有先后順序；式(3)表示每個機器正在加工的工序不能被打斷；式(4)表示單個機器加工具有順序性，在同一時刻只能加工一個工件；式(5)表示每個工件只能分配給一個FMU進行加工；式(6)表示各個FMU有能力加工完成任意工件；式(7)表示工件的每個工序只能分配至一個機器上進行加工。

2 模型求解

2.1 整體思想

模型求解的整體思路為將機器選擇和工序選擇作為FJSP嵌套于FMU的選擇問題中。FMU選擇產(chǎn)生的解作為FJSP的輸入，F(xiàn)JSP的輸出作為FMU選擇解的評價指標(biāo)，用于指導(dǎo)FMU選擇產(chǎn)生更優(yōu)解。

由于該研究問題屬于NP-hard問題，故選用粒子群算法進行求解。標(biāo)準(zhǔn)粒子群算法收斂速度快，能夠較為容易地得到較優(yōu)解，但同時存在著早熟收斂的缺陷[7]。為了解決該問題，本文對標(biāo)準(zhǔn)粒子群算法進行改進，提出了基于二階振蕩的隨機權(quán)重混合粒子群算法(RWSecVibratPSO)，提高算法的全局搜索能力，算法流程圖如圖2所示。

圖2 RWSecVibratPSO流程圖

2.2 算法具體設(shè)計

算法分為FMU選擇和FJSP兩部分。FMU選擇嵌套FJSP。二者均采用RWSecVibratPSO算法進行求解。

a)FMU選擇

1)粒子編碼

本文設(shè)計FMU選擇的每個粒子表示的信息為各個待加工工件分配至各個FMU的概率，概率變化范圍為(0,1)。

2)粒子初始化

假設(shè)單個粒子的維度為D1，則每個粒子的速度和位置可分別表示為vi=(vi1,vi2,…,viD1)和xi=(xi1,xi2,…,xiD1)。隨機初始化各粒子的速度和位置，并將各粒子的位置進行轉(zhuǎn)化，得到各個FMU的分配方案。

本文選擇FJSP作為FMU選擇的適應(yīng)度函數(shù)。FJSP的輸入為粒子產(chǎn)生的各個FMU的分配方案，輸出為FJSP的最小化、最大完工時間。考慮到各個FMU與倉庫中心的距離不同，故根據(jù)距離設(shè)計影響系數(shù)τu，將各個FMU的最小化、最大完工時間乘以τu得到的結(jié)果作為單個FMU的最小化、最大完工時間。比較各個FMU的最小化、最大完工時間，取最大值作為該粒子的適應(yīng)度，并初始化局部最優(yōu)適應(yīng)度與全局最優(yōu)適應(yīng)度。

3)粒子更新策略

針對早熟收斂的問題，本文提出了改進的混合粒子群算法RWSecVibratPSO，利用二階振蕩提高全局搜索能力，同時引入隨機權(quán)重，平衡全局和局部搜索能力。該算法的速度與位置更新方程如下：

vij(t+1)=ωvij(t)+c1r1[pij(t)-(1+ξ1)xij(t)+ξ1xij(t-1)]+

c2r2[pgd-(1+ξ2)xij(t)+ξ2xij(t-1)]

(8)

xij(t+1)=xij(t)+vij(t+1)

(9)

ω=μ+σ×N(0,1)

(10)

μ=μmin+(μmax-μmin)×rand(0,1)

(11)

在前二分之一迭代次數(shù)中，取

(12)

在后二分之一迭代次數(shù)中，取

(13)

式中：ω為隨機權(quán)重；c1與c2為學(xué)習(xí)因子；r1、r2和rand(0,1)為0～1的隨機數(shù)；ξ1和ξ2為隨機數(shù)，表示二階振蕩的搜索能力，前期利用式(12)提高全局搜索能力，后期利用式(13)提高局部搜索能力；pij為粒子i的局部最優(yōu)適應(yīng)度；pgd為粒子群的全局最優(yōu)適應(yīng)度；μ、μmax和μmin分別為隨機權(quán)重平均值、最大值和最小值；σ為隨機權(quán)重方差；N(0,1)為符合正態(tài)分布的隨機數(shù)。

b)FJSP

1)粒子編碼

本文FJSP的粒子表示工件在加工序列中下一個被加工的概率。通過對概率排序，根據(jù)工件的工藝規(guī)程得到相應(yīng)的加工序列。

2)粒子初始化

隨機初始化粒子的速度與位置，經(jīng)排序后得到加工序列，作為適應(yīng)度函數(shù)的輸入。

FJSP適應(yīng)度函數(shù)的核心是利用加工序列將加工任務(wù)分配至空閑的加工機器。分配的原則為保證當(dāng)前工序結(jié)束時間盡可能早。

根據(jù)FJSP的適應(yīng)度函數(shù)，可得到輸入加工序列的機器加工方案，從而確定最大完工時間的適應(yīng)度。根據(jù)初始化粒子的加工序列，可對其適應(yīng)度進行初始化，進而對局部最優(yōu)適應(yīng)度與全局最優(yōu)適應(yīng)度完成初始化。

3 仿真驗證與分析

為了驗證RWSecVibratPSO算法的有效性，本文設(shè)計了相關(guān)的仿真實驗，利用該算法對DMPPSP進行求解，同時選擇標(biāo)準(zhǔn)粒子群算法作為對比算法進行比較分析。

3.1 仿真實驗設(shè)計

設(shè)定共有3個分布式工廠，其與倉庫中心的距離的比值分別為130、110、100，包含的FMU分別為FMU1、FMU2和FMU3、FMU4。每個FMU包含多個加工機器，其中FMU1與FMU2均包含3臺車床、2臺銑床、2臺磨床與2臺鏜床，F(xiàn)MU3與FMU4均包含2臺車床、2臺銑床、2臺磨床與2臺鏜床。待加工工件共6種，每種工件的加工工序及加工時間如表2所示。現(xiàn)需要加工工件集合A={4,4,4,4,4,4}，其中各個數(shù)字表示從左到右的序號為工件類型的加工數(shù)量。各種類型工件的加工信息如表2所示。

表2 各種類型工件的加工信息

RWSecVibratPSO算法的參數(shù)設(shè)置分為FMU選擇和FJSP。對于FMU選擇，設(shè)定粒子個數(shù)為30，迭代次數(shù)為50。c1和c2分別取0.5和1.5。對于FJSP，設(shè)定粒子個數(shù)為50，迭代次數(shù)為50。c1和c2分別取2和2.1。隨機權(quán)重的取值兩部分相同，即ωmax、ωmin和σ分別取值為0.95、0.75和0.5。

由于各個FMU與倉庫中心的距離不同，故根據(jù)距離的比值設(shè)計τ1、τ2、τ3、τ4分別為1.3、1.1、1.1、1。

3.2 仿真結(jié)果分析

利用RWSecVibratPSO算法求解，得到一個較優(yōu)解，即將A分解成4部分，分別為{1,2,1,0,0,2}、{2,1,1,2,1,0}、{0,1,1,2,1,0}和{1,0,1,0,2,2}，并將其對應(yīng)分配至FMU1、FMU2、FMU3和FMU4。其最小化、最大完工時間為63.25。各個FMU調(diào)度安排的甘特圖如圖3所示。其中縱軸為各FMU的機器編號，橫軸為加工時間，不同顏色區(qū)塊對應(yīng)不同的加工工件，區(qū)塊上的編號與6的余數(shù)代表其對應(yīng)的工件類型，當(dāng)余數(shù)為0時代表第6種工件(本刊為黑白印刷，如有疑問可咨詢作者)。

圖3 各FMU調(diào)度的甘特圖

為驗證本文算法的優(yōu)越性，本文采用標(biāo)準(zhǔn)粒子群算法作為對比算法，與RWSecVibratPSO算法在粒子數(shù)為30、迭代次數(shù)為50的條件下，各獨立運行10次，比較兩種算法得到最小化、最大完工時間的最大值、最小值和平均值，如表3所示。

表3 RWSecVibratPSO與PSO結(jié)果對比表 單位：h

由表3可知，本文提出的算法相比于PSO算法具有較強的魯棒性和搜索性，在處理DMPPSP問題方面能力更優(yōu)。

4 結(jié)語

本文針對DMPPSP，將其轉(zhuǎn)化為DFJSP，提出了基于二階振蕩的隨機權(quán)重混合粒子群算法。首先明確了要研究的問題，構(gòu)建了DFJSP的數(shù)學(xué)模型；其次確定了算法的整體框架，將FJSP嵌套于FMU選擇中進行求解；再者，設(shè)計了基于二階振蕩的隨機權(quán)重混合粒子群算法，采用隨機權(quán)重平衡全局和局部搜索能力，利用學(xué)習(xí)因子的二階振蕩提高全局搜索能力；最后，通過實例仿真，驗證了本文算法的有效性和優(yōu)越性。