基于滾動窗口技術和遺傳算法的柔性作業車間動態調度研究*

斯興瑤,廖映華,任少波,胥 云

(四川輕化工大學 機械工程學院,四川 宜賓 644000)

0 引 言

柔性制造技術是隨著產業智能化的迅速發展而出現的,而作業車間的調度問題是一個生產過程中必須面臨的核心問題。柔性作業車間調度問題(FJSP)是由傳統作業車間調度問題延伸出來的,該問題具有復雜性、約束性、目標性,以及離散的特點[1]。FJSP是柔性生產線的核心問題[2]。

張國輝等人[3,4]在分析了柔性作業車間特點的基礎上,對滾動窗口技術、重調度策略和遺傳算法進行了深入的研究。彭博等人[5,6]經過研究指出,作業車間的調度問題是一個生產過程中必須面臨的核心問題,也是典型的組合和優化問題。衛少鵬等人[7]基于頭腦風暴算法和多層編碼技術,對機床調整模式和加工模式的耗費事件進行了研究。GONG G L等人[8-10]在研究柔性作業車間問題時,提出了一種混合人工蜂群算法,并設計了交叉和變異算子。

雖然很多學者都對車間的調度問題進行了研究,但是目前仍沒有一種系統的應對方案,既可以妥善處理動態的事件,又能夠保證作業車間有較高的生產效率和設備利用率[11，12]。

事實上,在實際的加工過程中,FJSP會出現多種多樣的動態事件,如某臺機器出現故障、緊急任務插單等。在以往的研究過程中,往往會因為對動態因素評估不足或模型建立不當,從而導致該問題無法得到徹底解決。

筆者針對柔性作業車間出現的生產效率和設備利用率低的問題,提出一種滾動窗口技術與遺傳算法相結合的方法,以達到處理動態事件的目的,使企業既能滿足用戶多品種、中小批量的要求,又能有效降低生產成本。

1 FJSP問題的求解流程

FJSP問題的具體求解流程如下:

(1)在整個作業車間開始調度時,假設所有機器均處于空閑狀態,只需從待加工工件集中選出一部分進入工件窗口;

(2)對放入窗口的工件進行編碼、初始化以及遺傳算子操作,在達到終止條件時,會產生新的調度方案;如果沒有達到終止條件,繼續進行遺傳算子操作和適應度函數計算,直到達到終止條件;

(3)如果該調度方案運行一個周期后,會將加工完的工件移出加工窗口,從待加工工件集中選出一部分工件添加到加工窗口,對加工窗口進行重調度;如果在調度方案執行過程中,出現干擾因素,即動態事件,則會根據動態事件的情況對加工窗口進行重調度;如果出現機器故障,則會屏蔽該機器編號,將工件安排在其他機器上進行加工;如果有緊急訂單需要加工,則會根據緊急工件的多少,對工件窗口進行重調度;

(4)所有工件加工完成,調度結束。

FJSP問題求解流程圖如圖1所示。

圖1 FJSP問題求解流程圖

2 基于滾動窗口技術的FJSP

滾動技術適用于復雜多變的動態環境,重調度適用于突發干擾事件。筆者將二者結合起來以解決FJSP問題。

2.1 參數修正

由文獻[13,14]可知,從初始時刻開始,經過一個加工周期后,滾動窗口的工件窗口會移除完工工件,添加新的工件。工件窗口的工件分為加工工件、待加工工件和新添加工件,需要對這些工件進行重調度。

由于機器狀態不同,工件狀態復雜,需要修正相關的信息,包括:機器可利用時間、加工機器順序矩陣和加工時間矩陣。

2.2 工件數量和調度周期的確定

在工件窗口中,工件數量和重調度周期的設定是影響作業車間調度效率的兩個重要因素[15,16]。

工件窗口中,工件數量的選擇對作業車間調度效率的影響較大,如果工件窗口中選取的工件數量太少,則滾動窗口技術的效果就不明顯,而且也會使機器設備利用率降低:反之,則無法對動態事件做出有效響應,同時降低了作業車間的生產效率;

