基于非合作博弈和RFID的緊急加單下柔性作業(yè)車間動態(tài)調(diào)度方法

王 晉 彭琰舉 羅庚合

(①西安航空學(xué)院機械工程學(xué)院，陜西西安710077;②西北工業(yè)大學(xué)現(xiàn)代設(shè)計與集成制造技術(shù)教育部重點實驗室，陜西西安710072)

車間調(diào)度問題作為提高企業(yè)競爭力的一個核心問題，吸引著大量的學(xué)者進行廣泛而深入的研究。在傳統(tǒng)的柔性作業(yè)車間生產(chǎn)調(diào)度問題中，學(xué)者們主要對靜態(tài)環(huán)境下的車間調(diào)度問題進行了研究，并沒有考慮車間環(huán)境本身的不確定性和動態(tài)性。但在實際的柔性作業(yè)車間制造環(huán)境中，一些不可預(yù)見或隨機的內(nèi)外擾動事件的發(fā)生使得原有的調(diào)度計劃不可行。例如:機器故障［1］、工人缺勤［2］、工序加工時間相對于計劃延長或者縮短［3］、物料未能及時送達［4］、新的訂單加入［5］或訂單取消［6］等，因而需要采取動態(tài)調(diào)度的方法，以快速響應(yīng)環(huán)境變化，修復(fù)原有調(diào)度計劃，使生產(chǎn)調(diào)度持續(xù)優(yōu)化運行。由于生產(chǎn)過程和動態(tài)調(diào)度是并行的，因此要求對原調(diào)度的修復(fù)時間盡可能短，使之對調(diào)度系統(tǒng)的性能影響降到最低;并且重調(diào)度和原調(diào)度之間要銜接合理，保證生產(chǎn)過程的高效性［7］。這就對柔性作業(yè)車間動態(tài)調(diào)度算法穩(wěn)定性和算法對異常事件的響應(yīng)能力提出了更高的要求。

近年來，隨著信息和傳感技術(shù)的快速發(fā)展和廣泛應(yīng)用，很多企業(yè)已經(jīng)開始采用這些技術(shù)對車間中生產(chǎn)情況進行實時的追蹤和追溯，以改善車間調(diào)度系統(tǒng)的性能?，F(xiàn)今，許多學(xué)者通過將云制造和物聯(lián)制造技術(shù)應(yīng)用到工業(yè)制造中，使得生產(chǎn)中的實時數(shù)據(jù)已經(jīng)變得無處不在，這將使各種制造資源的實時狀態(tài)能夠被容易的感知。因此，在真實的制造環(huán)境中，實時的制造數(shù)據(jù)將會挑戰(zhàn)傳統(tǒng)的多目標動態(tài)調(diào)度問題。例如Pach等［8］提出了一種在動態(tài)環(huán)境中的完全反應(yīng)式方法來對柔性制造系統(tǒng)進行調(diào)度，他們考慮的3個目標，分別是時間、能耗和資源轉(zhuǎn)換數(shù)。Cuihua等［9］提出了一種新的方法來處理簡單的調(diào)度問題，該方法采用RFID來獲取車間中的實時制造信息，用來增加調(diào)度結(jié)果的可行性并且能夠提高制造過程的智能化和有效性。

盡管這些研究有著重大的意義，但是在實時制造車間中，伴隨著生產(chǎn)任務(wù)的復(fù)雜性，生產(chǎn)異常的隨機性，柔性作業(yè)車間的調(diào)度方法仍然有以下的問題。

(1)如何設(shè)計一種新的緊急加單下柔性作業(yè)車間的分配方法來實現(xiàn)緊急加單的任務(wù)分配。一般來說，現(xiàn)有的緊急加單處理方法是遵循給定的目標集中式的將加單進行分配。然而，在生產(chǎn)執(zhí)行階段，伴隨著加單數(shù)量和加單頻率的增加會導(dǎo)致生產(chǎn)調(diào)度系統(tǒng)的性能出現(xiàn)下滑，因此需要設(shè)計一種新的基于實時數(shù)據(jù)的緊急加單下柔性作業(yè)車間調(diào)度方法來避免或者減少對調(diào)度系統(tǒng)性能的影響。

