賈萬達，彭 艷，石寶東

（1.燕山大學(xué)機械工程學(xué)院；2.國家冷軋板帶裝備及工藝工程技術(shù)研究中心，河北秦皇島 066004）

0 引言

制造業(yè)受成本、技術(shù)創(chuàng)新能力等因素制約，面臨的壓力與日俱增。企業(yè)數(shù)字化、智能化發(fā)展是轉(zhuǎn)型升級的重要方向和路徑。大規(guī)模定制模式因效率高、成本低、支持高度定制化、生產(chǎn)流程靈活等特點，成為產(chǎn)業(yè)熱點［1］。

當(dāng)前生產(chǎn)調(diào)度系統(tǒng)無法適應(yīng)復(fù)雜的動態(tài)調(diào)度需求，因此亟需建立一套可根據(jù)訂單緩急程度隨時改變生產(chǎn)計劃的智慧決策模型。柔性調(diào)度問題是解決生產(chǎn)管理和組合優(yōu)化問題的核心問題［2］，也是建立智慧決策模型的關(guān)鍵。該決策模型主要工作原理是通過優(yōu)化柔性調(diào)度問題中的生產(chǎn)調(diào)度，對工件進行智能排產(chǎn)，從而使管理者能掌控實際生產(chǎn)情況并實現(xiàn)實時調(diào)度，進而提高工作效率。

1 大規(guī)模定制車間生產(chǎn)調(diào)度優(yōu)化算法

針對大規(guī)模定制生產(chǎn)調(diào)度理論優(yōu)化問題，目前主要分為經(jīng)典傳統(tǒng)算法與人工智能調(diào)度算法。

1.1 經(jīng)典傳統(tǒng)算法

經(jīng)典傳統(tǒng)算法的核心是對調(diào)度理論算法進行優(yōu)化，通過分析目標(biāo)函數(shù)約束條件計算得出最優(yōu)生產(chǎn)調(diào)度方案。常用于優(yōu)化調(diào)度理論的方法有線性規(guī)劃法、分支定界法、拉格朗日松弛法和插入法等。傳統(tǒng)算法的優(yōu)勢在于計算方法簡單，無需構(gòu)建復(fù)雜的調(diào)度模型，其局限是只適用于求解小規(guī)模調(diào)度問題，無法解決不確定性大、極小解多等復(fù)雜的實際生產(chǎn)調(diào)度問題。

1.2 人工智能調(diào)度算法

基于人工智能調(diào)度算法的生產(chǎn)調(diào)度理論自20 世紀(jì)80年代逐漸發(fā)展成熟，為解決生產(chǎn)調(diào)度中具有復(fù)雜耦合約束的大規(guī)模組合優(yōu)化問題提供了理論支持。其中以人工神經(jīng)網(wǎng)絡(luò)與智能遺傳算法為特點的全局式統(tǒng)計搜索技術(shù)，因其計算機制獨特引起了國內(nèi)外研究者廣泛關(guān)注。

1.2.1 全局式統(tǒng)計搜索技術(shù)

該技術(shù)經(jīng)典算法是模擬退火算法與禁忌搜索算法。

模擬退火算法于20 世紀(jì)80 年代初［3］，其思想源于金屬材料退火過程，具體實現(xiàn)過程主要由4 部分構(gòu)成：①建立1 個由解空間、目標(biāo)函數(shù)和初始解組成的數(shù)學(xué)模型；②按照具體規(guī)定的機制產(chǎn)生1 個新解，并在滿足Metropolis準(zhǔn)則的基礎(chǔ)上判斷是否接受新解，對有不可行解而限定解空間僅包含可行解時，需判斷解的先行性；③檢查冷卻進度表，使溫度參數(shù)充分大且衰減充分慢；④最后創(chuàng)建1 個偽程序，對滿足要求的模型進行求解。依據(jù)該算法，Kim等［4］解決了帶有獨立調(diào)整時間的調(diào)度問題，從而提出了使所有工件延遲最小的調(diào)度策略；Van 等［5］基于模擬退火算法，描述了一種求解車間最小生產(chǎn)周期問題的近似算法，解決了Job shop 調(diào)度問題。

