緊急加單情況下柔性作業車間調度研究

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

(西安航空學院 機械工程學院， 西安 710077)

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

針對車間調度柔性化、動態化的發展趨勢，本文對柔性作業車間動態調度問題進行了研究。首先構建了基于大數據云計算下的柔性作業車間動態調度的體系構架，使初始調度性能在受緊急加單情況的影響下不產生較大的下滑，即維持初始調度的穩定性，同時在此基礎上提高其快速性；其次設計基于博弈論的柔性作業車間動態調度優化方法，給出動態調度實施的具體策略；最后通過MATLAB仿真實驗結果驗證該調度方法，說明了該調度方法能夠很好地解決柔性作業車間動態調度問題。

1 基于大數據云計算下柔性作業車間動態調度體系構架

通過Google提出的Map/Reduce編程模型,其中Reduce作業調度是指:在 Map和 Reduce兩個階段，如何把大量作業有效地分配到相應的計算資源上，最大限度地滿足用戶需求和時間合理分配等要求[7]。將其運用到生產車間中，建立基于大數據云計算下柔性作業車間動態調度體系構架，如圖1所示。

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

基于各個車間的情況(可工作機器與工人)的實時數據，切分成適當的子任務(pieces)，Map Reduce Library啟動復制操作，將用戶信息復制到各個工作車間(a cluster of shops)上，通過云計算(master)過濾子任務，選擇適當的車間(worker)，并將子任務(map任務或者是reduce任務)分配給這些車間進行預覽，信息無誤后車間開始進行子任務。

針對車間調度的動態化、柔性化趨勢，本文提出了基于大數據的云計算下柔性作業車間動態調度的框架。云計算環境下車間用基于博弈論的方法將最優的工序分配到最優的機器上，直到所有的工序分配完成，并得到加工反饋。基于大數據的云計算，利用其有能力提供靈活動態的IT(Information Technology)基礎設施，在生產過程中，當有緊急加單情況出現時，通過事件驅動動態調度策略進行重調度。

2 動態博弈模型

在基于大數據云計算下柔性作業車間動態調度體系構架的基礎上，緊急加單作為一種常見的不確定因素，引起了人們廣泛的研究興趣，為了提高緊急加單情況下工件的生產效率和生產質量，設計一種基于非合作博弈論下的優化方法，目的是優化受影響下工序加工的穩定性和快速性。

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

車間內共有M(M≥2)臺機器。

假設某一時刻：

在零時刻，所有的工件都可被加工；工序一旦進行不能中斷；所有機器在零時刻均處于空閑狀態；所有工件按一定順序加工；每個工件有多道工序；在任何時刻一個工序只能在一臺機器加工；不考慮工件的準備與運輸時間；每臺機器只能加工一道工序。

運行方式：在車間動態調度環境中，使用物聯網控制，通過無線射頻技術可得知每個機器的狀態，并投入所需加工的工件。分配給多個機器處理調整并執行，在工件生產不合格時，會進行加工反饋，啟動子任務的重新分配。

2.1 定義變量

變量定義如表1所示。

表1 變量定義

2.2 定義局中人

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

2.3 策略集

在車間動態調度環境中，通過無線射頻技術可得知每個機器的狀態。本文將可選擇的機器集作為生產的策略，車間可構成一個二人非合作博弈G= (G1，G2)，G1是R的策略集合，G2是S的策略集合，在調度中采用純策略。采用純策略的原因是在混合策略中，參與者是按照某種概率來選擇行動，但是在柔性作業車間調度問題中，讓工件以某一概率去選擇可選機器進行加工仍然具有不確定性，發生重調度時總是希望以一種確定的方式采取行動，所以在調度中每個局中人必須采用純策略。

在這種情況下，可采用多階段博弈。假設在受緊急加單情況下影響的加工工序為N(N≥2)道，將這些工序每兩道為一組分為若干組，當工序為奇數道時，末道單獨成組。每組則可以為參與博弈的雙方各分配一道工序，每個參與者的策略集就是工件可能選擇的加工機器。參與者為自己的工序選擇策略(加工機器)的原則是使各自的性能達到最優，同時Nash均衡目的使二人博弈達到均衡，可構成一個二次博弈矩陣。

2.4 收益函數

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

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

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

如果受緊急加單影響的工序只有兩個，則可以為參與博弈的雙方各分配一個工序，每個參與者的策略集就是工序可能選擇的加工機器集，參與者為自己的工序選擇加工機器的原則是使各自的性能達到最優。在快速性和穩定性的博弈中，Nash 均衡可以使得這兩個指標達到均衡。在本文所討論的問題中，快速性和穩定性越小，對預調度的影響越小，調度性能越好。因此本模型的Nash均衡的定義為：

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