重調度周期是指連續的兩次調度之間的時間長度。重調度周期的設定是固定的,這種設定重調度周期的方式無法有效地反映作業車間的負荷情況。為了解決這個問題,筆者采用重調度次數與生產車間的負荷成正比的方式,即:

Ts=TP/f

(1)

式中:Ts—兩次調度之間的時間間隔;TP—所有機床的加工時間之和;f—調度次數。

3 基于遺傳算法的FJSP問題求解

用遺傳算法求解柔性作業車間調度問題包括7個環節:染色體編碼、染色體解碼、種群初始化、選擇操作、交叉操作、變異操作和終止條件。

3.1 染色體編碼

采用遺傳算法可以求解FJSP問題,得到其最優解。染色體編碼是遺傳算法中的關鍵環節,它的主要任務是將解空間中的解用染色體的形式表達出來,方便以后遺傳算子的操作。

但是,不同的編碼方式所產生的染色體對后續遺傳算子的操作有較大的影響,甚至產生無解。一般編碼方式有兩種,即集成編碼和分段編碼。由于分段編碼的方式容易進行遺傳算子操作,此處筆者選擇分段編碼,并采用一種整數編碼方式MSOS。

該編碼方式如圖2所示。

圖2 分段編碼圖

3.1.1 機器選擇部分

在機器選擇(machine selection,MS)部分,其染色體長度是所有工件工序數量的總和,而且每個基因位都是整數。在對MS部分進行編碼時,首先需要對所有工件進行排序,其次將其各個工序展開,并與MS部分的染色體逐個對應。

機器選擇和工序排序如圖3所示。

圖3 機器選擇和工序排序圖

圖3中,工件J1和工件J2的所有工序與MS部分染色體逐個對應;之后,對各個工序逐個進行編碼,每個染色體基因位上的數值為該工序可選機器集中的順序編號(圖3中第2個基因位為1,即表示選擇2個機器中的第1個機器加工該工序O12)。

此處以圖3中的工件J1和工件J2為例進行解釋:對工件J1和工件J2的所有工序進行了排序,假設工序O11有5臺機器可以選擇,而在染色體中,工序O11對應的整數是4,即表示工序O12選擇了第4臺機器進行加工。

3.1.2 工序選擇部分

確定所有工件各個工序的加工機器后,要對工序排序(OS)進行編碼。工序排序部分的染色體長度為工件工序數量之和。在對工序排序部分進行編碼時,采用每個工件的工件號進行編碼,工件號在工序排序部分,染色體出現的先后順序就是該工件加工的先后順序。

圖3中,工序排序部分染色體的編碼為(2 2 1 1 2);其中,第1個數字2表示工件J2的第1道工序O21,第2個數字2表示工件J2的第2道工序O22……,依次類推,即可獲得各工件工序的加工順序。

通過對上述機器選擇部分和工序排序部分的分步驟解釋可以看出,機器選擇編碼區的每一位基因都與相應的一道工序對應;即使機器編碼區的基因進行交叉操作,編碼區的每一位基因在可執行該工序的機床集合內選擇,即可避免非法染色體的出現。

3.2 染色體解碼

由于FJSP問題的染色體解碼是對機器選擇和工序排序兩部分的解碼,需要考慮如何對這兩部分分別進行解碼。

解碼步驟如下:

(1)對機器選擇部分的解碼。主要是從機器選擇部分的染色體中讀出所有工件的所有工序在哪臺機器上進行加工,以及在該機器上加工的時間是多少。通常情況下,以機器順序矩陣和加工時間順序矩陣的方式展現;

(2)對工序排序部分的解碼。通過將步驟(1)獲得的所有工件及工序的相關數據應用于工序排序部分的染色體,便可獲得相應的調度方案。

3.3 種群初始化

