基于petri網(wǎng)仿真的雙資源jsp動(dòng)態(tài)優(yōu)化調(diào)度

1、基于Petri網(wǎng)仿真的雙資源JSP動(dòng)態(tài)優(yōu)化調(diào)度摘要:以帶有控制器的 Petri 網(wǎng)為建模工具對(duì)柔性生產(chǎn)調(diào)度中的離散事件建模,通過構(gòu)建Petri 網(wǎng)控制器使系統(tǒng)的運(yùn)行滿足期望的目標(biāo),同時(shí)利用混合遺傳算法獲得調(diào)度結(jié)果,用于解決作業(yè)車間的加工受到機(jī)床、操作工人等資源制約條件下的動(dòng)態(tài)優(yōu)化調(diào)度.為了保證生產(chǎn)的平穩(wěn)性,最大限度地維持車間的生產(chǎn)能力,提出了針對(duì)不同的擾動(dòng)進(jìn)行分類處理的新方法,首先基于機(jī)床故障修復(fù)時(shí)間、工人離崗時(shí)間及取消訂單包含任務(wù)的多少進(jìn)行分類調(diào)度,然后根據(jù)機(jī)床故障修復(fù)后以及工人回崗后剩余任務(wù)的多少?zèng)Q定是否進(jìn)行再一次的調(diào)度,最后對(duì)算法進(jìn)行了仿真研究.關(guān)鍵詞:Petri網(wǎng);控制器;遺傳算法;模

2、擬退火算法;動(dòng)態(tài)車間調(diào)度Abstract: A Petri net with controller is used to model discrete events in flexible job shop scheduling, and making the system running satisfy the anticipant aim through constructing the Petri net controller, and the scheduling results is obtained based on hybrid algorithm of genetic algo

3、rithm and simulated annealing algorithm. The method is developed to address the dynamic scheduling problem in manufacturing systems constrained by machines, workers. In order to assure the stability of manufacture, and the job shop production ability can be maintained farthest, different uncertain d

4、isturbances are classified to dispose with a new method. Firstly, classified based on machine repairing time, and worker leaving time, and task of order canceling; and then deciding whether it is arranged again based on remainder task after machine repairing and worker returning; and lastly, simulat

5、ion based dynamic job shop scheduling is developed. Key words: Petri net; controller; genetic algorithm; simulated annealing algorithm; dynamic job shop scheduling前言具有柔性加工路徑的Job shop型調(diào)度問題(JSP)是一個(gè)具有 NP 難計(jì)算復(fù)雜性的開放問題.雖然針對(duì)調(diào)度問題已經(jīng)提出了很多方法,例如排隊(duì)論模型、數(shù)學(xué)規(guī)劃、系統(tǒng)仿真、控制理論等,但是這些方法描述問題的能力很有限,所以尋找更加有效的方法是很有必要的.近年來,Petri網(wǎng)

6、作為離散事件動(dòng)態(tài)系統(tǒng)的建模和分析工具,已被成功地應(yīng)用于柔性生產(chǎn)系統(tǒng)的建模/分析和控制 1-6,但都只是對(duì)生產(chǎn)線本身建模,不能反映作為生產(chǎn)線中外部控制的調(diào)度策略的影響. 本文應(yīng)用具有庫所和變遷混合約束的Petri網(wǎng)控制器設(shè)計(jì)方法7進(jìn)行控制器的設(shè)計(jì),并對(duì)Petri網(wǎng)進(jìn)行建模.在此Petri網(wǎng)模型基礎(chǔ)之上充分地利用了混合的遺傳算法和模擬退火算法8(GASA),通過對(duì)該P(yáng)etri網(wǎng)模型的仿真運(yùn)行可以獲得調(diào)度策略的性能.為了更好地解決動(dòng)態(tài)調(diào)度問題,提出了對(duì)雙資源動(dòng)態(tài)優(yōu)化調(diào)度進(jìn)行分類處理的新方法,針對(duì)不同的擾動(dòng)通過選取合理有效的調(diào)度策略,最大限度地維持車間的生產(chǎn)能力,通過具體實(shí)例驗(yàn)證了所提方法的問題求解能

