王 晉 彭琰舉 羅庚合

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

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

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

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

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

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

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

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

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

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

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

(1)每臺(tái)機(jī)器在任何時(shí)刻最多加工一道工序。

(2)每道工序在一個(gè)時(shí)刻只能在一臺(tái)機(jī)器上加工。

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

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

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

表1 符號(hào)和變量定義

2.1 博弈模型建立

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

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

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

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

2.2 求解博弈模型

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

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

以上兩個(gè)矩陣，也可記為:

算法總體思想:

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

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

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

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

因?yàn)樵诖瞬┺哪Ｐ拖拢瑹o法保證純策略Nash均衡點(diǎn)的個(gè)數(shù):可能沒有純策略Nash均衡點(diǎn)或者存在多個(gè)Nash均衡點(diǎn)，故局中人無法知道采取何種行動(dòng)。為了克服純策略所帶來的缺陷，本文提出了近似Nash均衡解的概念。近似合作Nash均衡解的概念如下:

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

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

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

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

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

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

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

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

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

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

3.2 再調(diào)度策略

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

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

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

4 仿真與分析

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

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

表2 任務(wù)信息

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

5 結(jié)語

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

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