涂晶鑫

摘要：在當今的制造環(huán)境下，大多數(shù)企業(yè)多為分布式制造，所以在研究分布式車間調度已然當今調度領域的熱點。本文擬通過研究單機調度的情況，引入分布式調度的核心——MAS（Multi-agent system）。面向任務建立了基于MAS的調度控制系統(tǒng)模型。采用分布式調度將整個車間的調度問題分解成一系列的子調度問題，并將這一系列的子調度問題集成到拍賣機制中，滿足了現(xiàn)代制造系統(tǒng)對復雜性的要求。最后以經典的調度問題驗證了此方法的有效性。

Abstract： In today's manufacturing environment， most enterprises are distributed manufacturing， so the study of Distributed Shop scheduling has become a hot spot in the field of scheduling. This paper introduces the core ——MAS （Multi-agent system） of distributed scheduling by studying the single machine scheduling. A scheduling control system model based on MAS is established for tasks. The scheduling problem of the whole workshop is decomposed into a series of sub scheduling problems by distributed scheduling， and this series of sub scheduling problems are integrated into the auction mechanism to meet the requirements of the complexity of the modern manufacturing system. Finally， the effectiveness of this method is verified by the classical scheduling problem.

關鍵詞：分布式車間調度；MAS；agent；拍賣機制

Key words： distributed job shop scheduling；MAS；agent；auction mechanism

中圖分類號：TH164 文獻標識碼：A 文章編號：1006-4311（2018）33-0274-03

0 引言

在復雜、多變的生產制造環(huán)境中，生產擾動的隨機性往往會影響車間生產的正常運行，生產調度人員需結合實時工況有針對性地制定解決方案，因此如何快速智能的解決生產擾動事件、恢復生產系統(tǒng)穩(wěn)定性是車間智能調度問題的研究重點。目前，關于智能調度系統(tǒng)的研究，國內外學者進行了大量的研究，SNOO[1]和MIKKEL[2]等人通過建立不確定性因素的可靠性評價模型來評估擾動事件的影響程度，并根據評估結果結合調度閾值來確定重調度方法，但這種方法依賴于人的主觀性，會導致評估結果的不準確；何偉[3]和喻明讓[4]等人考慮設置調整時間，依據擾動事件發(fā)生的概率分布，實現(xiàn)車間調度與預防性維修的集成來達到預防目的，但是這樣會造成前期成本投入高以及工件加工時間增加等問題；劉愛軍[5]和李平[6]等人基于事件和周期驅動的混合調度策略，建立了自適應重調度框架，雖然這些方法得到的結果能夠為實時解決智能調度問題提供一定的參考，達到智能響應擾動的目的，但仍存在以下不足：

①生產擾動事件具有很強的隨機性和動態(tài)性，不斷變化的動態(tài)生產環(huán)境，給調度人員在生產調度模型修訂時帶來極大困難，有時甚至不可能；而且模型過于簡單、方法過于單一、適用范圍狹窄。②隨著求解問題的規(guī)模變大，尋求最優(yōu)解的計算量呈指數(shù)增長，使得一些常規(guī)優(yōu)化方法難以湊效，求解效率不高，陷入局部最優(yōu)的問題。為了解決上述問題，提出了MAS（Multi-agent system）。它的基本思想是把大的復雜系統(tǒng)轉化成小的、可以實現(xiàn)相互通信的、能夠彼此協(xié)調工作的自治系統(tǒng)，逐漸的把生產調度系統(tǒng)由傳統(tǒng)的集中式轉化為分布式，以便于解決生產調度管理系統(tǒng)具有開放性，分布性。

1 MAS的結構特點與調度系統(tǒng)框架

1.1 單一agent的結構特點 圖1所示的為單一agent的結構示意圖，每一個agent都包括了知識庫，推理決策工具和通訊功能模塊。單一的agent有如下的特點：①盡可能使局部獲得最大的利益，可以不考慮整體的目標。②單一agent可以使用通訊功能模塊與其他的agent進行溝通。

1.2 0MAS的結構特點 雖然單一agent的功能定義具有特定的功能，可以很好地嵌入到調度系統(tǒng)中去，但是在現(xiàn)在中復雜的問題，只靠單個的agent是無法解決的，甚至是無法描述。如圖2所示，為了很好地利用agent的特定的功能，因此，一個應用系統(tǒng)中往往包含了多個單一的agent，這些單一的agent不僅僅具有自己可以解決問題的能力，還可以通過相互協(xié)調通信，從局部最優(yōu)達到最優(yōu)，完成共同的目標。這樣的系統(tǒng)稱之為MAS（Multi-agent System）。

1.3 MAS的調度系統(tǒng)框架 如圖3所示，MAS的調度系統(tǒng)一般由三個agent組成，分別為車間調度agent，任務agent和車間資源agent。當有擾動發(fā)生時，任務agent便會收到任務，與其他兩個agent進行交互和合作，共同完成調度任務，最后輸出調度結果。

2 基于MAS的單機調度問題問題描述與模型建立

本文采用0-1整數(shù)規(guī)劃進行建模，傳統(tǒng)的單機調度模型通過0-1整數(shù)規(guī)劃構建是一個典型的集中式的模型，那么基于MAS的單機調度模型構建應該是一個分布式模型，把工件agent分開代表每一個工件。

則需要滿足如下假設：

①工件的優(yōu)先級相同。

②在t=0時刻所有的工件都可以被加工。

③忽略在加工過程中的擾動因素，加工一旦開始無法中斷。

