緊急加單情況下柔性作業(yè)車(chē)間調(diào)度研究

王 晉,郭豐赫,汪 鼎,翟鵬飛

(西安航空學(xué)院 機(jī)械工程學(xué)院， 西安 710077)

隨著經(jīng)濟(jì)和信息技術(shù)的快速發(fā)展，制造企業(yè)為了改善生產(chǎn)效率、提高自身的競(jìng)爭(zhēng)力，使得信息的共享與資源合理化分配運(yùn)用越來(lái)越廣泛，企業(yè)也越來(lái)越關(guān)注對(duì)車(chē)間中復(fù)雜多變的生產(chǎn)活動(dòng)進(jìn)行高效調(diào)度[1]。車(chē)間在生產(chǎn)過(guò)程中，會(huì)面臨各種各樣的緊急情況，如機(jī)器故障、來(lái)料延遲、緊急加單等[2]，若仍采取傳統(tǒng)的預(yù)調(diào)度處理方法，無(wú)法精確、高效地處理緊急情況，難以保證生產(chǎn)效率。車(chē)間生產(chǎn)調(diào)度問(wèn)題是制造領(lǐng)域研究的基礎(chǔ)問(wèn)題[3]，其主要任務(wù)是在有限的制造資源條件下，確定工件在機(jī)器上的加工順序和加工時(shí)間，以?xún)?yōu)化特定的目標(biāo)。而柔性作業(yè)車(chē)間調(diào)度問(wèn)題突破了機(jī)器和工藝路線的約束[4]，相比傳統(tǒng)的流水作業(yè)車(chē)間調(diào)度更接近實(shí)際生產(chǎn)[5]。在實(shí)際的生產(chǎn)過(guò)程中，出現(xiàn)緊急情況概率較大[6]，本文主要以最普遍的緊急加單情況下的柔性作業(yè)車(chē)間調(diào)度問(wèn)題進(jìn)行研究。

針對(duì)車(chē)間調(diào)度柔性化、動(dòng)態(tài)化的發(fā)展趨勢(shì)，本文對(duì)柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題進(jìn)行了研究。首先構(gòu)建了基于大數(shù)據(jù)云計(jì)算下的柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度的體系構(gòu)架，使初始調(diào)度性能在受緊急加單情況的影響下不產(chǎn)生較大的下滑，即維持初始調(diào)度的穩(wěn)定性，同時(shí)在此基礎(chǔ)上提高其快速性；其次設(shè)計(jì)基于博弈論的柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度優(yōu)化方法，給出動(dòng)態(tài)調(diào)度實(shí)施的具體策略；最后通過(guò)MATLAB仿真實(shí)驗(yàn)結(jié)果驗(yàn)證該調(diào)度方法，說(shuō)明了該調(diào)度方法能夠很好地解決柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題。

1 基于大數(shù)據(jù)云計(jì)算下柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度體系構(gòu)架

通過(guò)Google提出的Map/Reduce編程模型,其中Reduce作業(yè)調(diào)度是指:在 Map和 Reduce兩個(gè)階段，如何把大量作業(yè)有效地分配到相應(yīng)的計(jì)算資源上，最大限度地滿足用戶(hù)需求和時(shí)間合理分配等要求[7]。將其運(yùn)用到生產(chǎn)車(chē)間中，建立基于大數(shù)據(jù)云計(jì)算下柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度體系構(gòu)架，如圖1所示。