禁忌搜索算法是全局統(tǒng)計并逐步尋優(yōu)的經(jīng)典算法［6］，通過對局部鄰域的不斷搜索，擴大搜索區(qū)域。該算法常與模擬退火算法結(jié)合，提高搜索精度和計算效率。在生產(chǎn)調(diào)度問題中，Nowicki 等［7］構(gòu)造了一種快速禁忌搜索算法，解決了Job shop 調(diào)度問題；Tucci 等［8］通過構(gòu)造基于領(lǐng)域?qū)＜抑R的禁忌搜索算法，解決了紡織生產(chǎn)過程的調(diào)度問題；Bilge 等［9］通過構(gòu)建多約束的禁忌搜索算法，解決了不同工件交貨期不同、到達時間不同等多目標(biāo)生產(chǎn)調(diào)度問題。

同理，在信息化，全球化發(fā)展的今天，只要制度體制改革到位，就能極大地縮短中國科學(xué)技術(shù)與世界先進水平的差距，極大地縮小產(chǎn)業(yè)發(fā)展與世界先進水平的差距。中國科學(xué)技術(shù)發(fā)展和產(chǎn)業(yè)發(fā)展的歷史已經(jīng)證明了這一點，中國科學(xué)技術(shù)和產(chǎn)業(yè)的進一步發(fā)展更能證明這一點。進行原始創(chuàng)新型人力資本的制度建設(shè)，是關(guān)鍵的一步。

1.2.2 遺傳算法

遺傳算法因具有較好的魯棒性和并行性，易與其它算法結(jié)合，常用于解決實際生產(chǎn)的調(diào)度問題。王春等［10］利用遺傳算法求解柔性作業(yè)調(diào)度問題，取得了很好的效果；劉勝等［11］將該算法與禁忌搜索算法結(jié)合，解決了具有柔性路徑的車間調(diào)度問題。

1.2.3 人工神經(jīng)網(wǎng)絡(luò)

人工神經(jīng)網(wǎng)絡(luò)是一種在對人腦組織結(jié)構(gòu)和運行機制認(rèn)識理解的基礎(chǔ)上，模擬其結(jié)構(gòu)和智能行為的信息處理系統(tǒng)。目前應(yīng)用最廣泛的人工神經(jīng)網(wǎng)絡(luò)模型是基于傳播反向誤差算法的多層反饋人工神經(jīng)網(wǎng)絡(luò)，即反向神經(jīng)網(wǎng)絡(luò)（Back Propagation Network），常用于尋找參數(shù)最優(yōu)值。

人工神經(jīng)網(wǎng)絡(luò)在實際生產(chǎn)調(diào)度中主要有兩方面應(yīng)用：①利用其模擬學(xué)習(xí)及智能計算的能力獲取調(diào)度知識，構(gòu)建智能調(diào)度模型。Min 等［12］為實現(xiàn)自適應(yīng)調(diào)度，采用該算法選擇不同的調(diào)度模型；Park 等［13］為解決生產(chǎn)調(diào)度中并行機器的調(diào)度問題，將該算法與啟發(fā)式算法相結(jié)合，創(chuàng)造出新的并行機器調(diào)度規(guī)則；②將生產(chǎn)調(diào)度問題看成數(shù)學(xué)規(guī)劃問題，利用該算法的統(tǒng)籌優(yōu)化處理能力提高計算效率。Foo等［14］提出Hopfield 人工神經(jīng)網(wǎng)絡(luò)方法，用于解決生產(chǎn)車間的調(diào)度問題，并將生產(chǎn)車間調(diào)度問題視為線性規(guī)劃問題，構(gòu)建了基于線性規(guī)劃與二值調(diào)整算法的整數(shù)規(guī)劃人工神經(jīng)網(wǎng)絡(luò)，成功解決了Hopfield 不能穩(wěn)態(tài)輸出調(diào)度方案的問題。

1.2.4 人工蟻群算法

人工蟻群算法是一種以信息素為傳遞信號的仿生類算法，常用于解決復(fù)雜的組合優(yōu)化問題。劉志虎［15］提出解決柔性車間調(diào)度的改進蟻群算法，提高了車間動態(tài)環(huán)境自適應(yīng)性，實現(xiàn)了動態(tài)環(huán)境下車間柔性調(diào)度。

