涂晶鑫

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

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.

關(guān)鍵詞：分布式車間調(diào)度；MAS；agent；拍賣機制

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

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

0 引言

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

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

1 MAS的結(jié)構(gòu)特點與調(diào)度系統(tǒng)框架

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

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

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

2 基于MAS的單機調(diào)度問題問題描述與模型建立

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

則需要滿足如下假設(shè)：

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

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

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

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

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

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

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

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

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

3.1 確定模型的迭代方向

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

3.2 確定模型的迭代步長

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

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

3.3 確定模型的收斂條件

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

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

4 實例驗證

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

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

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

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

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

5 結(jié)果分析

從以上的結(jié)果中可以看出來，基于MAS的分布式調(diào)度有能力去更好的解決這些調(diào)度問題，在求解質(zhì)量上要比這些常用規(guī)則的結(jié)果要高出27%。該實驗可以說明了基于MAS的分布式調(diào)度有一定的可行性。但是目前僅僅只做到了基本的單機調(diào)度問題，所以在后續(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]喻明讓，張英杰，陳琨.考慮調(diào)整時間的作業(yè)車間調(diào)度與預(yù)防性維修集成方法[J].西安交通大學學報，2015，49（6）：16-21.

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

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