考慮訂單加急生產(chǎn)的柔性車間作業(yè)動態(tài)調(diào)度*

朱旭東

(無錫工藝職業(yè)技術學院,江蘇 宜興 214200)

0 引 言

隨著車間生產(chǎn)的智能化程度和柔性程度不斷提高,目前的車間機床可以加工多工件的多種工序,且工序在不同機床上的生產(chǎn)加工效率也可以不一致[1]。

合理的柔性車間調(diào)度方案可以有效提升車間的生產(chǎn)效率,體現(xiàn)企業(yè)的核心競爭力[2]。因此,研究柔性車間的生產(chǎn)調(diào)度問題具有重要的經(jīng)濟意義和實用價值。

柔性車間動態(tài)調(diào)度是在靜態(tài)調(diào)度基礎上,考慮生產(chǎn)擾動的一類調(diào)度問題。生產(chǎn)干擾主要由加工的中斷因素和不確定事件所引起,包括機床故障、緊急插單、加急生產(chǎn)、任務隨機到達等因素[3]。

根據(jù)優(yōu)化目標分類,柔性車間動態(tài)調(diào)度問題可以分為完工時間優(yōu)化、能耗優(yōu)化和負載均衡優(yōu)化等[4]。根據(jù)優(yōu)化目標數(shù)量分類,柔性車間動態(tài)調(diào)度問題可以分為單目標調(diào)度問題和多目標調(diào)度問題[5]。從動態(tài)調(diào)度算法的角度出發(fā),柔性車間動態(tài)調(diào)度問題又可以分為精確求解算法和啟發(fā)類求解算法。

其中,精確求解算法是基于梯度的一類求解方法,該方法的優(yōu)點是可以獲得算法的精確最優(yōu)解,且收斂速度較快;其缺點是只適用于小規(guī)模調(diào)度問題,且計算量較大。

啟發(fā)類求解方法是基于元啟發(fā)算法的一類求解方法。常見啟發(fā)類求解算法包括遺傳算法、粒子群算法等[6,7]。該類方法的優(yōu)點是適用于大規(guī)模調(diào)度問題、計算量適中,缺點是調(diào)度方案的優(yōu)劣與算法性能優(yōu)劣直接相關,不能保證一定獲得最優(yōu)解。

尤一琛等人[8]研究了機器發(fā)生隨機故障時的車間動態(tài)調(diào)度問題,設計了組合重調(diào)度策略,并使用精英選擇遺傳算法對其進行了求解,實現(xiàn)了機械故障條件下重調(diào)度的目的。張國輝等人[9]基于改進帝國競爭算法,研究了機械故障發(fā)生時的車間重調(diào)度問題,并在3種機器故障情景下,驗證了該方法的可行性與有效性。模糊加工時間和新訂單插入兩種擾動下,RAKOVITIS N等人[10]研究了車間的重調(diào)度問題,提出了采用兩階段人工蜂群算法求解重調(diào)度的方法,經(jīng)測試,該方法調(diào)度結果優(yōu)于另外7種現(xiàn)有的算法調(diào)度結果。

上述針對中斷因素和不確定事件的車間動態(tài)重調(diào)度問題中,研究人員主要研究了由機械故障、新訂單插入、訂單加工事件模糊等因素導致的重調(diào)度問題,而針對現(xiàn)有訂單的加急生產(chǎn)擾動的相關研究較少。但是當前市場需求瞬息萬變,因此,客戶依據(jù)市場而具有時變的生產(chǎn)需求是常見情況。

筆者針對上述問題進行研究。首先,根據(jù)預先設定的生產(chǎn)需求,提出基于強制進化遺傳算法的靜態(tài)調(diào)度方法;然后,當發(fā)生訂單加急生產(chǎn)擾動時,設計具有記憶功能的優(yōu)先生產(chǎn)通道,該生產(chǎn)通道能夠根據(jù)訂單緊急程度,自適應地調(diào)整相應生產(chǎn)機床;最后,在生產(chǎn)車間中,對該研究的重調(diào)度方法進行驗證。

