大規(guī)模定制下生產(chǎn)組織智慧決策模型研究

賈萬(wàn)達(dá)，彭 艷，石寶東

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2.2 遺傳算法

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

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

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

1.2.4 人工蟻群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

基于人工神經(jīng)網(wǎng)絡(luò)算法與人工蟻群算法的協(xié)商策略可針對(duì)生產(chǎn)車間環(huán)境的變化自適應(yīng)調(diào)整，比如當(dāng)車間出現(xiàn)機(jī)器故障、訂單插入、訂單改變等突發(fā)情況時(shí)，該協(xié)商策略可依據(jù)當(dāng)前訂單獎(jiǎng)勵(lì)值大小分配相應(yīng)行為，從而實(shí)現(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ī)器集。之后根據(jù)加工任務(wù)的獎(jiǎng)勵(lì)值為生產(chǎn)任務(wù)選擇最優(yōu)加工行為，并啟動(dòng)算法Agent 模塊完成調(diào)度任務(wù)；模塊根據(jù)調(diào)度結(jié)果完成時(shí)間判斷其是否符合生產(chǎn)要求，將符合時(shí)間要求的任務(wù)進(jìn)行局部更新，當(dāng)所有任務(wù)均符合生產(chǎn)要求后再進(jìn)行全局更新；最后輸出最優(yōu)調(diào)度結(jié)果，并將該結(jié)果與歷史結(jié)果相對(duì)比，更新最優(yōu)結(jié)果，取代差的結(jié)果。

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

2.4 實(shí)驗(yàn)仿真

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

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

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

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

3 結(jié)語(yǔ)

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