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

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

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

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

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

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

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