(2)如何在物聯(lián)制造車間中對調(diào)度系統(tǒng)的快速性和穩(wěn)定性進行優(yōu)化。當(dāng)前，對于緊急加單下的柔性作業(yè)車間的問題已經(jīng)吸引了大量的學(xué)者進行研究。一般來說，解決緊急加單下柔性作業(yè)車間的方法分為兩種:反應(yīng)式調(diào)度和預(yù)測反應(yīng)調(diào)度。預(yù)測反應(yīng)式調(diào)度是指在調(diào)度的生成階段不考慮制造環(huán)節(jié)的不確定性，只在不確定因素發(fā)生時重新進行調(diào)度。這種調(diào)度模式是目前眾多學(xué)者研究的重點。在預(yù)測反應(yīng)式調(diào)度中，大部分研究將時間作為優(yōu)化的目標。但是近年來，對于穩(wěn)定性和快速性的優(yōu)化越來越受到學(xué)者們的關(guān)注。然而，現(xiàn)有的文章多數(shù)考慮在傳統(tǒng)的制造車間中進行調(diào)度，并沒有考慮車間中的實時數(shù)據(jù)。

基于上述分析，針對路徑柔性和工藝柔性的柔性作業(yè)車間調(diào)度問題，本文首先建立了基于非合作博弈和RFID的緊急訂單下柔性作業(yè)車間動態(tài)調(diào)度方法體系框架，然后以柔性作業(yè)車間生產(chǎn)調(diào)度系統(tǒng)的快速性和穩(wěn)定性為目標，在考慮有緊急加單發(fā)生的動態(tài)生產(chǎn)環(huán)境基礎(chǔ)上，建立了基于非合作博弈的柔性作業(yè)車間動態(tài)調(diào)度模型;然后，結(jié)合完全信息下的靜態(tài)博弈理論，提出了基于非合作博弈的柔性作業(yè)車間動態(tài)調(diào)度算法，并給出了一種緊急加單任務(wù)的分配策略。

1 基于非合作博弈和RFID的緊急訂單下柔性作業(yè)車間動態(tài)調(diào)度方法體系框架

在傳統(tǒng)的柔性制造車間動態(tài)調(diào)度問題中，當(dāng)有緊急加單時，生產(chǎn)調(diào)度系統(tǒng)會將所有的加單集中地分配給相應(yīng)的機器。在這種集中調(diào)度的模式下，機器不能和其它的制造資源進行實時的交互，所以當(dāng)有緊急加單進行調(diào)度時，制造資源的實時數(shù)據(jù)并沒有被考慮。本文針對以上問題，提出了在緊急加單發(fā)生時，基于機器和制造資源相互感知情況下的實時調(diào)度分配策略，共包含3個模塊:(1)物聯(lián)制造車間模塊。(2)緊急加單下柔性車間動態(tài)調(diào)度的分配策略模塊。(3)基于博弈論的緊急加單下柔性車間動態(tài)調(diào)度方法模塊，如圖1所示。首先將RFID的讀寫器以及標簽貼在機器以及相應(yīng)的制造資源上，那么一個RFID驅(qū)動的實時制造車間就被建立起來。在這個實時數(shù)據(jù)驅(qū)動的車間環(huán)境中，將所有的緊急加單放入一個訂單任務(wù)池，選取訂單任務(wù)池中的兩道工序放入待調(diào)度任務(wù)池，然后待調(diào)度任務(wù)池中的每道工序?qū)詣拥匕l(fā)送它自己的實時狀態(tài)信息并且請求相應(yīng)的機器。此時工序和機器通過RFID持續(xù)進行交互。按照機器以及工序的實時狀態(tài)信息，加單的工序通過博弈的方法被分配到最優(yōu)的機器上。通過這種機器和制造資源感知的分配策略，當(dāng)有緊急訂單發(fā)生時，每道加單的工序都可以被分配到最優(yōu)的機器上。并且因為每一時刻只有兩道工序被分配到最優(yōu)的機器上，所以伴隨著緊急加單量和機器數(shù)的增加，調(diào)度問題的復(fù)雜性不會變化。又因為工序的分配是實時狀態(tài)信息驅(qū)動的，故此分配策略可以盡可能地消除在傳統(tǒng)的分配策略中發(fā)生的當(dāng)有大量加單時對原調(diào)度計劃的影響。