在體系構(gòu)架中，先將總訂單上傳，通過(guò)感知系統(tǒng)，得知總訂單及所有車(chē)間生產(chǎn)信息，并上傳至云平臺(tái)，構(gòu)建柔性車(chē)間信息數(shù)據(jù)倉(cāng)庫(kù)(如Teradata AsterData、 EMC GreenPlum、 HP Vertica 等)，同時(shí)針對(duì)單個(gè)車(chē)間建立數(shù)據(jù)集市(如QlikView、 Tableau 、Style Intelligence等)，通過(guò)前端展現(xiàn)工具(如BDP、大數(shù)據(jù)魔鏡、FineBI等)分級(jí)分析、處理數(shù)據(jù)以預(yù)測(cè)工件準(zhǔn)備和運(yùn)輸時(shí)間、各個(gè)車(chē)間的生產(chǎn)能力(可工作機(jī)器與工人數(shù)量等)，并通過(guò)云計(jì)算根據(jù)預(yù)測(cè)結(jié)果將總訂單分割分配到各個(gè)車(chē)間。車(chē)間對(duì)于這些緊急加單，以基于博弈論的柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度優(yōu)化模型對(duì)其進(jìn)行重調(diào)度，進(jìn)而達(dá)到優(yōu)化柔性作業(yè)車(chē)間生產(chǎn)的目的。利用大數(shù)據(jù)下云計(jì)算可達(dá)到實(shí)時(shí)獲得生產(chǎn)任務(wù)信息的效果，其中車(chē)間生產(chǎn)數(shù)據(jù)云計(jì)算和生產(chǎn)任務(wù)關(guān)系，如圖2所示。

基于各個(gè)車(chē)間的情況(可工作機(jī)器與工人)的實(shí)時(shí)數(shù)據(jù)，切分成適當(dāng)?shù)淖尤蝿?wù)(pieces)，Map Reduce Library啟動(dòng)復(fù)制操作，將用戶(hù)信息復(fù)制到各個(gè)工作車(chē)間(a cluster of shops)上，通過(guò)云計(jì)算(master)過(guò)濾子任務(wù)，選擇適當(dāng)?shù)能?chē)間(worker)，并將子任務(wù)(map任務(wù)或者是reduce任務(wù))分配給這些車(chē)間進(jìn)行預(yù)覽，信息無(wú)誤后車(chē)間開(kāi)始進(jìn)行子任務(wù)。

針對(duì)車(chē)間調(diào)度的動(dòng)態(tài)化、柔性化趨勢(shì)，本文提出了基于大數(shù)據(jù)的云計(jì)算下柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度的框架。云計(jì)算環(huán)境下車(chē)間用基于博弈論的方法將最優(yōu)的工序分配到最優(yōu)的機(jī)器上，直到所有的工序分配完成，并得到加工反饋?；诖髷?shù)據(jù)的云計(jì)算，利用其有能力提供靈活動(dòng)態(tài)的IT(Information Technology)基礎(chǔ)設(shè)施，在生產(chǎn)過(guò)程中，當(dāng)有緊急加單情況出現(xiàn)時(shí)，通過(guò)事件驅(qū)動(dòng)動(dòng)態(tài)調(diào)度策略進(jìn)行重調(diào)度。

2 動(dòng)態(tài)博弈模型

在基于大數(shù)據(jù)云計(jì)算下柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度體系構(gòu)架的基礎(chǔ)上，緊急加單作為一種常見(jiàn)的不確定因素，引起了人們廣泛的研究興趣，為了提高緊急加單情況下工件的生產(chǎn)效率和生產(chǎn)質(zhì)量，設(shè)計(jì)一種基于非合作博弈論下的優(yōu)化方法，目的是優(yōu)化受影響下工序加工的穩(wěn)定性和快速性。

博弈三要素:收益I(局中人)；G(策略) ；目標(biāo)U(收益)；

車(chē)間內(nèi)共有M(M≥2)臺(tái)機(jī)器。

假設(shè)某一時(shí)刻：

在零時(shí)刻，所有的工件都可被加工；工序一旦進(jìn)行不能中斷；所有機(jī)器在零時(shí)刻均處于空閑狀態(tài)；所有工件按一定順序加工；每個(gè)工件有多道工序；在任何時(shí)刻一個(gè)工序只能在一臺(tái)機(jī)器加工；不考慮工件的準(zhǔn)備與運(yùn)輸時(shí)間；每臺(tái)機(jī)器只能加工一道工序。

運(yùn)行方式：在車(chē)間動(dòng)態(tài)調(diào)度環(huán)境中，使用物聯(lián)網(wǎng)控制，通過(guò)無(wú)線射頻技術(shù)可得知每個(gè)機(jī)器的狀態(tài)，并投入所需加工的工件。分配給多個(gè)機(jī)器處理調(diào)整并執(zhí)行，在工件生產(chǎn)不合格時(shí)，會(huì)進(jìn)行加工反饋，啟動(dòng)子任務(wù)的重新分配。

