基于Petri網(wǎng)和啟發(fā)式搜索的調(diào)度算法研究.pdf

1、隨著工業(yè)4.0時代的到來，制造業(yè)將迎來智能工廠和智能生產(chǎn)兩大重要命題。迅速的響應客戶定制需求，在有效時間內(nèi)生產(chǎn)出高質(zhì)量和個性化產(chǎn)品成為了未來工廠核心競爭力，在此背景下的制造系統(tǒng)調(diào)度問題研究變得十分重要。本文在綜述現(xiàn)有制造系統(tǒng)調(diào)度問題這一類組合優(yōu)化問題的求解方法的基礎上，對基于Petri網(wǎng)可達圖啟發(fā)式搜索的求解方法展開了基礎性問題的研究，提出了多種能夠提高求解效率的方法。
　　該方法求解調(diào)度問題的主要思路是利用時間Petri網(wǎng)的執(zhí)行

2、能力，結(jié)合搜索算法產(chǎn)生可達圖，并在搜索過程中加入啟發(fā)式函數(shù)進行引導，以變遷激發(fā)順序的方式給出調(diào)度策略。但是該方法存在可達圖狀態(tài)數(shù)會隨著問題變大而指數(shù)性增長的問題，為了提高求解效率，現(xiàn)有研究均產(chǎn)生部分可達圖進行求解，兩大要素影響著該方法的效率:可達圖產(chǎn)生方法和啟發(fā)式函數(shù)設計。本文圍繞以上兩個關鍵點，由淺入深做了以下內(nèi)容研究:
　　1)對于最小完成時間調(diào)度問題，機器啟發(fā)式函數(shù)計算每臺機器的剩余操作時間，并選取最大值對整個過程完成時間的

3、下限進行預測，是一類重要的的啟發(fā)式函數(shù)，但是現(xiàn)有函數(shù)存在以下兩個重要問題:在柔性制造系統(tǒng)環(huán)境下，沒有準確分類剩余加工操作，會導致求解結(jié)果非最優(yōu);沒有考慮未完成操作的剩余時間，求解效率受到影響。本文針對以上情況提出了改進方法，在保證最優(yōu)性的前提下，提高了最小完成時間的預測下限，使得庫所延遲Petri網(wǎng)下的可達圖搜索方法求解效率更高。
　　2)現(xiàn)有啟發(fā)式函數(shù)均是在庫所延遲Petri網(wǎng)框架下設計的，受模型框架限制，整體效率不高。本文首次

4、提出在變遷延遲Petri網(wǎng)框架下設計啟發(fā)式函數(shù)，該方法能夠有效利用token時間戳這一時間屬性添加方式的優(yōu)勢，綜合考慮每個資源的可行時間，對完成時間的下限從機器和產(chǎn)品兩個角度進行預測。此外，現(xiàn)有方法均采用單個變遷激發(fā)方式擴展可達圖，而對于JSP（Job-shop Scheduling Problem，車間調(diào)度）這一特殊問題，本文證明在模型結(jié)構(gòu)條件滿足下，部分變遷能夠合并激發(fā)，在不影響結(jié)果最優(yōu)性的前提下能夠直接探索更深的后繼標識。以上兩個

5、方法均能夠提高用Petri網(wǎng)求解JSP的效率。
　　3)時間屬性添加方式上的不同，使得庫所延遲Petri網(wǎng)能夠抑制更多的可達圖冗余標識，而變遷延遲Petri網(wǎng)下能夠設計更加高效的啟發(fā)式函數(shù)，所以本文提出一種結(jié)合兩者優(yōu)勢的混合算法框架，在該框架中，前者用于構(gòu)建算法框架以產(chǎn)生部分可達圖并限制冗余標識，后者用以設計啟發(fā)式函數(shù)計算完成時間下限引導可達圖擴展。至此，基于Petri網(wǎng)的可達圖啟發(fā)式搜索的調(diào)度問題求解方法效率得到了明顯的提高。<

6、br>　　4)本文提出的啟發(fā)式設計方法和混合框架不僅適用于制造系統(tǒng)的調(diào)度問題，同時具備可拓展性，能夠推廣到其他帶有順序約束的組合優(yōu)化命題。本文以石化企業(yè)MES全業(yè)務流程為例，設計了一種基于石化企業(yè)MES業(yè)務流程的工作流控制系統(tǒng)。針對業(yè)務流程調(diào)度問題，在系統(tǒng)工作流服務器設計中融入了本文算法和框架，并針對更為復雜的Petri網(wǎng)結(jié)構(gòu)，調(diào)整了現(xiàn)有啟發(fā)式函數(shù)，使之能夠求解最小完成時間工作流調(diào)度問題。
　　最后，在總結(jié)全文內(nèi)容的基礎上，提出了