全局式統(tǒng)計搜索技術(shù)雖能實現(xiàn)智能調(diào)度，但過程復(fù)雜、計算量大，而遺傳算法通常用于解決小規(guī)模調(diào)度問題，因此本文將人工蟻群算法應(yīng)用于建立基于多Agent 技術(shù)的大規(guī)模定制調(diào)度強化學(xué)習(xí)模型，將人工神經(jīng)網(wǎng)絡(luò)算法與人工蟻群算法相結(jié)合提出智能算法協(xié)商策略，實現(xiàn)生產(chǎn)流程智能調(diào)度與排產(chǎn)。

2 基于多Agent技術(shù)的大規(guī)模定制動態(tài)調(diào)度方法

大規(guī)模定制生產(chǎn)系統(tǒng)是一種典型的柔性制造生產(chǎn)系統(tǒng)，在實際生產(chǎn)中不但需滿足客戶對產(chǎn)品的各種定制需求，還要處理設(shè)備損毀、訂單插入等突發(fā)事件。多Agent 技術(shù)是一種具有靈敏性與實時性等優(yōu)點的柔性處理系統(tǒng)，基于該系統(tǒng)建立的分布式處理體系能根據(jù)車間環(huán)境變化動態(tài)調(diào)整調(diào)度方案，增強生產(chǎn)工序自適應(yīng)性。

2.1 基于多Agent 技術(shù)的大規(guī)模定制調(diào)度問題

基于多Agent 技術(shù)的大規(guī)模定制調(diào)度主要實現(xiàn)調(diào)度車間（物理空間）與調(diào)度系統(tǒng)（虛擬空間）的協(xié)調(diào)工作。在某調(diào)度時刻T，調(diào)度系統(tǒng)首先需讀取來自調(diào)度車間的實時數(shù)據(jù)，之后將數(shù)據(jù)狀態(tài)傳遞給多Agent 系統(tǒng)進行分析，最后多Agent 系統(tǒng)將調(diào)度方案再反饋給調(diào)度車間，實現(xiàn)實時調(diào)度。整個調(diào)度決策過程如圖1 所示。

Fig.1 Real time scheduling mechanism of mass customization based on Agent圖1 基于Agent 的大規(guī)模定制實時調(diào)度機制

2.2 基于多Agent 技術(shù)的動態(tài)調(diào)度強化學(xué)習(xí)模型

基于多Agent 技術(shù)的動態(tài)調(diào)度強化學(xué)習(xí)模型基于人工蟻群算法構(gòu)建，該模型在實際車間中主要通過控制Agent、任務(wù)Agent、算法Agent 和調(diào)度Agent 信息互換實現(xiàn)。其中控制Agent 是該學(xué)習(xí)模型核心，負(fù)責(zé)整個生產(chǎn)工序控制、管理和協(xié)調(diào)；任務(wù)Agent 負(fù)責(zé)接受并保證生產(chǎn)任務(wù)正常進行；算法Agent 根據(jù)實際生產(chǎn)任務(wù)選擇智能調(diào)度算法，優(yōu)化調(diào)度任務(wù)；最后調(diào)度Agent 將所有信息進行匯總，通過對未完成任務(wù)的分析，建立相應(yīng)動態(tài)模型，從而選出最佳實施方案，實現(xiàn)實時調(diào)度。動態(tài)調(diào)度強化學(xué)習(xí)模型如圖2 所示。

Fig.2 Dynamic scheduling reinforcement learning model based on multi-agent technology圖2 基于多Agent 技術(shù)的動態(tài)調(diào)度強化學(xué)習(xí)模型

選擇行為準(zhǔn)則是調(diào)度Agent 的核心，即當(dāng)生產(chǎn)任務(wù)處于再加工狀態(tài)時，調(diào)度Agent 參照當(dāng)前任務(wù)資源分配情況為其選擇最優(yōu)加工行為。本文采用輪盤賭算法計算各行為優(yōu)化概率，資源分配多的被選中的可能性更大，反之被選中的可能性越小，可避免計算時算法出現(xiàn)局部循環(huán)。各行為優(yōu)化概率為：