算法步驟：

1) 機器因為預先的工作安排和緊急加單情況下工作時間延長的所受的影響；

2) 為每個操作采取可選擇的機器設備S1和S2，計算兩個集合的基數并用q1和q2表達出來；

3) 依據從S1，S2中獲得的每個策略集，建立q1*q2規模的矩陣結果；

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

6) 輸出結果。

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

當受緊急加單情況下影響的工序大于兩個時，參與者的策略數量將大幅增加，給求解帶來巨大困難，因此本文的模型無法直接運用。故本文將通過多階段博弈來解決空間策略龐大的問題，中心思想是將這些工序每兩道為一組分為若干組，當工序為奇數道時，末道單獨成組。每組則可以為參與博弈的雙方各分配一道工序，然后構造每組的動態博弈模型，稱為博弈的一個階段。如果有n組工序，就有n個階段的博弈。上一階段博弈結果的輸出作為下一階段的博弈的輸入。最終得出純策略Nash均衡解。該算法描述如下：

算法步驟：

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

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

3)i=1；

4) 得出Nash均衡解并更新調度；

5)i=i+1;

6) 如果第i組不是最后一個然后轉到步驟4)；否則轉到步驟7)；

7) 當最后一組只有一個操作，采用窮舉法。當最后一組有兩個操作得出納什均衡解并更新調度；

8) 輸出結果。

如果只有一個工序受到影響時,博弈的兩個參與者不得不選擇相同的策略，因此參與者已經不存在Nash博弈的過程。在此情況下，只能采用窮舉法，即對每一個可選的加工機器加以考察，如果存在1臺機器加工該工序后整個調度的快速性和穩定性比選擇其他機器要小，則該加工機器為最優選。

5 應用算例

一個加工系統有3個工件，4道工序。初始調度加工如表2所示。

表2 初始調度加工時間

預調度算法：緊急加單作為一種常見的未知因素，雖然準確信息通常無法提前得知,但可以根據歷史數據用統計學的方法了解緊急加單發生的概率，所以緊急加單的概率在一定程度上是可以預知的。在緊急加單發生概率已知的情況下可以采取措施來生成預調度。在已有的研究基礎上考慮緊急加單發生的概率和插入緊急加單工件時間生成預調度。

5.1 兩道工序受影響的調度結果

調度方案在執行過程中，遇到緊急加單情況，工件3的第1工序和工件2的第2道工序受到影響，需進行重調度，如表3所示。

表3 初始調度加工表

根據動態博弈模型及Nash 均衡搜索算法得到最終執行方案如圖3、圖4所示。

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

5.2 四道工序受影響的調度結果

調度方案在執行過程中，遇到緊急加單情況，工件2的第1工序，工件1的第2道工序，工件的第3工序和工件2的第4道工序受到影響，需進行重調度，如表4所示。

表4 初始調度加工表

圖5、圖6是對4道工序受緊急加單的調度結果和基于緊急加單概率的預調度算法結果的比較。由圖5可知基于博弈模型的重調度結果的總生產時間為12 min，圖6表示使用基于機器故障概率的預調度算法所需總生產時間為14 min[2]。也就是說，在多道工序受影響的情況下工序經過基于調度模型的重調度，從而利用時間空隙來吸收緊急加單的影響，與預調度算法相比較，基于博弈模型的調度是較好的重調度方法。

6 結論

本文針對柔性作業車間動態調度問題，建立了基于大數據云計算下柔性作業車間動態調度體系構架和策略，并采用博弈論的方法對柔性作業車間動態調度問題進行了建模。為驗證算法的有效性，將上述算法進行MATLAB仿真實驗，通過求解動態調度模型的純策略Nash均衡解，得到了柔性作業車間動態調度的優化結果。結果表明：與其他優化調度方法相比，本文算法在解決柔性作業車間緊急加單情況下動態調度問題時，具有穩定性強，速度快，效率高等優點。

：

[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] 何偉.機器故障下柔性Job Shop調度研究[D].重慶：重慶大學,2012.

[3] 楊武，崔英志，胡爽.基于連續多媒體的磁盤調度[J].四川兵工學報，2010,31(7)：85.

[4] 余琦瑋,蔣海青.柔性作業車間動態調度問題研究[J].科技與企業,2013(19):36-37.

[5] 楊琴,周國華,林晶晶,等.基于DBR理論的柔性流水車間動態調度[J].控制與決策,2011,26(7):1109-1112.

[6] 李開紅,肖輝，李橫，等.基于匈牙利算法的戰時運油車前送油料調度優化模型研究[J].四川兵工學報，2015(6):61-65.

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