1 問題描述與建模

1.1 訂單加急的動態(tài)重調(diào)度問題描述

訂單擾動可以分為訂單插入和訂單加急兩類,訂單插入是指原本不在計劃中的訂單插入到當前生產(chǎn)節(jié)奏中;訂單加急是指本來就在計劃中的訂單,要求加急生產(chǎn)[11]。

此處,筆者研究的是訂單加急擾動下的柔性車間動態(tài)重調(diào)度問題。

假設具有N個工件生產(chǎn)任務,記為{T1,T2,…,TN},工件i的第j道生產(chǎn)工序記為Oij,工件i的工序數(shù)量記為Ji;車間中具有K個加工機床,記為{M1,M2,…,MK}。每個機床具有加工不同工序的能力,每個工序允許選擇不同的機床。由于機床性能的差異性,同一工序在不同機床上的加工時間是不一致的。

柔性車間生產(chǎn)調(diào)度是指:通過合理地安排工序的加工順序和對應機床,實現(xiàn)時間最短、能耗最低、負載均衡等目標[12]。

而訂單加急擾動下的柔性車間動態(tài)重調(diào)度問題是指:按照預定調(diào)度方案生產(chǎn)過程中,忽然接到某一訂單加急生產(chǎn)的通知,而對車間內(nèi)剩余生產(chǎn)任務進行重新調(diào)度的問題。

1.2 動態(tài)重調(diào)度問題建模

為了建立規(guī)范實用的柔性車間動態(tài)重調(diào)度問題模型,筆者對該問題做出以下假設和規(guī)范:

(1)初始時刻,所有機床均處于健康可用狀態(tài);

(2)所有工件必須按照設定的工序順序加工;

(3)任一工序不能在多個機床上同時加工,但是必須加工一次;

(4)在任意時刻,同一機床無法同時加工多個工序;

(5)同一工件的下一工序開始時刻必須處于上一工序加工完成時刻之后;

(6)任一工序在可選機床上的加工概率是一致的。

為了建立柔性車間動態(tài)重調(diào)度模型,筆者設置一個標識參數(shù)xijk,并將其定義為:

(1)

基于上述假設和規(guī)范,根據(jù)訂單加急擾動柔性車間動態(tài)重調(diào)度問題特點,筆者在保證加急訂單優(yōu)先生產(chǎn)的前提下,以全部訂單的完工時間最短為優(yōu)化目標,進行動態(tài)重調(diào)度問題建模。

則訂單加急生產(chǎn)擾動下的車間重調(diào)度問題優(yōu)化模型為:

(2)

式中:T—最大完工時間;tSij—工序Oij的開始時間;tEij—工序Oij的結束時間;Pijk1—工序Oij在機器k1上的加工概率。

2 基于強制進化遺傳的靜態(tài)調(diào)度

當發(fā)生訂單加急生產(chǎn)擾動時,在預先設定生產(chǎn)方案的基礎上進行重調(diào)度,因此,筆者首先要進行靜態(tài)生產(chǎn)調(diào)度,而后考慮訂單加急生產(chǎn)擾動下的動態(tài)重調(diào)度。

2.1 染色體編碼與解碼

對于多工件、多工序、多柔性機床的生產(chǎn)調(diào)度問題,此處筆者使用雙基因鏈十進制編碼方式,其基因長度與總工序數(shù)量一致。一條基因鏈為工序基因鏈,規(guī)定了工序的加工順序;另一條基因鏈為機器基因鏈,規(guī)定了各工序加工對應的機器。

此處以3個工件共10道工序、4個生產(chǎn)機床為例,某染色體編碼如圖1所示。

圖1 雙基因鏈編碼

