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

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

2、擬退火算法;動態(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)是一個具有 NP 難計算復(fù)雜性的開放問題.雖然針對調(diào)度問題已經(jīng)提出了很多方法,例如排隊論模型、數(shù)學(xué)規(guī)劃、系統(tǒng)仿真、控制理論等,但是這些方法描述問題的能力很有限,所以尋找更加有效的方法是很有必要的.近年來,Petri網(wǎng)

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

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

8、型.考慮如下的一個FMS系統(tǒng),系統(tǒng)中有3種類型6臺機床,1、2號機床為類型;3號機床為類型;4、5、6號機床為類型.共有10個工件需要加工,每個工件有14個工序,工人工作表、任務(wù)參數(shù)表如表1和表2.工件 工序 加工時間 機床類型 工件 工序 加工時間 機床類型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 工人 機床1 機床2 機床3 機床4 機床5 機床61 操作 操作 2 操作 操作 3 操作

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

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

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

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

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

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

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

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

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