2 基于博弈論的緊急加單下柔性作業(yè)車間動態(tài)調(diào)度模型

柔性作業(yè)車間動態(tài)調(diào)度問題描述為:有n個工件{O1，O2，…，On}在 m 臺機器{m1，m2，…，mm}上加工，每個工件Oi有ni道工序組成，工件的每道工序可由m臺機器中的多臺機器加工，Mij表示可以加工工件i的第 j道工序的機器集合，Mij{1，2，…，M}，工序 Oij可使用Mij中的任一機器加工，加工時間隨所選擇機器的不同而不同［10］。然而，工件在生產(chǎn)過程中常常存在一些突發(fā)事件，如緊急加單等。因此，本文正是基于上述問題，為緊急加單的每道工序選擇合適的機器，并確定每臺機器上各緊急加單工序的最佳加工順序和開工時間，使生產(chǎn)調(diào)度系統(tǒng)快速性和穩(wěn)定性達到最優(yōu)。為了研究的可操作性，給出如下假設(shè):

(1)每臺機器在任何時刻最多加工一道工序。

(2)每道工序在一個時刻只能在一臺機器上加工。

(3)所有的工件必須按照一個給定的順序加工。

(4)緊急加單中的工序具有加工的優(yōu)先權(quán)。

為了建立數(shù)學(xué)模型，對一些符號和變量定義如表1所示。

表1 符號和變量定義

2.1 博弈模型建立

在柔性作業(yè)車間動態(tài)調(diào)度中，當(dāng)有緊急加單進行重調(diào)度時，調(diào)度系統(tǒng)的快速性和穩(wěn)定性是兩個考慮較多的性能指標。但是這兩個指標在一般情況下是相互矛盾的，不能同時滿足。也就是說當(dāng)其中一個指標達到最優(yōu)時，另外一個指標可能變壞。因此，如何在車間動態(tài)調(diào)度過程中安排工序，使得調(diào)度結(jié)果的快速性和穩(wěn)定性達到滿意的效果需要進行深入研究。本文從博弈論的角度出發(fā)，建立了基于非合作博弈的調(diào)度模型，如圖2所示。

在建立模型之前，首先要確定模型的3個基本元素:參與者、決策集以及收益函數(shù)。調(diào)度模型可以用以下三元組表示:

N是參與者的集合。就本文而言，因為待調(diào)度任務(wù)池中的工序是變化的，故該博弈分為K個階段。在每個階段的博弈中，將待調(diào)度任務(wù)池中的工序作為參與者，每個參與者都能夠獨立做出決策而不相互影響。因此該模型是一個完全信息下兩人的非合作博弈模型。則在第k個博弈階段，參與者集合描述如下:

在兩人博弈中，按照每個參與者可采取的策略，收益函數(shù)可以寫成一個大小為q1×q2的矩陣，如式(5)所示:

2.2 求解博弈模型

本文針對兩人博弈的特點，給出了基于雙矩陣的Nash均衡點求解方法。

對于任意的策略組合(αi，βj)，記收益函數(shù) U1(αi，βj)=aij，U2(αi，βj)=bij，則兩個局中人的收益函數(shù)分別記為矩陣A和矩陣B:

以上兩個矩陣，也可記為:

算法總體思想:

(1)對局中人 1，在矩陣(aij，bij)m×n的每一行 i中，找出對方支付矩陣B中該行的最大元素，即=max{bij|j=1，2，…，n}并記錄。當(dāng)不唯一時，均記錄;

(2)對局中人 2，在矩陣(aij，bij)m×n的每一列 j中，找出對方支付矩陣A中該列的最大元素，即=max{aij|i=1，2，…，m}并記錄。當(dāng)不唯一時，均記錄。

(3)如果存在一對(i*，j*)，使得兩元素和都被記錄，則()是純策略納什均衡。