圖1所示的染色體的工序鏈中,數(shù)字3出現(xiàn)了4次,表明工件3具有4道加工工序,數(shù)字3第1次出現(xiàn)代表工序O31,第2次出現(xiàn)代表工序O32,依此類推。

工序鏈解碼得到工序的加工順序為:O31→O11→O21→O32→O22→O12→O13→O33→O23→O34;機器鏈解碼得到對應的生產(chǎn)機床為:M2→M4→M3→M1→M1→M3→M4→M2→M3→M1。

2.2 強制進化遺傳實現(xiàn)方法

強制進化遺傳操作的核心思想是:適應度強的染色體具有較多的優(yōu)秀基因片段,因此,適應度強的染色體應該大概率進行交叉,實現(xiàn)優(yōu)秀基因片段重組的目的;同時進行小概率、小范圍的基因變異,防止優(yōu)秀基因片段的破壞;相應的,適應度弱的染色體具有較少的優(yōu)秀基因片段[13]。

因此,適應度弱的染色體應該小概率進行交叉,同時進行大概率、大范圍的基因變異使染色體強制進化。

將交叉概率范圍設置為[pc1,pc2],變異概率范圍設置為[pm1,pm2]。某一染色體i的適應度值記為fi,則其交叉概率和變異概率分別為:

(3)

式中:pci—染色體i的交叉概率;pmi—染色體i的變異概率;fmax，fmin—適應度最大值和最小值。

前文中提到,交叉操作時,適應度強的染色體進行小范圍變異,適應度弱的染色體進行大范圍變異(所謂的“大小范圍”是指參與變異的基因片段長度)。

(4)

2.3 遺傳操作方式與自然選擇

為了滿足柔性機床加工的約束條件,遺傳操作前后工序鏈中每個工序必須出現(xiàn)且僅出現(xiàn)1次,筆者提出了改進POX交叉策略,該策略在交叉前后能夠滿足工序約束,無需進行人為檢查和驗證。改進POX交叉策略如圖2所示。

圖2 改進POX交叉策略

改進POX交叉策略具體方法為:

(1)將工件按照數(shù)量大致相等的原則分為兩組,圖2中工件2和3為一組,工件1和4為一組;

(2)父代1的工件1、4基因位不變,遺傳給子代2,父代2的工件2、3基因位不變,遺傳給子代1;

(3)父代1的工件1、4基因位左移一位,嵌入到子代1,父代2的工件2、3基因位左移一位,嵌入到子代2。

變異包括工序變異和機床變異,染色體按照隨機方式選擇變異方式。當進行工序變異時,按照式(4)確定變異基因長度,然后按照逆序方式進行變異;當進行機床變異時,以負載均衡為目的進行變異,實現(xiàn)方法為:統(tǒng)計機床鏈中出現(xiàn)頻次最多的機床,將頻次最多的機床變異為滿足該工序生產(chǎn)要求的另一機床。

工序變異和機床變異方式如圖3所示。

圖3 變異策略

圖3(a)中,父代選擇了基因2和基因3之間的片段,將其逆序變異后得到子代工序鏈;圖3(b)中,父代機床鏈機床2出現(xiàn)的頻次最多,隨機選擇一個機床2,將其變異為滿足生產(chǎn)要求的機床3。

自然選擇過程即為優(yōu)勝劣汰過程[14],遺傳操作后比較子代和父代的適應度值,保留其中適應度高的個體,維持物種的規(guī)模穩(wěn)定。

3 基于記憶優(yōu)先通道的動態(tài)重調(diào)度

接下來,筆者設計記憶優(yōu)先通道,解決訂單加急生產(chǎn)擾動下的柔性車間動態(tài)重調(diào)度問題。首先,對優(yōu)先通道的記憶功能進行說明;而后,對優(yōu)先通道的重調(diào)度原理進行設計;最后,給出車間重調(diào)度的流程圖。

3.1 記憶功能與記憶矩陣

