考慮訂單加急生產的柔性車間作業動態調度*

朱旭東

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

0 引 言

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

合理的柔性車間調度方案可以有效提升車間的生產效率,體現企業的核心競爭力[2]。因此,研究柔性車間的生產調度問題具有重要的經濟意義和實用價值。

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

根據優化目標分類,柔性車間動態調度問題可以分為完工時間優化、能耗優化和負載均衡優化等[4]。根據優化目標數量分類,柔性車間動態調度問題可以分為單目標調度問題和多目標調度問題[5]。從動態調度算法的角度出發,柔性車間動態調度問題又可以分為精確求解算法和啟發類求解算法。

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

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

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

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

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

1 問題描述與建模

1.1 訂單加急的動態重調度問題描述

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

此處,筆者研究的是訂單加急擾動下的柔性車間動態重調度問題。

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

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

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

1.2 動態重調度問題建模

為了建立規范實用的柔性車間動態重調度問題模型,筆者對該問題做出以下假設和規范:

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

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

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

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

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

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

為了建立柔性車間動態重調度模型,筆者設置一個標識參數xijk,并將其定義為:

(1)

基于上述假設和規范,根據訂單加急擾動柔性車間動態重調度問題特點,筆者在保證加急訂單優先生產的前提下,以全部訂單的完工時間最短為優化目標,進行動態重調度問題建模。

則訂單加急生產擾動下的車間重調度問題優化模型為:

(2)

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

2 基于強制進化遺傳的靜態調度

當發生訂單加急生產擾動時,在預先設定生產方案的基礎上進行重調度,因此,筆者首先要進行靜態生產調度,而后考慮訂單加急生產擾動下的動態重調度。

2.1 染色體編碼與解碼

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

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

圖1 雙基因鏈編碼

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

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

2.2 強制進化遺傳實現方法

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

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

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

(3)

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

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

(4)

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

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

圖2 改進POX交叉策略

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

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

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

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

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

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

圖3 變異策略

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

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

3 基于記憶優先通道的動態重調度

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

3.1 記憶功能與記憶矩陣

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

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

(5)

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

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

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

(6)

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

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

3.2 優先加工通道設置

優先加工通道是為了應對訂單加急等擾動而設置的,當訂單加急生產時刻Te到來時,已進行而未完成的工序繼續生產,未上機床生產線的工序進行重新調度。

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

優先加工通道根據訂單生產的緊急程度,為其安排耗時相對較小的加工機床,具體方法為:

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

(7)

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

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

3.3 動態重調度流程

基于記憶優先通道和強制進化遺傳算法的柔性車間動態重調度算法流程,如圖4所示。

圖4 柔性車間動態重調度流程

對柔性車間的動態重調度流程進行如下說明:

(1)車間在接到訂單加急生產通知之前,按照靜態調度方案進行生產;

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

4 實驗與結果分析

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

4.1 車間靜態調度性能驗證

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

表1 工件加工任務

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

筆者利用上述3種算法分別進行10次柔性車間靜態調度,統計10次最優調度方案的最大生產時間、最小生產時間、平均生產時間,其結果如圖5所示。

圖5 任務完工時間統計

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

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

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

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

強制進化遺傳算法規劃的最優生產調度方案的甘特圖,如圖6所示。

圖6 任務調度的甘特圖

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

4.2 車間動態重調度性能驗證

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

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

表2 動態重調度任務完成時間/min

分析表2中數據可知:

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

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

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

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

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

綜合上述實驗數據可以得出結論:

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

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

圖7 動態重調度的甘特圖

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

5 結束語

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

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

經6工件生產的實驗驗證,得出以下結論:

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

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

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