7、力,表明所提出方法的有效性.柔性生產(chǎn)調(diào)度的Petri網(wǎng)模型普通Petri網(wǎng)模型僅能夠反映生產(chǎn)線的加工路徑及其資源約束,而本文通過構(gòu)建Petri網(wǎng)控制器可以對(duì)設(shè)備優(yōu)先級(jí)、操作優(yōu)先級(jí)等進(jìn)行描述.添加控制器的目的就是使系統(tǒng)的運(yùn)行滿足期望的目標(biāo),從控制的觀點(diǎn)來看,控制器是通過使能或禁止它的輸出變遷來實(shí)現(xiàn)它的控制目標(biāo)的,并從它的輸入變遷的激發(fā)獲得反饋,所以該控制器設(shè)計(jì)方法只需要考慮直接或間接的與約束有關(guān)的變遷,同時(shí)利用局部設(shè)計(jì)和Petri網(wǎng)簡(jiǎn)化技術(shù)實(shí)現(xiàn)控制器的設(shè)計(jì),因而比Yang9提出的 Petri 網(wǎng)控制器設(shè)計(jì)方法更加簡(jiǎn)單、有效并且不會(huì)導(dǎo)致死鎖.為了直觀的說明柔性生產(chǎn)調(diào)度的Petri網(wǎng)模型,建立一子模

8、型.考慮如下的一個(gè)FMS系統(tǒng),系統(tǒng)中有3種類型6臺(tái)機(jī)床,1、2號(hào)機(jī)床為類型;3號(hào)機(jī)床為類型;4、5、6號(hào)機(jī)床為類型.共有10個(gè)工件需要加工,每個(gè)工件有14個(gè)工序,工人工作表、任務(wù)參數(shù)表如表1和表2.工件 工序 加工時(shí)間 機(jī)床類型 工件 工序 加工時(shí)間 機(jī)床類型1 1 12 5 2 10 2 9 3 10 3 5 4 8 2 1 6 6 1 6 2 6 7 1 6 3 8 2 8 3 1 5 8 1 12 2 9 2 8 4 1 4 3 8 2 6 9 1 5 3 10 2 8 5 1 5 10 1 7 工人 機(jī)床1 機(jī)床2 機(jī)床3 機(jī)床4 機(jī)床5 機(jī)床61 操作 操作 2 操作 操作 3 操作

9、 操作4 操作 操作建立工件1的Petri模型如圖1所示,其中各符號(hào)的意義:表示第i個(gè)工件的初始狀態(tài);表示第i臺(tái)機(jī)床;表示第i個(gè)工件的第j個(gè)操作由第h個(gè)工人在第k臺(tái)機(jī)床上進(jìn)行;表示操作開始;表示操作結(jié)束;表示工件i的第j個(gè)操作結(jié)束后的緩沖區(qū);表示第i個(gè)工件加工完成.虛線部分表示控制器部分(具體設(shè)計(jì)步驟見參考文獻(xiàn)7),它主要對(duì)以下兩種行為進(jìn)行控制:第一個(gè)緩沖區(qū)不能上溢也不能下溢,當(dāng)緩沖區(qū)內(nèi)有工件時(shí)機(jī)床3不能啟動(dòng)操作,即;機(jī)床3有比機(jī)床1修復(fù)和回到正常工作(忙狀態(tài))的優(yōu)先級(jí):在兩臺(tái)機(jī)床同時(shí)壞掉的時(shí)候,機(jī)床3應(yīng)優(yōu)先被修復(fù).按照此方法可以依次建立其余工件的Petri網(wǎng)模型,最后將這些模型通過表示機(jī)床、

10、工人的資源庫所聯(lián)結(jié)起來,便得到系統(tǒng)的整個(gè)模型,由于圖形巨大,在此予以省略.調(diào)度數(shù)學(xué)模型的建立研究的調(diào)度模型是:作業(yè)車間需要加工多種工件,每種工件有多條工藝加工路線;要求制定出一個(gè)生產(chǎn)計(jì)劃,它不僅為每一個(gè)工件決定一條工藝加工路線,而且還必須滿足整個(gè)車間的生產(chǎn)周期最短.調(diào)度的目標(biāo)為min Z (1)約束條件如下:零件i的第j條工藝加工路線中的最后一道工序(2) 零件i的第j條工藝加工路線中的非最后一道工序(3)零件i的第j條工藝加工路線中的第一道工序(4)零件i的第j條工藝加工路線和零件p的第q條工藝加工路線中都有工序要在機(jī)床設(shè)備m上加工(5)(6)所有零件只能有一條工藝加工路線被選中(7)零件i