在出現(xiàn)訂單緊急加工擾動時,擾動時刻Te之間的加工方案無法改變,擾動時刻Te之后的生產(chǎn)方案進行重新調(diào)度。因此,具有記憶功能的記憶矩陣是重調(diào)度方法必需的,記憶矩陣包括機器記憶矩陣M和時間記憶矩陣T兩個。

其中,機器記憶矩陣M用于記憶已完成工序使用的機床,以及未完成工序的可選機床集合,為:

(5)

式中:mij=[m1,…,mk]—滿足工序Oij生產(chǎn)要求的機床集合。

在訂單加急生產(chǎn)時刻Te之前,已完成工序只保留選擇的機床、淘汰未選機床,未完成工序保留可選機床集合。

同樣地,時間記憶矩陣用于記憶已完成工序的耗時,以及未完成工序的可能耗時,為:

(6)

式中:tij=[t1,…,tk]—可選機床集合mij中各機床的加工時間。

在訂單加急生產(chǎn)時刻Te之前,已完成工序只保留選擇機床對應的加工時間、淘汰未選機床的加工時間,未完成工序保留可選機床集合的加工時間集合。

3.2 優(yōu)先加工通道設置

優(yōu)先加工通道是為了應對訂單加急等擾動而設置的,當訂單加急生產(chǎn)時刻Te到來時,已進行而未完成的工序繼續(xù)生產(chǎn),未上機床生產(chǎn)線的工序進行重新調(diào)度。

由于訂單的緊急程度不同,在安排生產(chǎn)機床時的優(yōu)先程度也必然不同,筆者通過設置一個優(yōu)先系數(shù)e∈[0,1],使機床安排的優(yōu)先程度隨訂單緊急程度自適應變化。

優(yōu)先加工通道根據(jù)訂單生產(chǎn)的緊急程度,為其安排耗時相對較小的加工機床,具體方法為:

mij=rand[Mij((1-e)+1)·lij]

(7)

式中:mij—優(yōu)先通道為工序Oij安排的機床,rand()—隨機函數(shù);Mij—工序Oij的可使用機床按照加工時間升序排列得到的集合; —向上取整函數(shù);lij—工序Oij可使用機床的數(shù)量。

式(7)可解釋為:假設e=70%,那么從加工時間最短的前30%機床集合中隨機選擇一個機床,執(zhí)行工序Oij的加工任務。式(7)中,這種按照排序和隨機方式產(chǎn)生的機床,既保證了工序Oij的優(yōu)先生產(chǎn),也使用隨機方式提高了染色體多樣性,是一種兼顧優(yōu)先和多樣性的調(diào)度方式。

3.3 動態(tài)重調(diào)度流程

基于記憶優(yōu)先通道和強制進化遺傳算法的柔性車間動態(tài)重調(diào)度算法流程,如圖4所示。

圖4 柔性車間動態(tài)重調(diào)度流程

對柔性車間的動態(tài)重調(diào)度流程進行如下說明:

(1)車間在接到訂單加急生產(chǎn)通知之前,按照靜態(tài)調(diào)度方案進行生產(chǎn);

(2)車間接到訂單加急生產(chǎn)通知之后,使用記憶優(yōu)先通道對加急訂單進行調(diào)度,而后使用強制進化遺傳算法,將剩余生產(chǎn)任務插入到訂單加急調(diào)度方案中。

4 實驗與結果分析

筆者從兩個方面對柔性車間動態(tài)重調(diào)度方法進行實驗驗證:(1)驗證基于強制進化遺傳算法的靜態(tài)調(diào)度性能;(2)驗證基于記憶優(yōu)先通道的動態(tài)重調(diào)度性能。

4.1 車間靜態(tài)調(diào)度性能驗證

根據(jù)江蘇亨鑫科技有限公司某車間的生產(chǎn)需求,該車間共承擔6個工件的生產(chǎn)任務,每個工件具有6道生產(chǎn)工序,車間中具有10臺制造機床,各工序的可選機床及對應加工時間如表1所示。