由以上可以數(shù)學模型可以看著這是一個典型的0-1整數(shù)規(guī)劃模型。為了把MAS的模型引入其中，則本文將原先的集中式的建模進行分解為多個單一的agent，即每個工件和機器分別代表工件agent和機器agent。在分解數(shù)學模型下，我們必須要保障分解之后的數(shù)學模型必須要有意義，因為單一agent結構要求必須將交織的數(shù)據和約束關系分解到各個獨立的agent中，而單一的agent又必須具有一定的交互能力，這樣才有可能達到全局最優(yōu)。

故本文采用拉格朗日松弛法去分解0-1整數(shù)規(guī)劃模型：

每一個工件都有獨立的數(shù)學模型。

針對單機作業(yè)問題的機器agent，？姿k作為違反機器能力約束的懲罰項并不是一個常數(shù)，反而？姿k的值是由每個工件的完工時間確定的，有兩個及兩個以上的工件需要同一段時間進行加工時，？姿k的值就會變大。為了得到可行的調度方案，需要最大化懲罰項來約束機器的能力。那么機器agent的目標函數(shù)表示為：

在這里，就已經完成了對集中式的數(shù)學模型進行了分解，得到了每個工件agent和機器agent的0-1數(shù)學規(guī)劃模型。

3 數(shù)學模型的解答流程

3.1 確定模型的迭代方向

在不斷的迭代的過程中，每迭代一次都在向最優(yōu)解不斷的靠近，則迭代的方向選擇正確那么可以大大的加快收斂速度，本文采用的是常見的最速下降法，則它的搜索方向為負梯度方向。由推論可得：

3.2 確定模型的迭代步長

步長設計只要滿足他提出的設計要求，基本是可以滿足求解的收斂性，在實際中常用的步長計算公式為：

在上述公式中，Zup（t）是原問題的一個上界。Zlb（t）是原問題的下界。βc的取值一般為：0≤βc≤2。一般在初始化時，取β0=2。當M（？姿）的值上升時，βc不變。為了計算簡單，在文中把原問題的上下界用前后兩次的迭代值代替。

3.3 確定模型的收斂條件

在確定了迭代方向和迭代步長之后，需要確定迭代停止的條件，也就是收斂條件，在實際運算中，設定迭代的停止條件為：當?shù)^程中，前后兩次迭代的差小于一個極小的常數(shù)，則認為M（？姿）已經收斂，迭代結束。

其中，μ是一個極小的常數(shù)。

4 實例驗證

整個調度時域是20個時間單位。所有的工件在時刻0時都可以開始加工。目標函數(shù)為完工成本最小。假設每個工件的完工成本是由加工成本還有提前和拖期完工的懲罰組成。（為了方便計算，則每個工件在機器上加工的成本一般是固定的，故完工成本只由加工成本進行衡量）每個工件的參數(shù)如表1所示。

計算第一輪出價，在機器沒有開始任何加工任務時，所以機器把1-20個時刻都作為拍賣品發(fā)起拍賣。在開始拍賣時，每個工件agent為了自己的完工成本最低，故此次在第一個時刻，懲罰值為0，經過求解，出價表如表2所示：圖4為3個工件出價的甘特圖。

從甘特圖中可以看到，這三個工件的加工需求時間有重疊，則在這段時間內，工件agent的模型得到的出價違反了機器能力約束，在機器在下次拍賣的迭代過程中會提高發(fā)生沖突時間段的機器價格，以便于消除沖突。

在后續(xù)的迭代中，在經歷的c=68時，目標函數(shù)收斂，形成了良好的調度方案，用圖5表示在68次出價之后的甘特圖；得到出價表如表3。

為了驗證基于MAS的調度算法的求解質量，讓本文的求解結果與一些常用的調度規(guī)則在次問題的結果上做一些對比。

5 結果分析

從以上的結果中可以看出來，基于MAS的分布式調度有能力去更好的解決這些調度問題，在求解質量上要比這些常用規(guī)則的結果要高出27%。該實驗可以說明了基于MAS的分布式調度有一定的可行性。但是目前僅僅只做到了基本的單機調度問題，所以在后續(xù)的研究中，會逐漸把車間的復雜程度加大，進行更為復雜的研究。

參考文獻：

[1]SNOO C DE， WEZEL W V， WORTMANN J C， et al. Coordination activities of human planners during rescheduling： case analysis and event handling procedure[J]. International Journal of Production Research， 2011， 49（7）： 2101-2122.

[2]MIKKEL T， JENSEN. Robust and flexible scheduling with evolutionary computation[D]. PhD Dissertation， Department of Computer Science University of Aarhus， 2001， Denmark.

[3]He W， Sun D H. Scheduling flexible job shop problem subject to machine breakdown with route changing and right-shift strategies[J]. International Journal of Advanced Manufacturing Technology， 2013， 66（1-4）：501-514.

[4]喻明讓，張英杰，陳琨.考慮調整時間的作業(yè)車間調度與預防性維修集成方法[J].西安交通大學學報，2015，49（6）：16-21.

[5]劉愛軍，楊育，邢青松，陸惠，張煜東，周振宇，吳光輝，趙小華.柔性作業(yè)車間多目標動態(tài)調度[J].計算機集成制造系統(tǒng)，2011，17（12）：2629-2637.

[6]李平，唐秋華，夏緒輝，陳平和.基于雙層遺傳編碼的柔性作業(yè)車間自適應重調度研究[J].中國機械工程，2013，24（16）：2195-2201.