11、的第j條工藝加工路線中的任何一道工序(8)零件i的第j條工藝加工路線和零件p的第q條工藝加工路線中都有工序由工人w來加工(9)(10)式中,Z為生產(chǎn)周期(make-span);i為零件;j為屬于一個(gè)零件的一條工藝加工路線;m為機(jī)床設(shè)備;h為零件i的某一條工藝加工路線的第h道工序;、分別為零件i的第j條工藝加工路線中的第h道工序在機(jī)床m上的加工時(shí)間和加工完畢時(shí)刻;H為非常大的正數(shù);w為工人;、分別為零件i的第j條工藝加工路線中的第h道工序由工人w加工的時(shí)間和加工完畢的時(shí)刻;為機(jī)床m加工工序h和s的順序判別條件,當(dāng)工序h和s都在機(jī)床m上被加工時(shí),如果零件i的第j條工藝加工路線中的第h道工序先于零件

12、p的第q條工藝加工路線中的第s道工序被加工,則=1,否則=0,為零件i的第j條工藝加工路線被選中的判別條件,如果選中,則=1,否則=0;為工人w加工工序h和s的順序判別條件,當(dāng)工序h和s都由工人w加工時(shí),如果零件i的第j條工藝加工路線中的第h道工序先于零件p的第q條工藝加工路線中的第s道工序被加工,則=1,否則=0.如果零件i的第j條工藝加工路線在式(2)和式(7)的條件下被選中,則式(1)中的目標(biāo)方程用來限制該工藝加工路線最后一道工序的完工時(shí)刻;式(7)確保每個(gè)零件只有一條工藝加工路線被選中;式(3)和式(4)確保對(duì)于一個(gè)指定的零件,在機(jī)床g上加工的順序h-1先于在機(jī)床m上加工的下一道工序h

13、,式(5)和式(6)確保兩道不同的工序不能同時(shí)在同一臺(tái)機(jī)床上被加工,而且任何機(jī)床在任何時(shí)候都不能加工一道以上的工序;式(5)表示零件p的第q條工藝加工路線中第s道工序在機(jī)床m上先于零件i的第j條工藝加工路線中第h道工序被加工,而式(6)表示了相反的加工順序;式(9)和式(10)確保兩道不同的工序不能同時(shí)被一名工人加工,而且任何一名工人在任何時(shí)候都不能加工一道以上的工序.動(dòng)態(tài)調(diào)度的分類處理根據(jù)車間實(shí)際工作的情況,研究的作業(yè)車間的動(dòng)態(tài)環(huán)境包括:機(jī)床設(shè)備突然損壞;損壞的機(jī)床被修復(fù);工人離崗;工人回崗;定單被取消.機(jī)床故障機(jī)床故障按其嚴(yán)重程度或所需修復(fù)時(shí)間長(zhǎng)短籠統(tǒng)分為2大類,即機(jī)床大故障和機(jī)床小故障,

14、這樣處理可以在仿真研究中屏蔽住不同的機(jī)床故障形式,因而也可以集中精力考慮如何進(jìn)行故障調(diào)度.機(jī)床大故障(11)(12)為修復(fù)故障機(jī)床m所需要的時(shí)間;、為給定的正數(shù),l為零件i所包含的工序數(shù),k為機(jī)床m故障修復(fù)好以后零件i開始加工的工序.式(11)為機(jī)床大故障/小故障的判別條件,滿足式(11)即為機(jī)床大故障,否則為機(jī)床小故障;式(12)用來判別機(jī)床故障修復(fù)好以后剩余任務(wù)的多少,是針對(duì)剩余工件的,如果滿足式(12)則剩余任務(wù)較多,否則剩余任務(wù)較少.機(jī)床發(fā)生大故障時(shí)對(duì)工件的加工有較大影響,如果等待機(jī)床修復(fù)完成再繼續(xù)加工,則很可能導(dǎo)致該批工件不能按時(shí)交貨,因此必須為這些工件尋找其它的加工路徑與設(shè)備,即滿