2.1 定義變量

變量定義如表1所示。

表1 變量定義

2.2 定義局中人

I是局中人集合。就基于緊急加單的車(chē)間作業(yè)調(diào)度問(wèn)題而言,選擇穩(wěn)定性與快速性作為非合作動(dòng)態(tài)博弈中的參與者，應(yīng)滿足緊急加單情況下穩(wěn)定性與快速性獨(dú)立做出決策并且兩者互不干擾的原則。構(gòu)成二人非合作博弈模型。I=(R，S)，R為穩(wěn)定性，S為快速性，他們都是博弈的參與者。

2.3 策略集

在車(chē)間動(dòng)態(tài)調(diào)度環(huán)境中，通過(guò)無(wú)線射頻技術(shù)可得知每個(gè)機(jī)器的狀態(tài)。本文將可選擇的機(jī)器集作為生產(chǎn)的策略，車(chē)間可構(gòu)成一個(gè)二人非合作博弈G= (G1，G2)，G1是R的策略集合，G2是S的策略集合，在調(diào)度中采用純策略。采用純策略的原因是在混合策略中，參與者是按照某種概率來(lái)選擇行動(dòng)，但是在柔性作業(yè)車(chē)間調(diào)度問(wèn)題中，讓工件以某一概率去選擇可選機(jī)器進(jìn)行加工仍然具有不確定性，發(fā)生重調(diào)度時(shí)總是希望以一種確定的方式采取行動(dòng)，所以在調(diào)度中每個(gè)局中人必須采用純策略。

在這種情況下，可采用多階段博弈。假設(shè)在受緊急加單情況下影響的加工工序?yàn)镹(N≥2)道，將這些工序每?jī)傻罏橐唤M分為若干組，當(dāng)工序?yàn)槠鏀?shù)道時(shí)，末道單獨(dú)成組。每組則可以為參與博弈的雙方各分配一道工序，每個(gè)參與者的策略集就是工件可能選擇的加工機(jī)器。參與者為自己的工序選擇策略(加工機(jī)器)的原則是使各自的性能達(dá)到最優(yōu)，同時(shí)Nash均衡目的使二人博弈達(dá)到均衡，可構(gòu)成一個(gè)二次博弈矩陣。

2.4 收益函數(shù)

調(diào)度目標(biāo)是在緊急加單情況下使穩(wěn)定性與快速性達(dá)到Nash均衡點(diǎn)，實(shí)現(xiàn)生產(chǎn)最優(yōu)化。在該模型中，快速性作為R的利益函數(shù)，穩(wěn)定性作為S的利益函數(shù)，并令U作為參與者的利益函數(shù)集合。由于該模型是雙人博弈模型，故參與者的利益可以寫(xiě)成q1*q2的效益矩陣。該矩陣的列作為R的策略，行作為S的策略。在這里，策略指的是工件所選擇的加工機(jī)器(當(dāng)受影響的工件≥2成立)。

效益矩陣q1*q2表示如下：

3 兩道原有工序受影響下的Nash均衡求解

如果受緊急加單影響的工序只有兩個(gè)，則可以為參與博弈的雙方各分配一個(gè)工序，每個(gè)參與者的策略集就是工序可能選擇的加工機(jī)器集，參與者為自己的工序選擇加工機(jī)器的原則是使各自的性能達(dá)到最優(yōu)。在快速性和穩(wěn)定性的博弈中，Nash 均衡可以使得這兩個(gè)指標(biāo)達(dá)到均衡。在本文所討論的問(wèn)題中，快速性和穩(wěn)定性越小，對(duì)預(yù)調(diào)度的影響越小，調(diào)度性能越好。因此本模型的Nash均衡的定義為：

本文給出了Nash均衡的存在條件，但博弈論中亟待解決的問(wèn)題是在離散條件下如何尋找Nash均衡，且大部分方法都是尋找混合策略的Nash均衡解，對(duì)生產(chǎn)有一定的不確定性影響。因此本文針對(duì)二人博弈的特點(diǎn)，提出基于利益矩陣的Nash均衡搜索算法，尋找純策略Nash均衡解。該算法描述如下所示：