表1 工件加工任務

為了進行比較,筆者分別使用標準遺傳算法、強制進化遺傳算法、文獻[15]改進遺傳算法對表1給出的案例進行調(diào)度。文獻[15]改進遺傳算法的參數(shù)按照原文設置,標準遺傳算法和強制進化遺傳算法的共同參數(shù)設置一致:染色體規(guī)模為100,算法最大迭代次數(shù)為200。另外,在標準遺傳算法中,交叉概率Pc=0.3,變異概率Pm=0.2;在強制進化遺傳算法中,交叉概率范圍[pc1,pc2]=[0.2,0.4],變異概率[pm1,pm2]=[0.1,0.3]。

筆者利用上述3種算法分別進行10次柔性車間靜態(tài)調(diào)度,統(tǒng)計10次最優(yōu)調(diào)度方案的最大生產(chǎn)時間、最小生產(chǎn)時間、平均生產(chǎn)時間,其結果如圖5所示。

圖5 任務完工時間統(tǒng)計

由圖5可知:針對表1給出的加工案例,上述3種算法規(guī)劃的10次調(diào)度方案中,強制進化遺傳算法靜態(tài)調(diào)度方案的平均加工時間為39.4 min,比改進遺傳算法減少了4.57%,比標準遺傳算法減少了6.85%;強制進化遺傳算法給定調(diào)度案例的最大完成時間、最小完成時間均小于標準遺傳算法和文獻[15]改進遺傳算法所用時間,說明強制進化遺傳算法具有最佳的靜態(tài)調(diào)度性能。這是因為:

(1)強制進化遺傳算法根據(jù)染色體適應度自適應調(diào)整個體的交叉概率,使優(yōu)秀個體的交叉概率較大,實現(xiàn)了優(yōu)秀基因片段重組;

(2)強制進化遺傳算法根據(jù)染色體適應度自適應調(diào)整個體的變異概率,使較差個體的變異概率和范圍較大,實現(xiàn)了較差染色體的強制進化;

(3)改進POX交叉策略在滿足工序約束條件下,使染色體變化較大,增強了算法的全局搜索能力。

強制進化遺傳算法規(guī)劃的最優(yōu)生產(chǎn)調(diào)度方案的甘特圖,如圖6所示。

圖6 任務調(diào)度的甘特圖

分析圖6可知:所有工件的工序加工均滿足時序要求,且均由滿足加工要求的機床完成。

4.2 車間動態(tài)重調(diào)度性能驗證

為了對動態(tài)重調(diào)度方法進行驗證,筆者將記憶優(yōu)先通道重調(diào)度方法與貪婪自適應方法[16]進行比較;并設計不同加急時刻、不同任務加急的情況進行比較。

筆者將加急時刻Te=10min，加急任務T1稱為任務1;加急時刻Te=20min，加急任務T1稱為任務2;加急時刻Te=20min，加急任務T3稱為任務3,重調(diào)度結果如表2所示。

表2 動態(tài)重調(diào)度任務完成時間/min

分析表2中數(shù)據(jù)可知:

(1)在3個訂單加急生產(chǎn)任務中,實現(xiàn)了訂單加急生產(chǎn)。以任務1為例,記憶優(yōu)先通道重調(diào)度方法的加急調(diào)度方案使任務1的生產(chǎn)時間減少了2 min,貪婪自適應方法的加急調(diào)度方案使任務1的生產(chǎn)時間減少了1 min;

(2)在訂單加急生產(chǎn)的條件下,相比于預先的靜態(tài)方案,記憶優(yōu)先通道重調(diào)度方法和貪婪自適應方法在所有任務耗時上均有一定提高,但是記憶優(yōu)先通道重調(diào)度方法的增加時間少于貪婪自適應方法調(diào)度方案增加的時間。以任務1為例,記憶優(yōu)先通道重調(diào)度方法的加急調(diào)度方案在整體生產(chǎn)時間上增加了5.0 min,貪婪自適應方法加急調(diào)度方案在整體生產(chǎn)時間上增加了8.0 min;