種群的初始化是遺傳算法中一個關鍵操作。初始化所得的解的質量會嚴重影響遺傳算法的求解速度和求解質量。而FJSP問題的本質就是選擇合適的機器對應到相應的工件工序上,使作業車間的加工過程滿足評價指標的要求。

如何進行初始化非常重要。針對FJSP問題的特點,筆者提出了GLR機器選擇法,包括全局選擇、局部選擇和隨機選擇方式。

3.4 選擇操作

選擇操作是要從所有種群中選擇出高質量的個體,使其優良的性能遺傳給子代,讓高質量的個體以更高的概率存活下來,從而提高整個種群的質量。筆者采用錦標賽選擇法,從父代種群中選出優良的個體。

錦標賽選擇法的原理如圖4所示。

圖4 錦標賽選擇法原理圖

圖4中,每次從所有的父代種群中選出一個性能優良的個體,并對這些個體進行適應度的比較,從這個性能優良的個體中選出適應度更高的個體插入交叉池中,不斷重復上面的操作,直到交叉池填滿為止。

3.5 交叉操作

交叉操作是將父代個體經過某種方式組合后產生新的個體。進行該操作時,需要滿足一個要求,即交叉之后的子代是可行的。筆者對機器選擇部分和工序排序部分采用的交叉方法分別進行討論。

3.5.1 機器選擇部分(均勻交叉法)

機器選擇部分必須保證每位基因的先后順序不改變,所以要采用均勻交叉法。

均勻交叉法原理圖如圖5所示

圖5 均勻交叉法原理圖

交叉操作的具體步驟如下:

(1)在機器選擇部分的染色體中,隨機選擇一個整數2,大小不超過機器選擇部分染色體的長度;

(2)在染色體中隨機選擇1和2的基因;

(3)在父代染色體中找到1和2的基因位置,將該位置的基因復制到子代染色體中,并保持其在原先父代染色體中的位置和順序;

(4)將父代染色體其余位置的基因互換,并分別復制到子代染色體中,產生新的子代染色體C1和C2。

上述均勻交叉的方法保證了機器選擇部分染色體的可行性,滿足了遺傳算法的要求。

3.5.2 工序排序部分(POX交叉法)

POX交叉法即是基于工件優先順序的交叉。在進行POX交叉的過程中,需要將父代染色體中被選中工件的所有工序所對應的基因位置和加工順序保留給子代,將父代染色體的其他基因位置互換,并按照其原本的順序添加到子代的染色體中。

POX交叉法原理圖如圖6所示。

圖6 POX交叉法原理圖

交叉操作的具體步驟如下:

(1)從整體的工件集中選出工件J1和工件J2組成的子集;

(2)將父代染色體中含有子工件集J1、J2的所有工序復制到子染色體C1、C2中,并保持它們原先在父代染色體中的位置和順序不變;

(3)將父代染色體中的其他基因互換,按順序逐個復制到子代染色體中。

3.6 變異操作

變異操作是為了增加種群的多樣性,每個子代根據一定的概率進行變異。變異操作一般采用:互換變異、插入變異和基于鄰域搜索變異等方法。

(1)機器選擇部分的染色體采用的變異方法如圖7所示。

圖7 機器選擇部分的染色體變異原理圖

(2)工序排序的部分,采用基于領域搜索變異的方法。

領域搜索變異原理圖如圖8所示。

圖8 領域搜索變異原理圖

3.7 終止條件

終止條件要設定迭代的次數,當迭代次數大于或等于設定的迭代次數,則終止操作;否則,繼續重復上述的迭代操作。

迭代的次數要根據生產過程中的實際情況來確定。

4 案例驗證

該實驗要求8個工件在8臺機器上進行加工,而且每個工件的每道工序至少有1臺機器可供選擇。案例中,迭代次數設定為500,種群規模為100,交叉概率pc為0.8,變異概率pm為0.2。