算法步驟：

1) 機(jī)器因?yàn)轭A(yù)先的工作安排和緊急加單情況下工作時(shí)間延長(zhǎng)的所受的影響；

2) 為每個(gè)操作采取可選擇的機(jī)器設(shè)備S1和S2，計(jì)算兩個(gè)集合的基數(shù)并用q1和q2表達(dá)出來(lái)；

3) 依據(jù)從S1，S2中獲得的每個(gè)策略集，建立q1*q2規(guī)模的矩陣結(jié)果；

5) 記錄納什均衡解決方案。最后i=i+1；

6) 輸出結(jié)果。

4 多道原有工序受影響下的Nash均衡求解

當(dāng)受緊急加單情況下影響的工序大于兩個(gè)時(shí)，參與者的策略數(shù)量將大幅增加，給求解帶來(lái)巨大困難，因此本文的模型無(wú)法直接運(yùn)用。故本文將通過(guò)多階段博弈來(lái)解決空間策略龐大的問(wèn)題，中心思想是將這些工序每?jī)傻罏橐唤M分為若干組，當(dāng)工序?yàn)槠鏀?shù)道時(shí)，末道單獨(dú)成組。每組則可以為參與博弈的雙方各分配一道工序，然后構(gòu)造每組的動(dòng)態(tài)博弈模型，稱(chēng)為博弈的一個(gè)階段。如果有n組工序，就有n個(gè)階段的博弈。上一階段博弈結(jié)果的輸出作為下一階段的博弈的輸入。最終得出純策略Nash均衡解。該算法描述如下：

算法步驟：

1) 確定受緊急加單影響下的工件；

2) 將操作劃分為n(n=(N/2))組，其中每組包含兩個(gè)操作，除了最后一個(gè)組包含一個(gè)或兩個(gè)操作(N為受影響的工件)；

3)i=1；

4) 得出Nash均衡解并更新調(diào)度；

5)i=i+1;

6) 如果第i組不是最后一個(gè)然后轉(zhuǎn)到步驟4)；否則轉(zhuǎn)到步驟7)；

7) 當(dāng)最后一組只有一個(gè)操作，采用窮舉法。當(dāng)最后一組有兩個(gè)操作得出納什均衡解并更新調(diào)度；

8) 輸出結(jié)果。

如果只有一個(gè)工序受到影響時(shí),博弈的兩個(gè)參與者不得不選擇相同的策略，因此參與者已經(jīng)不存在Nash博弈的過(guò)程。在此情況下，只能采用窮舉法，即對(duì)每一個(gè)可選的加工機(jī)器加以考察，如果存在1臺(tái)機(jī)器加工該工序后整個(gè)調(diào)度的快速性和穩(wěn)定性比選擇其他機(jī)器要小，則該加工機(jī)器為最優(yōu)選。

5 應(yīng)用算例

一個(gè)加工系統(tǒng)有3個(gè)工件，4道工序。初始調(diào)度加工如表2所示。

表2 初始調(diào)度加工時(shí)間

預(yù)調(diào)度算法：緊急加單作為一種常見(jiàn)的未知因素，雖然準(zhǔn)確信息通常無(wú)法提前得知,但可以根據(jù)歷史數(shù)據(jù)用統(tǒng)計(jì)學(xué)的方法了解緊急加單發(fā)生的概率，所以緊急加單的概率在一定程度上是可以預(yù)知的。在緊急加單發(fā)生概率已知的情況下可以采取措施來(lái)生成預(yù)調(diào)度。在已有的研究基礎(chǔ)上考慮緊急加單發(fā)生的概率和插入緊急加單工件時(shí)間生成預(yù)調(diào)度。

5.1 兩道工序受影響的調(diào)度結(jié)果

調(diào)度方案在執(zhí)行過(guò)程中，遇到緊急加單情況，工件3的第1工序和工件2的第2道工序受到影響，需進(jìn)行重調(diào)度，如表3所示。

表3 初始調(diào)度加工表