其中，f(am,bm)表示工件處于加工狀態(tài)m時選擇行為的概率；n 表示總行為個數(shù)；tm為選擇行為的獎勵值，獎勵值越大，行為選擇的最優(yōu)化概率越大。tm計算公式為：

2.3 基于人工神經(jīng)網(wǎng)絡(luò)算法與人工蟻群算法的協(xié)商策略

基于人工神經(jīng)網(wǎng)絡(luò)算法與人工蟻群算法的協(xié)商策略可針對生產(chǎn)車間環(huán)境的變化自適應(yīng)調(diào)整，比如當(dāng)車間出現(xiàn)機器故障、訂單插入、訂單改變等突發(fā)情況時，該協(xié)商策略可依據(jù)當(dāng)前訂單獎勵值大小分配相應(yīng)行為，從而實現(xiàn)車間優(yōu)化調(diào)度。協(xié)商策略結(jié)構(gòu)及工作流程如圖3 所示。

Fig.3 The structure and workflow of negotiation strategy圖3 協(xié)商策略結(jié)構(gòu)與工作流程

接受生產(chǎn)任務(wù)后，多Agent 系統(tǒng)將生產(chǎn)信息分配給任務(wù)Agent 和控制Agent，兩部分Agent 讀取和分析信息后將結(jié)果反饋給系統(tǒng)，系統(tǒng)根據(jù)反饋的信息建立加工任務(wù)的機器集。之后根據(jù)加工任務(wù)的獎勵值為生產(chǎn)任務(wù)選擇最優(yōu)加工行為，并啟動算法Agent 模塊完成調(diào)度任務(wù)；模塊根據(jù)調(diào)度結(jié)果完成時間判斷其是否符合生產(chǎn)要求，將符合時間要求的任務(wù)進行局部更新，當(dāng)所有任務(wù)均符合生產(chǎn)要求后再進行全局更新；最后輸出最優(yōu)調(diào)度結(jié)果，并將該結(jié)果與歷史結(jié)果相對比，更新最優(yōu)結(jié)果，取代差的結(jié)果。

綜上所述，基于多Agent 技術(shù)的動態(tài)調(diào)度強化學(xué)習(xí)模型具有應(yīng)對生產(chǎn)任務(wù)突發(fā)狀況的能力，可實現(xiàn)車間動態(tài)調(diào)度過程，還可將本次取得最優(yōu)解的學(xué)習(xí)經(jīng)驗保存下來，指導(dǎo)后續(xù)決策。

2.4 實驗仿真

以某加工車間的動態(tài)調(diào)度問題為仿真實例，用于驗證基于多Agent 技術(shù)的動態(tài)調(diào)度強化學(xué)習(xí)模型有效性與準(zhǔn)確性。該問題包含2 臺生產(chǎn)機器、8 個待加工工件，各有2 道工序。加工信息如表1 所示。

Table 1 Workpiece processing information表1 工件加工信息

經(jīng)過計算，算法在45 代左右基本收斂，最大完工時間為575min。M1、M2 機器甘特圖如圖4 所示。

Fig.4 Gantt chart of M1 and M2 machines with maximum completion time of 779 minutes圖4 最大完工時間為779min 的M1、M2 機器甘特圖

3 結(jié)語

本文研究了大規(guī)模定制下生產(chǎn)組織智慧決策模型，建立智慧決策模型的目的是對生產(chǎn)過程中生產(chǎn)調(diào)度進行柔性化智能處理，從而達到智能排產(chǎn)。針對大規(guī)模生產(chǎn)調(diào)度優(yōu)化建模問題，為適應(yīng)其生產(chǎn)過程多復(fù)雜性、多約束性的特點，在研究人工神經(jīng)網(wǎng)絡(luò)及人工蟻群算法等一系列智能調(diào)度算法的基礎(chǔ)上，提出基于多Agent 技術(shù)的動態(tài)調(diào)度強化學(xué)習(xí)模型。最后通過實驗仿真，驗證了該模型在處理復(fù)雜生產(chǎn)調(diào)度問題時具有較高的準(zhǔn)確率。下一步將繼續(xù)完善多Agent 生產(chǎn)調(diào)度系統(tǒng)理論框架和算法，以更好適應(yīng)未來大規(guī)模產(chǎn)品生產(chǎn)模式。