(3)記憶優(yōu)先通道重調(diào)度方案在任務1、任務2、任務3的整體完工時間分別為42.0 min、43.0 min、42.5 min,比貪婪自適應方法分別減少了3.0 min、2.0 min、3.5 min,說明記憶優(yōu)先通道重調(diào)度方案在加急工況下的重調(diào)度性能好于貪婪自適應方法;

(4)在不同加急時刻、不同工件加急的工況下,記憶優(yōu)先加工通道的加急訂單生產(chǎn)時間、整體加工時間均小于貪婪自適應方法;

(5)對于同一任務,在不同時刻進行加急,任務的可加急空間是不同的;對于同一時刻,不同任務的加急空間也是不同的。

綜合上述實驗數(shù)據(jù)可以得出結論:

在上述3種任務加急生產(chǎn)擾動中,記憶優(yōu)先通道重調(diào)度方案的整體生產(chǎn)耗時少于貪婪自適應方法重調(diào)度方案,同時記憶優(yōu)先通道重調(diào)度方案的加急訂單生產(chǎn)耗時少于貪婪自適應方法。這是因為當發(fā)生訂單加急擾動時,加急生產(chǎn)通道能夠根據(jù)生產(chǎn)任務的緊急程度自適應為其分配合適的生產(chǎn)機床,在滿足加急生產(chǎn)的同時保證了任務整體的加工效率[17-19]。

以加急時刻為Te=20 min,加急任務為T3為例,對2種方法動態(tài)重調(diào)度方案進行展示,結果如圖7所示。

圖7 動態(tài)重調(diào)度的甘特圖

分析圖7可知:所有工件的工序加工均滿足時序要求,且均由滿足加工要求的機床完成,滿足設定的約束條件。

5 結束語

為了解決訂單加急生產(chǎn)擾動下的柔性車間動態(tài)重調(diào)度問題,以縮短整體加工時間為目標,筆者提出了一種基于強制進化遺傳算法和記憶優(yōu)先加工通道的動態(tài)重調(diào)度方法。

筆者首先根據(jù)預先設定的生產(chǎn)需求,提出了基于強制進化遺傳算法的靜態(tài)調(diào)度方法;然后,當發(fā)生訂單加急生產(chǎn)擾動時,設計了具有記憶功能的優(yōu)先生產(chǎn)通道,該生產(chǎn)通道能夠根據(jù)訂單緊急程度,自適應地調(diào)整相應生產(chǎn)機床;最后,在生產(chǎn)車間中,對該研究的重調(diào)度方法進行了驗證。

經(jīng)6工件生產(chǎn)的實驗驗證,得出以下結論:

(1)在柔性車間靜態(tài)調(diào)度中,強制進化遺傳算法靜態(tài)調(diào)度方案的平均加工時間為39.4 min,比改進遺傳算法減少了4.57%,比標準遺傳算法減少了6.85%,說明強制進化遺傳算法具有最佳的靜態(tài)調(diào)度性能;

(2)在柔性車間動態(tài)調(diào)度中,記憶優(yōu)先通道重調(diào)度方案在任務1、任務2、任務3的整體完工時間分別為42.0 min、43.0 min、42.5 min,比貪婪自適應方法分別減少了3.0 min、2.0 min、3.5 min,說明記憶優(yōu)先通道重調(diào)度方案在加急工況下的重調(diào)度性能好于貪婪自適應方法。

在對訂單加急生產(chǎn)情況下的柔性車間重調(diào)度問題進行研究時,筆者未考慮訂單插入、機械故障、加工時間模糊等特殊情況。因此,在后續(xù)的研究中,筆者將針對這些特殊情況展開相關的研究。