根據(jù)動(dòng)態(tài)博弈模型及Nash 均衡搜索算法得到最終執(zhí)行方案如圖3、圖4所示。

圖3、圖4是對(duì)2道工序受緊急加單下的調(diào)度結(jié)果和基于緊急加單概率的預(yù)調(diào)度算法結(jié)果。由圖3可知基于博弈模型的重調(diào)度結(jié)果的總生產(chǎn)時(shí)間為10 min，圖4表示使用基于機(jī)器故障概率的預(yù)調(diào)度算法所需總生產(chǎn)時(shí)間為14 min[2]。也就是說(shuō)，在只有兩道工序受影響的情況下工序間存在足夠的時(shí)間空隙吸收緊急加單情況的影響，因而基于博弈模型的調(diào)度是較好的重調(diào)度方法。

5.2 四道工序受影響的調(diào)度結(jié)果

調(diào)度方案在執(zhí)行過(guò)程中，遇到緊急加單情況，工件2的第1工序，工件1的第2道工序，工件的第3工序和工件2的第4道工序受到影響，需進(jìn)行重調(diào)度，如表4所示。

表4 初始調(diào)度加工表

圖5、圖6是對(duì)4道工序受緊急加單的調(diào)度結(jié)果和基于緊急加單概率的預(yù)調(diào)度算法結(jié)果的比較。由圖5可知基于博弈模型的重調(diào)度結(jié)果的總生產(chǎn)時(shí)間為12 min，圖6表示使用基于機(jī)器故障概率的預(yù)調(diào)度算法所需總生產(chǎn)時(shí)間為14 min[2]。也就是說(shuō)，在多道工序受影響的情況下工序經(jīng)過(guò)基于調(diào)度模型的重調(diào)度，從而利用時(shí)間空隙來(lái)吸收緊急加單的影響，與預(yù)調(diào)度算法相比較，基于博弈模型的調(diào)度是較好的重調(diào)度方法。

6 結(jié)論

本文針對(duì)柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題，建立了基于大數(shù)據(jù)云計(jì)算下柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度體系構(gòu)架和策略，并采用博弈論的方法對(duì)柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題進(jìn)行了建模。為驗(yàn)證算法的有效性，將上述算法進(jìn)行MATLAB仿真實(shí)驗(yàn)，通過(guò)求解動(dòng)態(tài)調(diào)度模型的純策略Nash均衡解，得到了柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度的優(yōu)化結(jié)果。結(jié)果表明：與其他優(yōu)化調(diào)度方法相比，本文算法在解決柔性作業(yè)車(chē)間緊急加單情況下動(dòng)態(tài)調(diào)度問(wèn)題時(shí)，具有穩(wěn)定性強(qiáng)，速度快，效率高等優(yōu)點(diǎn)。

：

[1] ZHANG Y,WANG J,LIU S,et al.Game theory based real-time shop floor scheduling strategy and method for cloud manufacturing[J].International Journal of Intelligent Systems,2016(10)：71-74.

[2] 何偉.機(jī)器故障下柔性Job Shop調(diào)度研究[D].重慶：重慶大學(xué),2012.

[3] 楊武，崔英志，胡爽.基于連續(xù)多媒體的磁盤(pán)調(diào)度[J].四川兵工學(xué)報(bào)，2010,31(7)：85.

[4] 余琦瑋,蔣海青.柔性作業(yè)車(chē)間動(dòng)態(tài)調(diào)度問(wèn)題研究[J].科技與企業(yè),2013(19):36-37.

[5] 楊琴,周?chē)?guó)華,林晶晶,等.基于DBR理論的柔性流水車(chē)間動(dòng)態(tài)調(diào)度[J].控制與決策,2011,26(7):1109-1112.

[6] 李開(kāi)紅,肖輝，李橫，等.基于匈牙利算法的戰(zhàn)時(shí)運(yùn)油車(chē)前送油料調(diào)度優(yōu)化模型研究[J].四川兵工學(xué)報(bào)，2015(6):61-65.

[7] 梁靜,許波,葛宇.基于改進(jìn)蛙跳策略的Map-Reduce作業(yè)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用研究,2013,30(7):1999-2002.