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

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

0 引 言

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

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

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

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

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

1 FJSP問題的求解流程

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

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

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

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

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

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

圖1 FJSP問題求解流程圖

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

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

2.1 參數(shù)修正

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

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

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

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

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

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

Ts=TP/f

(1)

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

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

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

3.1 染色體編碼

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

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

該編碼方式如圖2所示。

圖2 分段編碼圖

3.1.1 機(jī)器選擇部分

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

機(jī)器選擇和工序排序如圖3所示。

圖3 機(jī)器選擇和工序排序圖

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

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

3.1.2 工序選擇部分

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

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

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

3.2 染色體解碼

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

解碼步驟如下:

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

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

3.3 種群初始化

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

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

3.4 選擇操作

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

錦標(biāo)賽選擇法的原理如圖4所示。

圖4 錦標(biāo)賽選擇法原理圖

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

3.5 交叉操作

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

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

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

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

圖5 均勻交叉法原理圖

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

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

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

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

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

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

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

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

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

圖6 POX交叉法原理圖

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

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

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

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

3.6 變異操作

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

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

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

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

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

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

3.7 終止條件

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

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

4 案例驗(yàn)證

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

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

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

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

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

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

續(xù)表

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

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

實(shí)驗(yàn)結(jié)果可見甘特圖如圖9所示。

圖9中,橫坐標(biāo)表示加工時間,縱坐標(biāo)表示機(jī)器編號。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

筆者對FJSP進(jìn)行了深入分析,并列出了求解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ù)進(jìn)行準(zhǔn)確修正,有利于獲得良好的重調(diào)度方案;

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

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

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