(4)對不存在滿足(3)的數(shù)對(i*，j*)，則該博弈無純策略納什均衡。

因為在此博弈模型下，無法保證純策略Nash均衡點的個數(shù):可能沒有純策略Nash均衡點或者存在多個Nash均衡點，故局中人無法知道采取何種行動。為了克服純策略所帶來的缺陷，本文提出了近似Nash均衡解的概念。近似合作Nash均衡解的概念如下:

設(shè)(aij，bij)為兩個機器的收益值，滿足下式的解為近似Nash均衡解:

基于上述定義，在多個Nash均衡解或無Nash均衡解的情況下，近似Nash均衡解的求解方法如下:

(1)如果算法1的輸出是空值，則計算支付矩陣下每種策略［||+||］的值。

(2)按照式(6)獲取CNE。如果此時CNE超過一個，則隨機選取一個。

(3)如果算法1輸出的Nash均衡點超過1個，則將這些Nash均衡點按照公式(6)進行計算。

(4)選取最合適的Nash均衡點。

3 動態(tài)調(diào)度策略

目前求解緊急加單下的柔性動態(tài)調(diào)度問題一般采用預(yù)測—反應(yīng)式調(diào)度的方法。該方法分為兩個階段:預(yù)調(diào)度和重調(diào)度。在預(yù)調(diào)度階段，調(diào)度考慮未來緊急加單的影響，通常是在每道工序之前插入一定長度的空閑時間，然后生成預(yù)調(diào)度;在緊急加單發(fā)生之前，所有工件按照預(yù)調(diào)度的結(jié)果進行加工。一旦出現(xiàn)緊急加單，則采用右移［11］、更改路徑［12］或者完全重調(diào)度［13］的方法。鑒于此，本文基于預(yù)測—反應(yīng)式調(diào)度，并且采用右移重調(diào)度方法，給出了一種基于博弈的緊急加單下柔性作業(yè)車間動態(tài)調(diào)度的策略，如圖3所示。

3.1 調(diào)度任務(wù)池

在本文中，將調(diào)度的任務(wù)池分為訂單任務(wù)池、待調(diào)度任務(wù)池和已調(diào)度任務(wù)池。訂單任務(wù)池中存放著緊急訂單的工序;待調(diào)度任務(wù)池放著需要進行調(diào)度的工序;已調(diào)度任務(wù)池則放著已經(jīng)調(diào)度完的工序。初始時刻，按新進訂單的交貨期的先后排列，依次將每兩個訂單的第一道工序放入到待調(diào)度任務(wù)池中進行調(diào)度，直到所有訂單的第一道工序分配完成;每當(dāng)有兩道工序加工完成后，則將這兩道工序的下一道工序放入待調(diào)度任務(wù)池中進行調(diào)度;分配完成后的工序就轉(zhuǎn)入已調(diào)度任務(wù)池中。

3.2 再調(diào)度策略

在原有生產(chǎn)調(diào)度執(zhí)行過程中，當(dāng)有緊急加單時，選取離交貨期最近的兩個訂單的第一道工序Oi1和Oj1放入調(diào)度任務(wù)池中，進而進行機床匹配，則具有加工Oi1的機器集為{mi，mj，…，mk}，具有加工 Oj1的機器集為{mo，mp，…，mq}，其中{mi，mj，…，mk}∩{mo，mp，…，mq}可能為空集，也可能不為空集。然后工序Oi1和Oj1根據(jù)系統(tǒng)的快速性和穩(wěn)定性指標進行博弈，將工序Oi1和Oj1分配到相應(yīng)的機器，并根據(jù)右移重調(diào)度方法將工序Oi1和Oj1插入到原調(diào)度中生成新的調(diào)度計劃。最后將工序Oi1和Oj1放入已調(diào)度任務(wù)池中。同理可將每個訂單的第一道工序分配到最優(yōu)的機器上。若出現(xiàn)訂單數(shù)為奇數(shù)時，則最后一個新進訂單的第一道工序加入到第二道工序的分配中去，并且第一道工序具有優(yōu)選分配權(quán)。