15、足式(11)的故障機(jī)床退出生產(chǎn)后對(duì)余下的工件進(jìn)行重新調(diào)度.機(jī)床故障被修復(fù)好以后根據(jù)剩余任務(wù)的多少來判斷是否馬上安排該機(jī)床進(jìn)入到新的調(diào)度中:滿足式(12)則剩余任務(wù)較多,機(jī)床馬上被安排進(jìn)行加工操作,即對(duì)剩余任務(wù)進(jìn)行再次調(diào)度. 不滿足式(12)則認(rèn)為剩余任務(wù)較少,該機(jī)床就不再參與這次的調(diào)度進(jìn)行加工,等該調(diào)度結(jié)束后再參與下一次的調(diào)度.否則,不但擾亂了原來的工人和機(jī)床的任務(wù)分配,而且由于剩余任務(wù)較少,調(diào)度結(jié)果與原來的相差不是很大.機(jī)床小故障如果機(jī)床故障修復(fù)時(shí)間不滿足式(11)即機(jī)床發(fā)生小故障時(shí),可以不去為故障機(jī)床上的工件另外尋找加工路徑,而寧可讓其等待該機(jī)床的修復(fù),然后再重新進(jìn)行加工.這樣處理顯然是以

16、局部的工件等待為代價(jià)來換取整體的協(xié)調(diào)有序.工人離崗工人離崗按其離崗時(shí)間長(zhǎng)短分為工人長(zhǎng)時(shí)間離崗和短時(shí)間離崗.(13)為工人w離開崗位的時(shí)間;為給定的正數(shù),式(13)用來判別工人是長(zhǎng)時(shí)間還是短時(shí)間離崗,如滿足式(13)則是工人長(zhǎng)時(shí)間離崗,否則是工人短時(shí)間離崗;工人長(zhǎng)時(shí)間離崗需對(duì)余下工件進(jìn)行重新調(diào)度,工人回歸崗位后同樣根據(jù)式(12)判別剩余任務(wù)的多少?zèng)Q定是否馬上參與再調(diào)度,這時(shí)k為工人w回來以后零件i開始加工的工序,再調(diào)度的原理同機(jī)床大故障相同.工人短時(shí)間離崗處理方式同機(jī)床小故障相同.定單取消定單取消按該定單所包含任務(wù)的多少進(jìn)行分類,即大定單和小定單.(14)f為該定單包含的工件數(shù),式(14)用來判

17、斷該定單是大定單還是小定單,如滿足式(14)則認(rèn)為是大定單,否則認(rèn)為是小定單.取消大定單時(shí)需進(jìn)行重新調(diào)度,否則很可能導(dǎo)致某些工人和機(jī)床有較長(zhǎng)的空閑時(shí)間,從而使機(jī)床和工人的加工和操作能力發(fā)揮不足,降低了機(jī)床的利用率和工人的工作效率.小定單取消不需要重新調(diào)度,由于小定單工件加工時(shí)間較短,這類定單的取消對(duì)整個(gè)調(diào)度影響不大,如果采用與取消大定單相同的調(diào)度策略,則不僅調(diào)度結(jié)果差別不大,而且由于打亂了原有的調(diào)度方案,對(duì)工人和機(jī)床干擾很大.因此,在取消小定單時(shí),可以不去為剩余的工件另外尋找加工路徑,而讓它們遵循原來的調(diào)度進(jìn)行加工.仿真結(jié)果與分析對(duì)表1和表2所示的例子進(jìn)行仿真運(yùn)算.種群規(guī)模50,交叉率為0.8,變異率為0.1,退溫指數(shù)=0.9,進(jìn)化50代后得到的調(diào)度方案見圖2(灰色表示機(jī)床/工人處于忙的狀態(tài),白色部分為機(jī)床/工人處于空閑狀態(tài)),目標(biāo)函數(shù)值為55.如果調(diào)度的最佳解不唯一,則該調(diào)度算法同樣也可以將他們?nèi)克阉鞯?該算例的最佳調(diào)度就不是唯一的,圖2所示的只是其中的一個(gè)最佳調(diào)度的Gantt圖和工人任務(wù)分配圖.圖2調(diào)度Gantt圖顯示了工序和機(jī)床的分配關(guān)系.圖中橫坐標(biāo)表明了這批零件加工的時(shí)間歷程,縱坐標(biāo)表明了機(jī)床設(shè)備,不同的零件及工序用四個(gè)字