2PETRI網(wǎng)定義與兩種時(shí)間添加策略摘要本章首先闡述了煉油企業(yè)級優(yōu)化的意義與重要性。在此基礎(chǔ)上對煉油廠供應(yīng)鏈的背景和研究現(xiàn)狀做了介紹。關(guān)鍵字PETRI網(wǎng)21PETRI網(wǎng)基礎(chǔ)定義PETRI網(wǎng)最初由德國CARLADAMPETRI博士于上世紀(jì)60年代提出，針對當(dāng)時(shí)自動(dòng)機(jī)理論缺乏并發(fā)概念，無法研究現(xiàn)代物理學(xué)理論中典型問題，如狹義相對論，不確定性原理。PETRI博士提出了一種新的離散事件建模工具與方法PETRI網(wǎng)。PETRI博士在博士論文用自動(dòng)機(jī)通信中首次使用網(wǎng)狀結(jié)構(gòu)模擬通信系統(tǒng)，該系統(tǒng)模型后來以PETRI網(wǎng)為流傳?，F(xiàn)在我們看到的PETRI網(wǎng)既指這種模型和衍生模型，又指各種以這種模型為基礎(chǔ)發(fā)展起來的理論。PETRI網(wǎng)是一個(gè)狀態(tài)變遷模型，可用來描述系統(tǒng)中各異步成分之間的關(guān)系，而且允許同時(shí)發(fā)生多個(gè)狀態(tài)變遷，PETRI網(wǎng)是1個(gè)并發(fā)模型。在分析并行系統(tǒng)的狀態(tài)行為的技術(shù)中，PETRI網(wǎng)模型具有自然，直觀，簡單易懂等特點(diǎn)。目前在有限狀態(tài)機(jī)、通信協(xié)議、同步控制、生產(chǎn)系統(tǒng)、形式語言、多處理器系統(tǒng)建模與分析中都取得了廣泛的應(yīng)用。本文主要使用PETRI網(wǎng)對生產(chǎn)系統(tǒng)，尤其是化工批處理系統(tǒng)（過程），F(xiàn)LOWSHOP問題，F(xiàn)MS（柔性制造系統(tǒng)）進(jìn)行問題建模，同時(shí)采用了網(wǎng)的可達(dá)樹模型進(jìn)行了上述系統(tǒng)調(diào)度問題的分析和研究。PETRI網(wǎng)框架由以下幾個(gè)基本元素組成庫所，變遷和有向弧組成。在圖形上分別用圓圈、矩形和帶箭頭的連接線表示。在網(wǎng)模型通常建模對象的變動(dòng)，例如柔性制造系統(tǒng)中的機(jī)器可以處于加工狀態(tài)和閑置狀態(tài)，生產(chǎn)線上的子部件流轉(zhuǎn)均用PETRI網(wǎng)中的TOKEN表示（TOKEN，也翻譯作令牌）。圖21顯示了一個(gè)最基本的PETRI網(wǎng)模型。該模型在化工批處理過程中即可以作為一個(gè)加工裝置的生產(chǎn)過程元模型，也可以作為FMS中的一臺(tái)機(jī)器的加工操作元模型。通過對該模型在規(guī)模上的拓展和時(shí)間上的衍生，就可以得到一般性調(diào)度問題的模型。一個(gè)不具有時(shí)間屬性的通用PETRI網(wǎng)模型Z可以定義如下定義21,其中為基礎(chǔ)模型結(jié)構(gòu)，稱為基網(wǎng)，,0,1）是有限庫所集合；1,2,2）是有限變遷集合，同時(shí)和；1,2,3）是定義連接庫所到變遷有向弧的輸入函數(shù)，其中0是正整數(shù)集；4）是定義連接變遷到庫所有向弧的輸出函數(shù)；05）是初始標(biāo)識(shí)；00另有一種六元組形式化的定義，。該定義多了,0,一個(gè)庫所容量函數(shù)，按K函數(shù)的取值可將PETRI網(wǎng)分為無界網(wǎng)和有界網(wǎng)。如果取，則無界網(wǎng)，而,則為有界網(wǎng)。KK在系統(tǒng)狀態(tài)變化上，PETRI網(wǎng)給出了詳細(xì)的變遷激發(fā)規(guī)則定義22變遷激發(fā)規(guī)則當(dāng)且僅當(dāng)，變遷T能夠被激發(fā)，,0,。,其中，表示標(biāo)識(shí)M下變遷可以被激發(fā)，表示和不能同,時(shí)被激發(fā)。變遷沖突在多數(shù)情況下是由于加工資源有限引起的，我們將在相關(guān)章節(jié)中詳細(xì)討論這一問題。22時(shí)間PETRI網(wǎng)為了分析時(shí)間相關(guān)問題，例如通信系統(tǒng)中遲滯和制造系統(tǒng)中的調(diào)度問題，具有時(shí)間屬性的PETRI網(wǎng)被提出來，本文正是采用時(shí)間PETRI網(wǎng)對所研究調(diào)度問題進(jìn)行建模。PETRI網(wǎng)添加時(shí)間屬性的方式主要分為兩類庫所延遲時(shí)間PETRI網(wǎng)PLACETIMEDPETRINET，以下簡稱PTPN以及變遷延遲時(shí)間PETRI網(wǎng)TRANSITIONTIMEDPETRINET,TTPN。下面分別PTPN和TTPN的相關(guān)定義與變遷激發(fā)規(guī)則。221PTPNPTPN顧名思義，即在庫所上添加延遲來表示網(wǎng)的時(shí)間屬性。在被建模系統(tǒng)中，例如FMS，通常帶有延遲的庫所表征的是一個(gè)加工狀態(tài)。同時(shí)，建模系統(tǒng)可能存在某些庫所并不需要延遲，例如FMS中的中間緩存BUFFER。所以PTPN的庫所可以分為兩類帶有時(shí)間延遲的庫所和不帶時(shí)間延遲的庫所（也可以理解庫所延遲為0）。定義24PTPN是一個(gè)六元組，其中，,0,1）是有限庫所集合；1,2,2）是有限變遷集合，同時(shí)和；1,2,3）是定義連接庫所到變遷有向弧的輸入函數(shù)，其中0是正整數(shù)集；4）是定義連接變遷到庫所有向弧的輸出函數(shù)；05）是初始標(biāo)識(shí)；006）是分配變遷延遲的函數(shù)。0圖21是本文研究調(diào)度問題中一個(gè)基本操作（或加工步驟、處理過程）的PTPN模型。采用PTPN對該過程建模，一個(gè)基本操作將需要輸入輸出庫所,對應(yīng)著一臺(tái)機(jī)器的輸入輸出緩存，中TOKEN對應(yīng)待加工和加工完中間1,21,2件可能是最終產(chǎn)品，機(jī)器資源庫所對應(yīng)加工機(jī)器狀態(tài)，加工開始結(jié)束變遷。,由于庫所具備時(shí)間延遲，為了表示網(wǎng)時(shí)間屬性，PTPN多采用一個(gè)全局時(shí)鐘來表征網(wǎng)到達(dá)當(dāng)前標(biāo)識(shí)的時(shí)間。222PTPN網(wǎng)的全局時(shí)鐘計(jì)算方法PTPN網(wǎng)采用全局時(shí)鐘來表征網(wǎng)到達(dá)當(dāng)前標(biāo)識(shí)（狀態(tài)）的時(shí)刻，在PTPN下，變遷是立即觸發(fā)的。觸發(fā)后將消耗輸入庫所的TOKEN，并立即在輸出庫所添加TOKEN。庫所延遲體現(xiàn)在，輸出庫所新產(chǎn)生的TOKEN將在時(shí)延結(jié)束后才能用于后繼變遷的激發(fā)。時(shí)鐘的計(jì)算方法與庫所延遲以及相關(guān)輸入輸出變遷相關(guān)，如果不人為的干預(yù)變遷激發(fā)，例如在庫所后繼變遷使能后，強(qiáng)制延遲變遷激發(fā)時(shí)間。網(wǎng)的全局時(shí)鐘計(jì)算方法如下GM,由于庫所延遲描述對象的原子性，所以狀態(tài)B在后繼算法中并不存在，只是為了便于理解而添加的中間過渡狀態(tài)。P2P1TSTEP21TSTETIME0TIME0P2P1TSTETIME22P1TSTETIME2P開始計(jì)時(shí)圖21PTPN模型223TTPN網(wǎng)的時(shí)間屬性添加方法TTPN網(wǎng)為每一個(gè)TOKEN分配獨(dú)立的時(shí)間戳，其定義如下定義23TTPN是一個(gè)六元組，其中,0,1）是有限庫所集合；1,2,2）是有限變遷集合，同時(shí)和；1,2,3）是定義連接庫所到變遷有向弧的輸入函數(shù)，其中0是正整數(shù)集；4）是定義連接變遷到庫所有向弧的輸出函數(shù)；05）是初始標(biāo)識(shí)，其中是包含TOKEN數(shù)量和時(shí)間屬性的多重0集；006）是分配變遷延遲的函數(shù)。0TTPN下模型一個(gè)庫所中TOKEN的記錄方法如下1122其中，表示從時(shí)刻開始可行的TOKEN數(shù)量為，在TTPN下，變遷激發(fā)除了滿足定義22在輸入TOKEN數(shù)量上的限制，每一個(gè)用于激發(fā)變遷的TOKEN還應(yīng)滿足時(shí)間戳不大于當(dāng)前激發(fā)時(shí)間。定義25TTPN使能規(guī)則,|,|,0,轉(zhuǎn)至步驟4；步驟7判斷當(dāng)前標(biāo)識(shí)M是否為目標(biāo)標(biāo)識(shí)。如果,則進(jìn)行如下計(jì)算判斷；否則，進(jìn)行步驟8；A計(jì)算從到時(shí)間,0B如果,對上限進(jìn)行更新,0,0則稱直接相連，記為,定義432如果存在庫所和滿足以下條件1,2,則稱是相連的，中表示加工狀態(tài)的庫所則構(gòu)12,1,2,成連接的加工路徑S。,定義43RCR矩陣RCR|0,0,1,2,其中，,為連接庫所到庫所的機(jī)器資源路徑。12為這些加工庫所消耗時(shí)間之和。定義432,即為加工庫|0所P所使用的機(jī)器資源集合定義431；RS0|其中，為加工庫所P使用的機(jī)器資源數(shù)量。例如，上圖中連接和|10之間的加工路徑有兩條15和；2111,132211,14R211113R221114；R10,15MIN,R21,R22再如，因?yàn)楹椭g不存在加工路徑。0,15015表1例1所示FMS模型RCR矩陣123456789101112131415123456789101112131415由于YU在文獻(xiàn)中采用的是TTPN建模方法，用延遲變遷表示加工步驟，而PTPN用延遲庫所表示加工步驟，所以啟發(fā)式RCR需要做一定的調(diào)整。調(diào)整后定義如下定義,其中，為JOBI的終止庫所，,/|為各條最小加工路徑上所使用的機(jī)器資源集合。432LBR啟發(fā)式函數(shù)LEE在RCR矩陣的基礎(chǔ)上提出了LBR（LOWERBOUNDRESOURCES）矩陣，用于計(jì)算JOB剩余加工步驟所占用的機(jī)器資源時(shí)間。,0,庫所到庫所的沒有加工路徑,1,2,其中，S0定義LBR函數(shù)啟發(fā)式函數(shù)值，為的結(jié)束庫所。,計(jì)算單個(gè)JOB的剩余時(shí)間，選取最大值作為整個(gè)加工過程的剩余時(shí)間。當(dāng)JOB中存在多個(gè)未完成工件時(shí)，為了綜合利用多個(gè)包含TOKEN的庫所LBR值，HUANG提出了一種改進(jìn)的LBR啟發(fā)式函數(shù)定義改進(jìn)的LBR函數(shù),其中為擁有的JOB中的未完成,的工件數(shù)量433啟發(fā)式函數(shù)通過單個(gè)機(jī)器未加工操作計(jì)算剩余時(shí)間并選取最大值作為整個(gè)過程剩余時(shí)間下限8。定義，其中,是機(jī)器MAX,1,2,未開始加工操作庫所集合REMAININGOPERATIONSET,ROS。434綜合啟發(fā)式函數(shù)為了綜合性的使用以上幾種啟發(fā)式函數(shù)，HUANG在文獻(xiàn)中對以上啟發(fā)式函數(shù)取最大值進(jìn)行使用,提出綜合啟發(fā)式函數(shù)定義6。,顯然綜合性啟發(fā)式函數(shù)可以進(jìn)一步減少搜索次數(shù)，但是由于需要計(jì)算多個(gè)啟發(fā)式函數(shù)值，會(huì)增加單次迭代算法運(yùn)算量。44PTPN框架下現(xiàn)有機(jī)器啟發(fā)式函數(shù)關(guān)于在加工操作步驟問題LEE在文獻(xiàn)10中指出在計(jì)算啟發(fā)函數(shù)值時(shí)需要考慮在加工操作剩余時(shí)間問題，否則無法保證算法最優(yōu)性。441在加工操作步驟剩余時(shí)間的計(jì)算方法假設(shè)當(dāng)前標(biāo)識(shí)下，機(jī)器R關(guān)聯(lián)加工庫所為在加工操作庫所，則庫所需滿足以下條件。此時(shí)剩余時(shí)間計(jì)算法方法如下00,000,其他其中為加工庫所輸出變遷的激發(fā)時(shí)間。因同一時(shí)刻，機(jī)器R只能加工一個(gè)任務(wù)，所以滿足條件的庫所至多只有一個(gè)。此外受搜索算法限制，這保證了。0442啟發(fā)式函數(shù)的修正在考慮在加工操作問題后，PTPN下，啟發(fā)式函數(shù)需要做以下調(diào)整。,0,0,當(dāng)存在在加工操作時(shí)，在加工操作庫所中TOKEN數(shù)量為1，此時(shí)，需要計(jì)算后繼緩存庫所的RCR值，加上當(dāng)前在加工操作時(shí)間，計(jì)算JOB剩余時(shí)間。改進(jìn)后，啟發(fā)式函數(shù)值為,/|442啟發(fā)式函數(shù)的修正類比，的改進(jìn)型函數(shù)為,0,0,改進(jìn)后的啟發(fā)式函數(shù)為,443啟發(fā)式函數(shù)的問題和修正以上ROS中僅包括未開始的剩余加工操作集合，對于在加工操作忽略不計(jì)。同時(shí)，現(xiàn)有文獻(xiàn)中對于ROS定義較為模糊，在通用FMS模型下，沒有給出剩余加工操作集合計(jì)算的具體方法。針對以上情況，本文提出一種改進(jìn)的機(jī)器啟發(fā)式函數(shù)。首先，需要準(zhǔn)確區(qū)分當(dāng)前標(biāo)識(shí)下機(jī)器R剩余未完成加工操作。現(xiàn)以圖1中模型和初始標(biāo)識(shí)中為例,計(jì)算機(jī)器的過程中，雖然作為操作均R22P3，P5，P17使用了機(jī)器，但是由于存在并行加工操作庫所，中TOKEN可能不R2P2P14P1P12經(jīng)過（到達(dá)，所以我們不能將和列入機(jī)器剩余操作集合中，P3P13P4P15P3P17R2因此初始標(biāo)識(shí)下，。針對以上情況，本文對機(jī)器R未開始關(guān)聯(lián)加工25庫所集合進(jìn)行以下區(qū)分A必經(jīng)庫所IOSINEVITABLEOPERATIONSET,其中表示P屬于R相關(guān)|,|1,加工狀態(tài)庫所，表示當(dāng)前任務(wù)只有一個(gè)加工路徑,表示當(dāng)前|1標(biāo)識(shí)下所有未開始加工操作庫所集合。B選擇性庫所OOSOPTIONALOPERATIONSET|,|1,其中表示當(dāng)前任務(wù)存在選擇性路徑。|1在計(jì)算剩余操作集合元素時(shí)，因無法確定最優(yōu)調(diào)度策略在路徑多樣性下的執(zhí)行情況，所以只能計(jì)算IOS中的剩余操作，從而保證結(jié)果的最優(yōu)性。其次，我們需要計(jì)算在加工任務(wù)的剩余時(shí)間。此時(shí)，只要是使用R的操作都應(yīng)進(jìn)行考慮。綜上，本文提出一種PTPN框架下新的機(jī)器啟發(fā)式函數(shù)構(gòu)建方法。定義,其中45有效性和最優(yōu)性的證明文獻(xiàn)給出了關(guān)于啟發(fā)式函數(shù)效率比較的方法，可以作為判斷啟發(fā)式函數(shù)是否更有效的通用標(biāo)準(zhǔn)?，F(xiàn)給出其定義定義5如果對于任一非目標(biāo)標(biāo)識(shí)，,則比更有1212信息量MOREINFORMED。由于文獻(xiàn)已經(jīng)證明了RCR,LBR等啟發(fā)式函數(shù)的最優(yōu)性問題，所以在此，主要證明的有效性和最優(yōu)性問題。根據(jù)定義和定義關(guān)于有效性和最優(yōu)性的表述，需要證明以下定理。定理1。證明1）；對于機(jī)器R，如果存在加工操作則,1,2,如果不存在加工操作則0,1,2,所以，選取最大值作為輸出，。（為便于比較啟發(fā)式函數(shù)效率，本文進(jìn)行比較的在通用FMS下是最優(yōu)的，所以。）2）；現(xiàn)假設(shè)為從M到最小剩余時(shí)間激發(fā)策略下機(jī)器R的加工操作集合,顯然，所以對于機(jī)器R，如果存在加工操作，則；如果不存在在加工操作，則。同時(shí)，實(shí)際中可能包含了變遷競爭帶來的機(jī)器等待時(shí)間，所以。MAX綜上，。46測試模型461固定測試模型XIONG在文獻(xiàn)中提出了一種規(guī)模為（4個(gè)JOB,3臺(tái)機(jī)器）的固定模型進(jìn)43行算法測試，該模型被眾多學(xué)者使用進(jìn)行對比（在后續(xù)章節(jié)中，涉及到該模型統(tǒng)一稱為固定模型）。OPERATION/JOBS123411,23,41,32,322,31,23,53,433,42,22,31,3按照第二章所述的PTPN建模方法，能夠得到固定模型的PN網(wǎng)模型。P1T2P45P6TT3TT7T7P9P12P13T0T8T90429R18T2T13P6P189P20T177T4T561T19P23P256P27T34T0T18T45T8P30R2P31R1R329R30R3R2R0R0R3R2R該固定模型較為簡單，存在以下特點(diǎn)1）每個(gè)JOB內(nèi)，單個(gè)任務(wù)不存在路徑選擇；2）每個(gè)JOB內(nèi)，單個(gè)加工步驟只使用一臺(tái)機(jī)器；3）每個(gè)JOB內(nèi)，加工步驟使用的加工機(jī)器不重復(fù)。該模型更接近于FLOWSHOP調(diào)度問題，但是在此作為一種FMS模型特例進(jìn)行使用。462隨機(jī)FMS模型產(chǎn)生器為了進(jìn)一步確認(rèn)在隨機(jī)模型的執(zhí)行效率。本文采用文獻(xiàn)11中標(biāo)準(zhǔn)的隨機(jī)FMS調(diào)度問題產(chǎn)生器進(jìn)行測試。該產(chǎn)生器隨機(jī)產(chǎn)生機(jī)器資源數(shù)量M，JOB數(shù)量N，每個(gè)JOB的批量和加工序列數(shù)量,序列中的任務(wù)數(shù),每個(gè)任務(wù)的操作數(shù),以及操作的執(zhí)行時(shí)間和所需機(jī)器資源數(shù)。操作所需機(jī)器資源集合中機(jī)器必須互不相同，同時(shí)不能超過總的機(jī)器數(shù)量。以上隨機(jī)產(chǎn)生的數(shù)值均服從界于1和相應(yīng)設(shè)定值之間的均勻分布。的最大值被設(shè)定為M,N,L,S,T,O,R,P。在后續(xù)章節(jié)中，統(tǒng)一,稱為隨機(jī)FMS模型產(chǎn)生器。47改進(jìn)的機(jī)器啟發(fā)式函數(shù)試驗(yàn)471固定模型實(shí)驗(yàn)參數(shù)和結(jié)果如表2所示，表中MS是總完成時(shí)間MAKESPAN，EM是算法擴(kuò)展出的可達(dá)樹的狀態(tài)數(shù)EXPANDEDMARKING，CT是CPU運(yùn)行時(shí)間CPUTIME。表2文獻(xiàn)11中固定模型實(shí)驗(yàn)數(shù)據(jù)TABLE2EXPERIMENTPARAMETERSANDRESULTSOFFIXEDMODELFROMXIONG11（1,1,1,1）（2,2,1,1）（5,5,2,2）（8,8,4,4）（10,10,6,6）MSEMCTMSEMCTMSEMCTMSEMCTMSEMCT1710713725101110671710299259278211750642511114958626761100149321771342332392417383825554258145110100261170134376264174663251111045862368110014931802134233239241738372555465814593100261166134376301因?yàn)樗鶞y試的啟發(fā)式函數(shù)均是容許的，所以得到的調(diào)度策略MS相同且是最優(yōu)的。表3中數(shù)據(jù)同時(shí)表明，在此固定模型中，的效率較低，當(dāng)批,量增長到5,5,2,2時(shí)，算法已經(jīng)無法在合理時(shí)間內(nèi)獲得最優(yōu)解。而現(xiàn)有啟發(fā)式函數(shù)中，占用的計(jì)算資源最少。雖然需要同時(shí)計(jì)算占用了更多,的計(jì)算資源，對算法執(zhí)行效率產(chǎn)生了影響，但是從仿真結(jié)果看，該影響可以忽略。能夠進(jìn)一步降低計(jì)算需求，所需的EM和CT最小。當(dāng)采用本文提出的后，算法執(zhí)行效率有了較為明顯的提升，所需的狀態(tài)數(shù)和運(yùn)行時(shí)間是各個(gè)單獨(dú)啟發(fā)式函數(shù)中是最低的。同時(shí)，采用了綜合性方法后，較在算法性能也有明顯提升。表3中數(shù)據(jù)指出此固定模型下，由于要多計(jì)算的函數(shù)值，增加了運(yùn)算量，而本身效率已經(jīng)很高，因此相,比，優(yōu)勢并不明顯，部分實(shí)驗(yàn)中甚至需要更多CT。472隨機(jī)模型測試本文首先測試50組規(guī)模較小的隨機(jī)模型，平均測試結(jié)果如表3所示，表中為不同啟發(fā)式函數(shù)A和LB的MAKESPAN誤差率。計(jì)算方法如,下（2）,100同時(shí)，以下實(shí)驗(yàn)中，函數(shù)LBLOWERBOUND使用,即不使用任何啟0發(fā)式函數(shù)，保證了算法結(jié)果最優(yōu)。和固定模型一致，表3中各欄說,0明各啟發(fā)式函數(shù)均是最優(yōu)的。本組隨機(jī)實(shí)驗(yàn)中，在三者中，效率最高。綜合使用以上啟發(fā)式函數(shù)之后，將平均EM和CT降至3286和24，而本文提出的較在算法性能上又有了一定提升，同時(shí)結(jié)合，能夠在最少計(jì)算資源下獲得最優(yōu)解。,表3小規(guī)模隨機(jī)FMS實(shí)驗(yàn)參數(shù)和數(shù)據(jù)TABLE3EXPERIMENTRESULTSOFSMALLSCALERANDOMFMSSMRN3,TSOL2,P50,TIMES50AVERAGERDA,LBAVERAGEEMAVERAGECT061584638045483294047485078040343280328624031121836表4中等規(guī)模隨機(jī)FMS實(shí)驗(yàn)參數(shù)和數(shù)據(jù)（一）TABLE4EXPERIMENTRESULTSOFMIDDLESCALERANDOMFMSSMR4,TNLO3,S2,P50；TIMES50AVERAGERDA,LBAVERAGEEMAVERAGECT0567169380804760278260686229790606303488296035426413060307733568表5中等規(guī)模隨機(jī)FMS實(shí)驗(yàn)參數(shù)和數(shù)據(jù)（二）TABLE5EXPERIMENTRESULTSOFMIDDLESCALERANDOMFMSSMR5,NT4,LT3,SO2,P50；TIMES50AVERAGERDA,LBAVERAGEEMAVERAGECT0239564741602408439670141962638101320525178010125173530917614327然后我們又測試了兩組中等規(guī)模的隨機(jī)模型，同樣每組實(shí)驗(yàn)進(jìn)行了50次。實(shí)驗(yàn)參數(shù)和結(jié)果如下表4和表5所示，表4數(shù)據(jù)表明，在獨(dú)立啟發(fā)式函數(shù)中效率最高，較有了一定的性能提升。同樣，作為綜合使用方法，和顯著提高了算法執(zhí)行效率。隨著問題規(guī)模的變大，表5中EM和CT有了明顯的增長，但實(shí)驗(yàn)數(shù)據(jù)比較結(jié)果和表3類似。多組隨機(jī)實(shí)驗(yàn)證明了本文提出的能夠保證算法最優(yōu)性，同時(shí)又提升了機(jī)器啟發(fā)式函數(shù)的性能。在實(shí)際運(yùn)用中，雖然需要計(jì)算不同啟發(fā)式函數(shù)值，占用了更多的計(jì)算資源，但是整體的算法性能提升較為明顯，是效率最高的啟發(fā)式函數(shù)。48本章小結(jié)本章主要討論了PTPN框架的啟發(fā)式函數(shù)，LEE在文獻(xiàn)中指出了啟發(fā)式函數(shù)需要考慮在加工操作問題，但是現(xiàn)有的機(jī)器啟發(fā)式函數(shù)并沒有考慮這一問題，本章針對這一問題主要改進(jìn)了現(xiàn)有文獻(xiàn)中的機(jī)器啟發(fā)式函數(shù)，較原有算法，我們對剩余加工操作進(jìn)行合理分類，為了保證最優(yōu)性，明確提出只能計(jì)算必經(jīng)加工庫所中的剩余加工操作，同時(shí)在計(jì)算過程中，考慮了在加工操作的剩余時(shí)間，提高了剩余時(shí)間預(yù)測值下限，較有了較明顯的性能提升。在結(jié)合之后，算法能夠在最少的計(jì)算資源下獲得最優(yōu)調(diào)度策略。固定，和隨機(jī)模型實(shí)驗(yàn)均驗(yàn)證了本文提出方法的正確性和有效性。在下一章節(jié)中，我們將討論TTPN搜索框架下的啟發(fā)式函數(shù)問題，對啟發(fā)式函數(shù)進(jìn)行改進(jìn)。第五章TTPN下啟發(fā)式函數(shù)設(shè)計(jì)51TTPN框架下啟發(fā)式函數(shù)的特點(diǎn)TTPN框架和PTPN框架最大的不同之處在于時(shí)間屬性的添加上，由于TTPN框架有獨(dú)立的TOKEN時(shí)間戳，所以不需要全局時(shí)鐘控制標(biāo)識(shí)的變化。在TTPN下，并不存在加工狀態(tài)。加工變遷一旦觸發(fā)，TOKEN的時(shí)間戳變化可以直接繼續(xù)計(jì)算。這一特點(diǎn)決定了TTPN框架下啟發(fā)式函數(shù)具有以下特點(diǎn)1）無在加工操作狀態(tài)無在加工操作狀態(tài)使得啟發(fā)式函數(shù)計(jì)算時(shí)，不用考慮LBR,RCR,MIU等啟發(fā)式函數(shù)在PTPN下的在加工狀態(tài)問題。2）可以設(shè)計(jì)更加精細(xì)的啟發(fā)式函數(shù)TTPN每一個(gè)TOKEN都包含有可行時(shí)間信息，相對于PTPN，模型信息更加豐富，可以基于此設(shè)計(jì)更加精細(xì)的啟發(fā)式函數(shù)。本章將詳細(xì)介紹新構(gòu)建的一種JOB和機(jī)器啟發(fā)式函數(shù)。52TTPN下的JSP問題建模521JSP問題一般性描述JSP車間調(diào)度問題是制造系統(tǒng)傳統(tǒng)調(diào)度問題，同樣屬于組合約束優(yōu)化和典型NP男問題。和FMS調(diào)度問題一樣，JSP也可以采用數(shù)學(xué)規(guī)劃方法，但是數(shù)學(xué)規(guī)模不可能太大，且實(shí)用性比較差。目前主要采用領(lǐng)域搜索和智能算法進(jìn)行調(diào)度問題求解，例如TABUSEARCH,滅火法等。而本文提供另外一種求解思路，利用時(shí)間PETRI網(wǎng)進(jìn)行調(diào)度問題求解。JSP問題一般可被描述為M臺(tái)不同的機(jī)器，L臺(tái)不同的工件，每個(gè)工件有躲到供需，每到供需由指定的機(jī)器在固定的時(shí)間內(nèi)完成。一道工序一旦開始，就無法中斷，具備原子性。每臺(tái)機(jī)器一次只能加工一道工序。最小時(shí)間調(diào)度問題便是決定每臺(tái)工序的加工順序，使得機(jī)器完成所有工件的時(shí)間最短。具體數(shù)來，該問題就是要求在滿足工件加工次序要求和制定機(jī)器約束的條件下，確定每臺(tái)機(jī)器上工序的順序，使得從所有加工過程開始到結(jié)束的時(shí)間間隔最小。522JSP問題的TTPN模型相對于FMS調(diào)度，JSP問題相對簡單，不需要考慮路徑多樣性問題，同時(shí)也不需要考慮機(jī)器在相同工件中重復(fù)使用問題，可視為一類特殊FMS調(diào)度問題加以研究?，F(xiàn)以一條簡單的JSP調(diào)度問題說明TTPN建模過程，表21給出了該JSP加工要求。123工序12,51,51,4工序23,33,42,1工序31,32,53,3現(xiàn)以BNET方法對以上JSP問題進(jìn)行建模，可以得到如圖1所示的TTPN模型。JSP問題可以轉(zhuǎn)換為相應(yīng)的TTPN變遷激發(fā)次序安排問題，和PTPN下模型類似，不要對算法進(jìn)行修改即可通過搜索獲得調(diào)度策略，在此不再贅述。M1M2M3P21P2P23T21T2P24T23P31P32P3T31T32P34T3121TT114T131MMM2123ODELSIZ353TTPN框架下的啟發(fā)式函數(shù),531TTPN下啟發(fā)式函數(shù)由于每個(gè)TOKEN都具備獨(dú)立時(shí)間戳，表征機(jī)器當(dāng)前可行時(shí)間，所以計(jì)算每臺(tái)機(jī)器的剩余加工時(shí)間不能和PTPN下一樣，僅計(jì)算剩余加工步驟，而不考慮當(dāng)前機(jī)器可行時(shí)間。定義31其中，表示機(jī)器的剩余加工操作集合，和PTPN下不同的是，此處的計(jì)算方法較為簡單，不需要考慮路徑多樣性問題。表示剩余加工操作對于變遷會(huì)激發(fā)的次數(shù)。532TTPN下啟發(fā)式函數(shù)JSP問題的TTPN啟發(fā)式函數(shù)對應(yīng)LBR矩陣需要做以下變動(dòng)定義32,0,庫所到庫所的沒有加工路徑由于不存在路徑多樣性問題，從至多可能存在一條路徑。庫所到庫所此處需注意的是的計(jì)算方法有了小的變動(dòng)定義330即計(jì)算路徑S中的所有的變遷時(shí)間之和。和一樣，由于獨(dú)立時(shí)間戳的設(shè)置，需要獨(dú)立計(jì)算每一個(gè)JOB的完成時(shí)間。在批量為1情況下，啟發(fā)式函數(shù)組織形式如下定義34MAX,1,2,庫所為中擁有TOKEN的庫所，而則為結(jié)束庫所。在批量大于1的情況下，需要考慮最優(yōu)性問題，對于單個(gè)JOB，只能選取最大的TOKEN進(jìn)行計(jì)算，定義如下定義34MAX,1,2,533TTPN下啟發(fā)式函數(shù)不用考慮路徑多樣性問題，JSP問題的TTPN啟發(fā)式函數(shù)使用的RCR矩陣和LBR矩陣一致，在此不在贅述。由于RCR方法考慮的是機(jī)器平均剩余時(shí)間，和PTPN下的PTPN類似。給出定義定義35,/|54TTPN新構(gòu)建的啟發(fā)式函數(shù)541無路徑選擇和重復(fù)機(jī)器選擇情況下啟發(fā)式函數(shù)FLOWSHOP問題現(xiàn)有TTPN啟發(fā)式函數(shù)僅通過標(biāo)識(shí)TOKEN數(shù)量信息和PETRI網(wǎng)模型結(jié)構(gòu)求解JOB或者機(jī)器資源剩余加工時(shí)間，而作為TTPN的一個(gè)重要特征，獨(dú)立時(shí)間戳并沒有被考慮。本節(jié)將著重介紹一種充分利用這一特征的啟發(fā)式函數(shù)設(shè)計(jì)方法，并證明其有效性和最優(yōu)性。5411JOB函數(shù)根據(jù)TTPN激發(fā)規(guī)則，變遷必須等待所有輸入庫所中TOKEN滿足變遷弧上數(shù)量要求后才能進(jìn)行激發(fā)?，F(xiàn)假設(shè)代表待加工的工件到達(dá)緩存庫所的時(shí)間為，接下來將完成變遷所代表加工操作，使用的機(jī)器資源為，那11么在沒有其他JOB變遷競爭的情況下，激發(fā)以及工件到達(dá)的時(shí)間可以11按照以下估計(jì)；1MAX,11進(jìn)一步分析，現(xiàn)假設(shè)有加工路徑如圖所示。按照以上無競爭原則，則中TOKEN到達(dá)的時(shí)間可以按照以下方法進(jìn)行估計(jì)PSP1PIT1T2PI1TIPFTF12IF1MAX,112MAX1,22MAX1,至此，我們可以總結(jié)出一個(gè)計(jì)算連接起始庫所和目標(biāo)庫所的最小剩余時(shí)間估計(jì)方法。,1,11,222,公式1那么在單批量（每個(gè)JOB待加工工件數(shù)量至多為1）問題下的JOB啟發(fā)式函數(shù)為公式2MAX,1,2,其中表示中包含有TOKEN的剩余加工操作開始庫所，為為結(jié)束庫所；啟發(fā)式函數(shù)的特點(diǎn)便是除了考慮剩余加工步驟的時(shí)延，還應(yīng)考慮所使用的機(jī)器資源的可行時(shí)間，比現(xiàn)有算法更加合理高效，我們將在后續(xù)部分中證明的有效性和最優(yōu)性。5412MACHINE函數(shù)對于機(jī)器啟發(fā)式函數(shù)，我們可以采用的形式進(jìn)行改進(jìn)，機(jī)器資源的加工操作完成時(shí)間估計(jì)為，但是在TTPN下，我們能夠進(jìn)一步提高該下限。假設(shè)存在如圖所示情況，加工機(jī)器對應(yīng)的操作為,但是的輸入庫所當(dāng)前標(biāo)識(shí)下并沒有TOKEN，所以的剩余加工時(shí)間需要考慮這一時(shí)延。同樣的，我們先考慮單批量問題，假設(shè)位于同一JOB的庫所擁有TOKEN，那么在沒有其他JOB競爭的情況下，中TOKEN到達(dá)的時(shí)間可以按照公式1進(jìn)行估計(jì)。,將這種情況進(jìn)行推廣，假設(shè)是使用機(jī)器資源的所有加工操作。對于任一，我們都要計(jì)算器前置庫所出現(xiàn)TOKEN的最早時(shí)間，然后選取最小值，并綜合考慮機(jī)器本身的可行時(shí)間，作為下一個(gè)加工步驟的開始時(shí)間進(jìn)行預(yù)估，即。,那么機(jī)器的完成時(shí)間預(yù)估方法則調(diào)整為。單批量情況下的機(jī)器啟發(fā)式函數(shù)則可以調(diào)整為公式35413多批量情況的拓展在多批量情況下，需要考慮加工操作的并行問題，否則無法保證最優(yōu)性。啟發(fā)式函數(shù)的處理方式是選取最大的TOKEN計(jì)算或者取多個(gè)TOKEN的平均來保證最優(yōu)性。式4MAX,或者，平均方法沒有最,/大值方法有效因?yàn)椋?/MAX,其中是中有TOKEN的庫所。當(dāng)批量為1時(shí)，式4和式1沒有什么不同，故可以作為統(tǒng)一的LBR方法進(jìn)行下面的討論。而本文的JOB啟發(fā)式函數(shù)則可以充分利用TOKEN時(shí)間戳這一特性對并發(fā)現(xiàn)象進(jìn)行考察。在中，我們僅承認(rèn)JOB間的最大并行性，一個(gè)JOB能夠在沒有競爭的情況下完成所有操作，但是在JOB內(nèi)部，我們必須要考慮操作間的并發(fā)問題以獲得一個(gè)更加準(zhǔn)確的下限。而我們的計(jì)算方法并不復(fù)雜只需重復(fù)利用上述公式一計(jì)算過程即可。例如，現(xiàn)有加工流程如圖所示，該JOB有兩個(gè)未完成的工件，TOKEN分別存在于庫所和中，我們需按照，的順序?qū)φ麄€(gè)JOB進(jìn)行完成時(shí)間計(jì)算，1212而中TOKEN到達(dá)目標(biāo)庫所的時(shí)間就為JOB完成時(shí)間。2計(jì)算過程如下1）中TOKEN的完成時(shí)間為；11,2）更新從到中間的變遷使用的機(jī)器的時(shí)間戳為11MAX,13）中TOKEN的完成時(shí)間為；22,從另一角度解釋，在計(jì)算中TOKEN完成時(shí)間時(shí)，需要用更新“使用2過的”機(jī)器資源。這樣整個(gè)加工過程可以被分為兩個(gè)部分，第一部分包含從到的機(jī)器，該部分的12121,11,222,第二部分為從到的機(jī)器，這部分機(jī)器已經(jīng)使用過。1；211,綜上，JOB完成時(shí)間估計(jì)可以按一下方式進(jìn)行計(jì)算1,2當(dāng)未完成工件數(shù)量大于2時(shí)，計(jì)算過程和上述過程類似，但是需要遵循以下原則1）計(jì)算順序“由深到淺，由小到大”，即從離目標(biāo)庫所最近的庫所開始計(jì)算起，對于相同庫所，則需要先計(jì)算時(shí)間戳小的TOKEN完成時(shí)間，再計(jì)算時(shí)間戳較大的TOKEN；2）完成一次計(jì)算后，需要立即更新被使用過的機(jī)器時(shí)間戳。3）最淺庫所最大時(shí)間戳的TOKEN完成時(shí)間為整個(gè)JOB完成時(shí)間。PPIPI1TIPTT1T以上便是在對于多批量情況的拓展，機(jī)器啟發(fā)式函數(shù)的多批量拓展相對簡單，只需注意以下問題。4）計(jì)算延遲時(shí)，需要計(jì)算離最近的庫所時(shí)間戳最小的TOKEN抵達(dá)相應(yīng)前置庫所的時(shí)間，以此作為最小開始時(shí)間依據(jù)。5）在計(jì)算時(shí)注意多批量的加工操作需要重復(fù)計(jì)數(shù)問題。此時(shí)，加工變遷的前置庫所擁有TOKEN的時(shí)間變?yōu)?為離變遷T最近的包含TOKEN的庫所。而在單批量情況下，擁有TOKEN的庫所即為離變遷最近的庫所，所以從這一點(diǎn)上是一致的。如此我們便可總結(jié)出TTPN根據(jù)TOKEN時(shí)間戳設(shè)計(jì)的啟發(fā)式函數(shù)MAX,MAX,2在迭代中，我們考慮的機(jī)器可行時(shí)間1MAX,1是當(dāng)前標(biāo)識(shí)下，并且假設(shè)其他JOB并沒有參與到競爭中來，如果其他JOB使用了路徑上的機(jī)器，,表示實(shí)際情況下，當(dāng)變遷激發(fā)時(shí)，機(jī)器的可行時(shí)間。所以，作為迭代結(jié)果多批量情況下也是如此。啟發(fā)函數(shù)定理41,其中表示當(dāng)前標(biāo)識(shí)下，實(shí)際能夠獲得的最小完成時(shí)間。1）；是最小開始時(shí)間因?yàn)槲覀儍H承認(rèn)由,之間的變遷激發(fā)導(dǎo)致的延遲，在理想情況下即當(dāng)前,標(biāo)識(shí)前置庫所即存在TOKEN。所以，MAX,故；2）同樣的，由于競爭的存在，同時(shí)，也是理想情況下的連續(xù)激發(fā)。故55針對TTPN模型的激發(fā)策略改進(jìn)551單個(gè)變遷激發(fā)策略在現(xiàn)有的搜索算法忽視了PETRI網(wǎng)的并發(fā)現(xiàn)象，在迭代過程中，多選擇單個(gè)變遷進(jìn)行觸發(fā)。但是，在特定情形下，同時(shí)激發(fā)多個(gè)非沖突變遷將不會(huì)影響搜索結(jié)果的最優(yōu)性，并且能夠直接搜索到更深的節(jié)點(diǎn)，減少算法運(yùn)算量。然后，對非沖突變遷進(jìn)行隨意組合激發(fā)可能會(huì)因?yàn)樽顑?yōu)路徑上的標(biāo)識(shí)丟失，導(dǎo)致搜索結(jié)果非最優(yōu)。例如如圖所示，和是當(dāng)前標(biāo)識(shí)下的使能的非沖突變14遷。對于變遷，存在以下激發(fā)次序1，2（其他激發(fā)順序1,2,41,2,41,4,2將和這兩者產(chǎn)生相同的后繼標(biāo)識(shí)）。同時(shí)激發(fā)和將會(huì)損失第二種情況，但是無法保證激發(fā)次序1優(yōu)于次序142。因而，對非沖突變遷不能進(jìn)行隨意組合。圖顯示了該情形。經(jīng)過組合，和會(huì)丟失，在未獲得前，不知道完成時(shí)間小于。46667任意可行調(diào)度策略均可被分解成多臺(tái)機(jī)器來自不同JOB的操作排序組合，而最優(yōu)調(diào)度策略則是從中選取最優(yōu)的一種組合可能。在搜索過程中，選取不同沖突變遷激發(fā)順序?qū)嶋H上是選擇不同操作排序可能。在可達(dá)樹搜索過程中，每一個(gè)標(biāo)識(shí)的信息包含了已經(jīng)完成的部分操作，以及這些操作的排序。啟發(fā)式搜索對應(yīng)于通過啟發(fā)式規(guī)則來優(yōu)先探索部分排序可能，或者放棄部分排序可能。定理能夠一起激發(fā)并且不影響最優(yōu)性，如果滿足以下條件,1）,。是所屬JOB所有后續(xù)加工操作相應(yīng)變遷集合。2）,；3）；證明即以及后續(xù)變遷將不會(huì)競爭任何機(jī)器資源，由于屬于,不同JOB，又不會(huì)使用相同的緩存庫所。因此，激發(fā)中的操作排序?qū)⒉粫?huì),影響中的操作排序可能，反之也是如此。進(jìn)而，同時(shí)激發(fā)來和的變遷將不會(huì)影響獲得最優(yōu)調(diào)度策略。單個(gè)變遷激發(fā)策略使得算法能夠探查所有排序可能，然后搜索速度較慢。兩個(gè)變遷如果滿足以上條件，合并激發(fā)將不會(huì)影響后續(xù)對于機(jī)器排序的可能，所丟失的狀態(tài)實(shí)際上搜索過程中的部分重復(fù)冗余標(biāo)識(shí)。以圖所示模型為例，變遷能夠同時(shí)激發(fā)，13,241313，14，15，,2424，251313,14,15,16,3,4,52424,25,26,1,2表示相互獨(dú)立，是否激發(fā)將對的輸入庫所和后繼庫所132413,241324中TOKEN變化不產(chǎn)生任何影響。推論如果，,，則也能同時(shí)激發(fā)而不影響算，法最優(yōu)性。證明如果兩個(gè)變遷滿足定理1，顯然他們的后續(xù)變遷均滿足定理1條件。變遷組合算法步驟1初始化,1,2,1,2,WHILE,SELECTFOR,FOR,IF,IF,THENFOR,IF,BREAKOUTPUTASTHEGROUP變遷隨機(jī)組合算法,1,2,STEP1初始化,1,2,WHILE,SELECT,FOR,IF,TCTCWHILE|FOR1_IF,SELECTFROM,OUTPUTASTHEFIRINGGROUP作為對比，我們同樣給出非沖突變遷隨機(jī)組合算法。在實(shí)施中，我們用變遷激發(fā)組來代替單個(gè)變遷產(chǎn)生后繼標(biāo)識(shí)。56實(shí)驗(yàn)例證561FLOWSHOP模型產(chǎn)生器SIZEMNNUMBEROFPLACEMN1NP1_1T1_1P1_2T1_2T1_NP1_N1T2_1P2_2T2_2T2_NP2_N1P2_1TM_1PM_2TM_2TM_NPM_1PM_N1NOPERATIONSMJOBSNUMBEROFTRANSITIONSMNNUMBEROFMACHINESN