唐紅濤,楊基源,張雁翔,張 偉

(1.武漢理工大學 機電工程學院,湖北 武漢 430070;2.韶關液壓件廠有限公司,廣東 韶關 512000;3.機器人與智能制造湖北省工程研究中心,湖北 武漢 430070)

液壓缸制造車間調度問題屬于典型的柔性作業(yè)車間調度問題(flexible job-shop scheduling problem, FJSP)。不良品檢驗以及次品處理是液壓缸零部件生產(chǎn)中不可或缺的環(huán)節(jié),而由于液壓缸“多品種,小批量”的生產(chǎn)模式以及其零部件毛坯價值較大等因素,導致次品處理在液壓缸生產(chǎn)過程中難以避免。次品處理程序使得原有加工需求發(fā)生變化導致初始調度方案不再最優(yōu),同時由于員工熟練度、機床老化等因素導致實際生產(chǎn)中次品處理常發(fā),因此急需研究考慮次品處理的液壓缸制造車間調度問題。

FJSP是經(jīng)典JSP(job-shop scheduling problem)的擴展,它允許給定集合的機器完成加工[1]。近年來有很多FJSP的擴展研究,如帶模糊加工時間的生產(chǎn)調度[2]、多目標車間調度[3]、分布式車間調度等[4]。而在應用中動態(tài)柔性作業(yè)車間調度問題(dynamic flexible job-shop scheduling problem, DFJSP)與實際環(huán)境更相似,能夠滿足不斷變化的車間環(huán)境[5]。如機器發(fā)生故障,使可用機器數(shù)量減少,從而導致原調度過程需要調整[6]。Nouiri[7]通過改進PSO(particle swarm optimization)算法解決了考慮能耗的動態(tài)柔性作業(yè)車間調度問題。高開周等[8]提出中斷和釋放的已調度任務來解決緊急訂單問題。吳正佳等[9]針對故障機器剩余工件構建了約束模型,提出了重調度方法。汪俊亮等[10]針對加工時間不確定的FJSP,采用冗余處理方法構建模型。

帝國競爭算法(imperialist competitive algorithm, ICA)是一種受社會和歷史的進化而啟發(fā)的群智能優(yōu)化算法[11]。針對ICA收斂過快易陷入局部最優(yōu)等問題,Lin等[12]提出攝動同化運動和邊界反彈改進了帝國同化方式。

1 柔性作業(yè)車間動態(tài)調度模型

FJSP可以描述為n個工件安排在m個機器上加工,每個工件有若干工序,確定加工方案來保證整體加工目標值最優(yōu)。DFJSP可以視為在FJSP的基礎上考慮擾動因子。筆者將次品處理擾動分為4類,具體如表1所示。相關變量符號及定義如表2所示。

表1 次品處理動態(tài)擾動因素

表2 變量描述

決策變量如下:

δijk:若工序Oij在機器k上加工為1,否則為0;

Fij:若工序Oij發(fā)生返工為1,發(fā)生返修為2,發(fā)生重投為3。

目標函數(shù)為:

minCmax=min[max(Cj)]

(1)

(2)

(3)

約束條件如下:

(4)

Ci(j+1)k-Pi(j+1)k+M(1-δi(j+1)k)≥Cijk?i,j,k

(5)

Cijk≤Sghk+M(1-γijghk) ?i,j,g,h,k

(6)

Cijk=Sijk+Pijk?i,j,k

(7)

當Fij=1或Fij=2時:

Ci(j+1)k-Pi(j+1)k+M(1-δi(j+1)k)≥Ci′j′kδijk=1

(8)

當Fij=3時:

(9)

式(1)為最大完工時間Cmax最小;式(2)為在制品庫存γ最小;式(3)為動態(tài)調度擾動量ω最小,體現(xiàn)了動態(tài)調度給生產(chǎn)系統(tǒng)帶來的額外任務量;式(4)為一道工序只能被一臺機器加工;式(5)為工序加工順序約束;式(6)為一臺機器同時只能加工一道工序;式(7)為加工不可中斷;式(8)為次品處理工序的加工順序約束;式(9)為重投后所有工序重新加工。

