考慮次品處理的液壓缸制造車間動態調度研究

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

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

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

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

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

1 柔性作業車間動態調度模型

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

表1 次品處理動態擾動因素

表2 變量描述

決策變量如下:

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

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

目標函數為:

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)為動態調度擾動量ω最小,體現了動態調度給生產系統帶來的額外任務量;式(4)為一道工序只能被一臺機器加工;式(5)為工序加工順序約束;式(6)為一臺機器同時只能加工一道工序;式(7)為加工不可中斷;式(8)為次品處理工序的加工順序約束;式(9)為重投后所有工序重新加工。

2 改進帝國競爭算法

2.1 編碼和解碼

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

圖1 3×3規模問題編碼舉例

2.2 改進ICA算法

2.2.1 初始化國家

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

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

(10)

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

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

xij=uj+zij(vj-uj)

(11)

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

2.2.2 構建初始帝國

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

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

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

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

(12)

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

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

2.2.3 帝國同化

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

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

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

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

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

(13)

(14)

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

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:選擇一道關鍵工序,將其與其他工序做工序交換,若得到非支配解,則替換;否則繼續搜索,直到到達搜索上限g1,退出。

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

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

2.2.5 帝國競爭

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

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

(16)

(17)

TCP為帝國p的總成本,ξ為系數,一般取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為隨機數,取向量最大值對應的帝國l。

3 仿真結果分析

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

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

3.1 改進策略有效性分析

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

表3 策略分配

表4 算法結果對比

3.2 算法對比分析

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

表5 動態擾動詳情

表6 算法實驗數據

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

圖3 算法最優解對比圖

圖4 動態調度甘特圖

4 結論

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