若工序Og1和Oh1首先完成，則將工序Og2和Oh2加入到調(diào)度任務(wù)池中并進行機床匹配。通過博弈選取最優(yōu)的機床并將按右移重調(diào)度方法將工序插入到調(diào)度計劃中。每當(dāng)有兩個新進訂單的工序加工完成時，則將這兩道工序的下一道工序通過博弈的方法進行分配并插入到調(diào)度計劃中，直到所有新進訂單的工序分配完成。若新進訂單的總工序數(shù)為奇數(shù)時，則最后一道工序不參與博弈，直接通過窮舉法來選擇最優(yōu)的機床。按照上述流程，當(dāng)所有新進訂單的工序都加入到調(diào)度計劃中，則動態(tài)調(diào)度結(jié)束。

本文研究的在緊急加單的柔性車間動態(tài)調(diào)度問題中，由第一階段博弈生成的調(diào)度計劃可看作原調(diào)度的重調(diào)度。而當(dāng)前的重調(diào)度又可以看作是下一次重調(diào)度的預(yù)調(diào)度，同時產(chǎn)生新的重調(diào)度，以此類推。

4 仿真與分析

本文以某制造業(yè)加工車間為例，將生產(chǎn)數(shù)據(jù)進行了簡化，設(shè)計了一個由6個工件，每個工件有3道工序，一共有6臺機器完成加工任務(wù)的仿真實例。具體的任務(wù)信息如表2所示。其中J1～J6表示初始時刻的加工任務(wù)。J7和J8表示在t=12時刻的緊急加單任務(wù)。表中的數(shù)據(jù)(x，y)表示工序在機器上的加工時間為x，準備時間為y。圖4給出了沒有緊急加單情況下的預(yù)調(diào)度甘特圖，采用本文給出的模型及其算法，動態(tài)調(diào)度甘特圖如圖5所示。

在t=12時刻，將J7和J8的第一道工序放入待調(diào)度任務(wù)池中，則可加工 O71的機器集為{M1，M2，M3}，可加工 O81的機器集為{M4，M5，M6}，并使 O71代表系統(tǒng)的快速性指標，O81代表系統(tǒng)的穩(wěn)定性指標。通過博弈的方法將O71和O81分別分配給機器M3和M5，并插入到原有調(diào)度計劃中，此時O43發(fā)生右移。同理，當(dāng)O71和O81完成后，將 O71和 O81放入已完工任務(wù)池，將O72和O82放入待調(diào)度任務(wù)池中進行調(diào)度，并將O72和O82插入到第一階段生成的調(diào)度計劃中，此時O13的開始時間由原來的t=21變?yōu)閠=24。通過上述方法，最終將O73和O83插入第二階段生成的調(diào)度計劃中，得到最終的動態(tài)調(diào)度結(jié)果。

表2 任務(wù)信息

為了說明本文提出方法的有效性，將提出的動態(tài)調(diào)度方法與現(xiàn)存的動態(tài)調(diào)度方法進行比較，例如用Fang［14］等提出的遺傳周期性調(diào)度方法進行重調(diào)度，結(jié)果如圖6所示。雖然Makespan和基于博弈的動態(tài)調(diào)度結(jié)果相同，但是每臺機器的加工序列發(fā)生了變化，因此其使調(diào)度系統(tǒng)的穩(wěn)定性性能下降。故當(dāng)有緊急加單時，和現(xiàn)有的動態(tài)調(diào)度算法相比，本文的方法能夠獲得更優(yōu)化的解。

5 結(jié)語

本文運用博弈的方法解決緊急加單下柔性車間動態(tài)調(diào)度問題，并通過仿真實驗證明了本文提出博弈論在車間動態(tài)調(diào)度中的可行性。目前，對于車間動態(tài)調(diào)度中異常事件處理的研究主要集中在機器故障下的動態(tài)調(diào)度問題，對于緊急加單下的異常事件研究很少。

后續(xù)研究的主要方面有:(1)優(yōu)化模型，添加模型中未考慮的某些因素，如綠色生產(chǎn)中需要考慮的碳排放等。(2)研究多種異常事件同時發(fā)生時的重調(diào)度問題，如緊急加單和機器故障同時發(fā)生等。