2 改進帝國競爭算法

2.1 編碼和解碼

FJSP采用雙層編碼即工序排序(operation sequence,OS)和機器選擇(machines selection,MS)兩部分,如圖1所示。OS部分中工件i第j次出現(xiàn)代表工序Oij,對應的MS部分為其加工的機器次序。

圖1 3×3規(guī)模問題編碼舉例

2.2 改進ICA算法

2.2.1 初始化國家

設置國家數(shù)量Npop、帝國數(shù)量Nimp等參數(shù)。引入Logistic 混沌映射迭代方程來完成初始化,映射迭代方程為:

y(k+1)=μy(k)(1-y(k)),k=1,2,…,n

(10)

式中:y(k)、y(k+1)分別為第k次、第k+1次混沌映射迭代中該編碼處的隨機數(shù);μ為方向參數(shù)。

定義個體維度為m,種群規(guī)模為N,隨機生成m維初始序列z1=(z11,z12,…,z1m),通過式(10)迭代從而得到初始混沌序列矩陣zlo。將zlo通過式(11)變換到目標問題的變量區(qū)間上,從而完成初始混沌映射。

xij=uj+zij(vj-uj)

(11)

式中,vj和ui分別為第j維變量取值的上界和下界。

2.2.2 構建初始帝國

針對多目標優(yōu)化問題,給出了一種簡化的帝國初始化機制,步驟如下:

步驟1對種群Npop進行Pareto非支配排序,得到大小為n的第一前沿解集Π;

步驟2如果第一前沿解的數(shù)量n<算法所定的帝國數(shù)量imp,則對Π進行局部搜索生成外部種群Nn,將Nn放入種群Npop中,執(zhí)行步驟1;否則執(zhí)行步驟3;

步驟3隨機選擇Π中的imp個個體為殖民國家,由式(12)可計算帝國分配的殖民地數(shù)。

(12)

式中:NCi為第i個帝國中的殖民地數(shù)量;pop為所有國家數(shù)量;a為隨機參數(shù)。

步驟4:將Npop中剩余的col個個體按Rank等級排序,并交替分配給殖民國家。

2.2.3 帝國同化

引入文化入侵概念,即殖民地在向殖民國家同化時,有一定概率向其他殖民國家學習。步驟如下:

步驟1殖民地kcol,與其殖民國家同化得到子代k1,若k1是的kcol非支配解,則保留k1;

步驟2隨機選擇殖民國家,使kcol與之同化得到子代k2,若k2支配kcol,則保留;

步驟3在k1和k2均存在的情況下,取隨機數(shù)χ和文化入侵概率ε,若χ<ε,則k2取代kcol;反之,則k1替代kcol作為新的殖民地。

同化采用POX(precedence operation crossover)交叉,引入同化因子δ,通過影響轉移長度β來控制同化程度。ρ為(0,1)之間的隨機數(shù)。

(13)

(14)

式中,It和MaxIt分別是當前迭代數(shù)和總迭代次數(shù)。

2.2.4 帝國革命

針對帝國革命,設計了一種多層級反饋的鄰域搜索算子,按照復雜度把算子分為SNS(simple neighborhod search)、HNS(hard neighborhod search):

SNS計算簡單,能夠快速突變。

(15)

SNS2:隨機選擇兩道工序a和b,將工序b插到工序a之前,MS部分隨之變化。

SNS3:隨機選擇兩個工序,并反轉兩個位置的OS部分和MS部分。

HNS比SNS更為復雜,它在當前方案關鍵路徑的基礎上做變換。

設計兩種HNS結構,具體如下:

HNS1:針對關鍵路徑工序,使關鍵工序的加工機器突變,直到得到非支配解。

HNS2:選擇一道關鍵工序,將其與其他工序做工序交換,若得到非支配解,則替換;否則繼續(xù)搜索,直到到達搜索上限g1,退出。

帝國革命詳細步驟如下:對于殖民地個體kcol,引入革命概率η2,革命若發(fā)生,針對kcol做SNS 3種搜索,若產(chǎn)生非支配解k1,則k1替換kcol并終止革命;若無,則革命失敗。