在調度過程中,計算參與調度的所有工件的每道工序在相應加工機器上開始加工的時間。實踐證明,加工某道工序的開始加工時間分為兩種情況:(1)后一道工序開始加工時間是前一道工序的完成時間;(2)前后兩道工序不在同一機器的完成時間。

從待加工的工件集中選出的一定數量的工件,如果將其添加進工件窗口的時間和重調度的時間不相同,那么對于這類工件的第一道工序的開始加工時間也有兩種情況:(1)這類工件添加進工件窗口的時間,正好安排這類工件去空閑機器上加工;(2)這類工件中的某個工件的第一道工序所選機器加工完成其前道工序的時間。而待加工工件的開始加工時間就是這兩種情況中的最大值t。根據加工時間、工件數量和調度周期解決調度問題。

通過這些數據可以驗證單目標FJSP問題求解方法的正確性。同時,該案例對機器出現故障的情況進行驗證,可以測試采用滾動窗口技術與遺傳算法相結合的方法應對柔性作業車間突發事件時的性能。

實例數據如表1所示。

表1 實例數據表

續表

4.1 作業車間正常運行

在作業車間正常運行時,通過滾動窗口技術與遺傳算法相結合的方法求得最短完工時間為17。

實驗結果可見甘特圖如圖9所示。

圖9中,橫坐標表示加工時間,縱坐標表示機器編號。

由圖9可以看到:各個機器所加工的工件,機器M8對應的(6-2)表示6號工件的第2道工序;方格的長短表示機器在該機器上的加工時間長短。

甘特圖的運行結果表明,采用滾動窗口技術和遺傳算法相結合的方法可以有效解決單目標FJSP。

在進行遺傳算子操作的過程中,可得最優解和解的平均值收斂曲線,如圖10所示。

在圖10中可以看到:經過遺傳算子操作的解在收斂,在接近第500次迭代時出現最優解,即最大完工時間最小的數值為17。

4.2 機器出現故障

在運行過程中,假設機器出現故障,需要在可選機器集中將機器1的編號從機器集中移出,再進行重調度。機器出現故障時的甘特圖如圖11所示。

圖9 作業車間正常運行時的甘特圖

圖10 作業車間正常運行時收斂曲線圖

圖11中的甘特圖表示機器1故障時,對工件窗口中工件進行的重調度。

圖11中,結果顯示最大完工時間值為20。通過對機器故障的處理可以證明,滾動窗口技術和遺傳算法相結合的方法可以有效應對作業車間出現的突發事件。

機器出現故障時收斂曲線圖如圖12所示。

圖12為機器1出現故障時,解空間中最優解和所有解的平均值的收斂曲線;通過觀察各種解的變化情況可以看出:解空間中的解呈現收斂趨勢,在20處達到最值,即最大完工時間最小值為20。

圖11 機器出現故障時的甘特圖

圖12 機器出現故障時收斂曲線圖

5 結束語

針對FMS系統中存在多種動態事件,導致生產線生產效率下降的問題,筆者采用滾動窗口技術與遺傳算法相結合的方式求解單目標FJSP。

筆者對FJSP進行了深入分析,并列出了求解FJSP的流程,介紹了在求解過程中遺傳算法的編碼、初始化及遺傳算子的各種操作方法,可以在有效處理突發事件的前提下,提高作業車間的生產效率。研究結果表明:

(1)周期性重調度和事件驅動重調度結合形成的混合重調度方式可以有效應對作業車間動態事件的發生;

(2)每次重調度時,對滾動窗口中各個參數進行準確修正,有利于獲得良好的重調度方案;

(3)根據作業車間負荷的大小,合理選擇重調度的周期,有利于反映作業車間各個階段負荷的情況;

(4)采用分段編碼的方式對機器選擇部分和工序排序部分進行編碼,既能保證最終求得解決方案,又能有效降低計算量。

在今后的研究工作中,筆者將進一步研究多目標的車間調度策略,以便更好地解決柔性車間的動態調度問題。