基于滾動窗口技術(shù)和遺傳算法的柔性作業(yè)車間動態(tài)調(diào)度研究*

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

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

0 引 言

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

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

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

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

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

1 FJSP問題的求解流程

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

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

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

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

(4)所有工件加工完成,調(diào)度結(jié)束。

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

圖1 FJSP問題求解流程圖

2 基于滾動窗口技術(shù)的FJSP

滾動技術(shù)適用于復雜多變的動態(tài)環(huán)境,重調(diào)度適用于突發(fā)干擾事件。筆者將二者結(jié)合起來以解決FJSP問題。

2.1 參數(shù)修正

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

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

2.2 工件數(shù)量和調(diào)度周期的確定

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

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

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

Ts=TP/f

(1)

式中:Ts—兩次調(diào)度之間的時間間隔;TP—所有機床的加工時間之和;f—調(diào)度次數(shù)。

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

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

3.1 染色體編碼

采用遺傳算法可以求解FJSP問題,得到其最優(yōu)解。染色體編碼是遺傳算法中的關(guān)鍵環(huán)節(jié),它的主要任務(wù)是將解空間中的解用染色體的形式表達出來,方便以后遺傳算子的操作。

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

該編碼方式如圖2所示。

圖2 分段編碼圖

3.1.1 機器選擇部分

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

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

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

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

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

3.1.2 工序選擇部分

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

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

通過對上述機器選擇部分和工序排序部分的分步驟解釋可以看出,機器選擇編碼區(qū)的每一位基因都與相應(yīng)的一道工序?qū)?yīng);即使機器編碼區(qū)的基因進行交叉操作,編碼區(qū)的每一位基因在可執(zhí)行該工序的機床集合內(nèi)選擇,即可避免非法染色體的出現(xiàn)。

3.2 染色體解碼

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

解碼步驟如下:

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

(2)對工序排序部分的解碼。通過將步驟(1)獲得的所有工件及工序的相關(guān)數(shù)據(jù)應(yīng)用于工序排序部分的染色體,便可獲得相應(yīng)的調(diào)度方案。

3.3 種群初始化

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

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

3.4 選擇操作

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

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

圖4 錦標賽選擇法原理圖

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

3.5 交叉操作

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

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

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

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

圖5 均勻交叉法原理圖

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

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

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

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

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

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

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

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

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

圖6 POX交叉法原理圖

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

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

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

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

3.6 變異操作

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

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

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

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

領(lǐng)域搜索變異原理圖如圖8所示。

圖8 領(lǐng)域搜索變異原理圖

3.7 終止條件

終止條件要設(shè)定迭代的次數(shù),當?shù)螖?shù)大于或等于設(shè)定的迭代次數(shù),則終止操作;否則,繼續(xù)重復上述的迭代操作。

迭代的次數(shù)要根據(jù)生產(chǎn)過程中的實際情況來確定。

4 案例驗證

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

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

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

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

實例數(shù)據(jù)如表1所示。

表1 實例數(shù)據(jù)表

續(xù)表

4.1 作業(yè)車間正常運行

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

實驗結(jié)果可見甘特圖如圖9所示。

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

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

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

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

在圖10中可以看到:經(jīng)過遺傳算子操作的解在收斂,在接近第500次迭代時出現(xiàn)最優(yōu)解,即最大完工時間最小的數(shù)值為17。

4.2 機器出現(xiàn)故障

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

圖9 作業(yè)車間正常運行時的甘特圖

圖10 作業(yè)車間正常運行時收斂曲線圖

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

圖11中,結(jié)果顯示最大完工時間值為20。通過對機器故障的處理可以證明,滾動窗口技術(shù)和遺傳算法相結(jié)合的方法可以有效應(yīng)對作業(yè)車間出現(xiàn)的突發(fā)事件。

機器出現(xiàn)故障時收斂曲線圖如圖12所示。

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

圖11 機器出現(xiàn)故障時的甘特圖

圖12 機器出現(xiàn)故障時收斂曲線圖

5 結(jié)束語

針對FMS系統(tǒng)中存在多種動態(tài)事件,導致生產(chǎn)線生產(chǎn)效率下降的問題,筆者采用滾動窗口技術(shù)與遺傳算法相結(jié)合的方式求解單目標FJSP。

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

(1)周期性重調(diào)度和事件驅(qū)動重調(diào)度結(jié)合形成的混合重調(diào)度方式可以有效應(yīng)對作業(yè)車間動態(tài)事件的發(fā)生;

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

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

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

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