對于殖民國家個體kimp,首先對kimp依次做SNS搜索若產(chǎn)生非支配解k1,則k1替換kcol并終止革命;若無且達到搜索上限g2,則對kimp做HNS搜索,若沒有非支配解的產(chǎn)生,則革命失敗;且之后該殖民地跳過SNS,直到kimp發(fā)生變化才恢復對kimp做SNS搜索。

2.2.5 帝國競爭

1.2.5 A 在進行工作過程中，管理人員應當根據(jù)實際情況對護理工作的開展進行分析，認真分析門診感染控制中存在的問題，總結護理結果，并根據(jù)標本的控制狀況對標本管理計劃進行完善。通過持續(xù)改進的方式，能夠有效的對管理期間的標本管理狀況進行分析，從而對管理方案進行改善。通過周而復始的實施，達到循環(huán)的目的。

筆者設計了一種保護最弱帝國策略。個體k的成本值ck可用式(16)進行計算:

(16)

(17)

TCP為帝國p的總成本,ξ為系數(shù),一般取0.1。NTCP為歸一化成本,EPP為帝國P的勢力。

(18)

NTCp=2×max(TC)-TCp

(19)

(20)

式中:cimp為帝國p中殖民國家的勢力值;cj為帝國p中殖民地的勢力值。

具體步驟如下:

步驟1對所有帝國按勢力值排序,勢力值最大的帝國不參與競爭。

步驟2取最差帝國的最差個體kwor。

步驟3生成一組隨機向量[EP2-r2,EP3-r3,EP4-r4,…,EPimp-rimp],其中r為隨機數(shù),取向量最大值對應的帝國l。

3 仿真結果分析

為測試改進ICA算法求解性能,進行實驗驗證,經(jīng)正交實驗得到算法參數(shù)設置為:種群規(guī)模population=50,最大迭代次數(shù)MaxIter=100。初始帝國數(shù)量Nimp=10,HNS搜索最大迭代次數(shù)g1=10,入侵概率ε=0.3。

采用 Brandimarte數(shù)據(jù)集中的8個標準經(jīng)典算例(MK01～MK08)擴展算例進行策略對比分析[13]以及某液壓件廠實際案例進行算法分析。

3.1 改進策略有效性分析

筆者設計了8個策略組合算法來分析改進策略的有效性,如表3所示,每個算法采用相同參數(shù),獨立運行MK01-MK08各10次。運算結果如表4所示,分別帶有改進策略的IICA-1～IICA-3在兩個目標上的平均值Avg和最優(yōu)值Best均小于初始ICA算法值;能夠證明策略的有效性。

表3 策略分配

表4 算法結果對比

3.2 算法對比分析

分別與現(xiàn)有文獻中的灰狼算法[14]、改進遺傳算法[15]、粒子群算法[16]、人工蜂群算法[17]進行算法對比,記錄每個算法運行10次的結果。某液壓件廠實際案例的初始調度甘特圖如圖2所示,模擬其發(fā)生動態(tài)擾動,擾動情況如表5所示。算法實驗數(shù)據(jù)如表6所示。

表5 動態(tài)擾動詳情

表6 算法實驗數(shù)據(jù)

從表6可知,IICA算法在3種情況下均取得了最優(yōu)解,證明了改進算法的有效性。以情況三為例,算法最優(yōu)解情況如圖3所示,動態(tài)調度后的最優(yōu)甘特圖如圖4所示。

圖3 算法最優(yōu)解對比圖

圖4 動態(tài)調度甘特圖

4 結論

研究考慮次品處置的液壓缸零部件車間多目標動態(tài)調度問題。在模型上,考慮了液壓缸裝配車間零部件繁多,提出了在制品庫存最小為調度目標。在算法上,以ICA算法核心框架為內核,通過引入文化入侵操作、保護最弱帝國的帝國競爭行為,保護了種群多樣性避免算法陷入局部最優(yōu)解。最后通過基準測試算例進行策略對比實驗,結果驗證了改進算法的有效性。