信息物理融合生產(chǎn)系統(tǒng)動態(tài)任務(wù)調(diào)度研究

金 陽，蔣增強，鄂明成

(北京交通大學(xué) 機械與電子控制工程學(xué)院，北京 100044)

?

信息物理融合生產(chǎn)系統(tǒng)動態(tài)任務(wù)調(diào)度研究

金 陽，蔣增強，鄂明成

(北京交通大學(xué) 機械與電子控制工程學(xué)院，北京 100044)

為使制造系統(tǒng)適應(yīng)當(dāng)前多品種、小批量市場需求，有關(guān)CPPS的生產(chǎn)系統(tǒng)構(gòu)架和運行優(yōu)化技術(shù)成為當(dāng)前研究熱點。首先通過分析CPPS的研究背景和任務(wù)調(diào)度現(xiàn)狀，研究了CPPS的動態(tài)任務(wù)調(diào)度方法。該方法首先利用Petri網(wǎng)，建立了系統(tǒng)運行的邏輯模型；其次設(shè)計了系統(tǒng)中任務(wù)的表達形式和匹配方法，使得系統(tǒng)能夠自動接受、分析并執(zhí)行任務(wù)；再次為保證分布式系統(tǒng)的整體運行效果，設(shè)計了一種基于動態(tài)決策中心的雙層決策模式，并對其中的運行指標(biāo)和調(diào)度規(guī)則進行了說明；最后通過實例驗證，證明了所提出的策略不僅可以滿足系統(tǒng)的生產(chǎn)需求，而且能夠保證各項指標(biāo)的優(yōu)化。

信息物理融合生產(chǎn)系統(tǒng)；動態(tài)任務(wù)調(diào)度；Petri網(wǎng)；雙層決策模式

隨著當(dāng)今科學(xué)技術(shù)的快速發(fā)展，制造業(yè)正在面臨變革，其中以德國提出的“工業(yè)4.0”為代表?！肮I(yè)4.0”是以智能制造為主導(dǎo)的第四次工業(yè)革命，通過充分利用信息通訊技術(shù)和網(wǎng)絡(luò)空間虛擬系統(tǒng)——信息物理系統(tǒng)(cyber-physical systems, CPS)相結(jié)合的手段，實現(xiàn)新的生產(chǎn)組織系統(tǒng)[1]，即信息物理融合生產(chǎn)系統(tǒng)(cyber-physical production systems, CPPS)。CPPS是一種利用CPS相關(guān)技術(shù)，依賴不同設(shè)備上的嵌入式設(shè)備，不斷通過計算通信而形成并發(fā)式網(wǎng)絡(luò)，從而在復(fù)雜生產(chǎn)環(huán)境和需求多變的情況下增加工業(yè)生產(chǎn)系統(tǒng)的靈活性和自適應(yīng)性，實現(xiàn)現(xiàn)代工業(yè)制造的個性化、高效化的生產(chǎn)系統(tǒng)[2-4]。CPPS中，制造資源的自主性、生產(chǎn)任務(wù)的多樣性和制造環(huán)境的不確定性不斷增加，CPPS的任務(wù)調(diào)度模式將由集中式控制向分散式增強型控制轉(zhuǎn)變。CPPS的運行和調(diào)度過程可描述為：系統(tǒng)自動接受并分析任務(wù)，通過混雜環(huán)境感知數(shù)據(jù)的分析、融合與挖掘，結(jié)合系統(tǒng)自身運行狀態(tài)，制定合理的調(diào)度策略并依靠分布式節(jié)點自治協(xié)同地實施；同時，通過計算進程與物理進程相互影響的實時反饋循環(huán)，自主地協(xié)調(diào)物理進程[5]。如何處理不同設(shè)備間的協(xié)同關(guān)系，在不同的任務(wù)和目標(biāo)下，有效地對不同系統(tǒng)和機構(gòu)進行調(diào)度，是該生產(chǎn)系統(tǒng)面臨的一個重要的挑戰(zhàn)。

關(guān)于生產(chǎn)系統(tǒng)的調(diào)度，傳統(tǒng)研究主要為集中式調(diào)度，方法較為成熟。典型的方法包括數(shù)學(xué)規(guī)劃方法、啟發(fā)式搜索方法、系統(tǒng)仿真方法、人工智能方法等[6]。以上相關(guān)方法，可以對CPPS中任務(wù)調(diào)度提供有益的借鑒，但不能完全適用于分布式系統(tǒng)。而當(dāng)前一些分布式調(diào)度策略的研究中[7-9]，存在任務(wù)規(guī)模小且靜態(tài)、任務(wù)類別和相關(guān)數(shù)據(jù)已知、任務(wù)分配方式單一等問題，無法滿足CPPS中任務(wù)調(diào)度的需求。鑒于此，筆者將從系統(tǒng)運行邏輯模型設(shè)計、任務(wù)的定義和匹配方式設(shè)計、設(shè)備間的組織形式和調(diào)度策略設(shè)計這3個方面，進行CPPS中動態(tài)任務(wù)調(diào)度研究。

1 基于Petri網(wǎng)的邏輯模型搭建

Petri網(wǎng)最早由德國學(xué)者CARL博士于1962年在其論文中提出，其具有描述異步并發(fā)的能力[10]。相關(guān)學(xué)者已成功將Petri網(wǎng)應(yīng)用于不同領(lǐng)域[11-12]，如路徑優(yōu)化、生產(chǎn)調(diào)度、流水線平衡等優(yōu)化問題。鑒于此，筆者將采用Petri網(wǎng)進行邏輯模型的構(gòu)建。

制造系統(tǒng)的運行流程可描述為：制造系統(tǒng)接收任務(wù)后進行任務(wù)分析，獲取參數(shù)，選取可加工的任務(wù)，然后進行任務(wù)匹配，通過分配機制，將任務(wù)分配給合適的設(shè)備，設(shè)備執(zhí)行生產(chǎn)任務(wù)，如果正常完成，則繼續(xù)進行下一步任務(wù)，如果不能完成，則需重新進行任務(wù)分析和分配，如此往復(fù)，直至全部任務(wù)完成。系統(tǒng)運行流程如圖1所示，運行邏輯Petri網(wǎng)如圖2所示。

圖1 系統(tǒng)運行流程圖

圖2 系統(tǒng)運行邏輯Petri網(wǎng)示意圖

2 任務(wù)定義和匹配機制設(shè)計

2.1 任務(wù)定義方式

為了使制造系統(tǒng)自動執(zhí)行工作，需要對任務(wù)進行識別，因此需要設(shè)計規(guī)范的任務(wù)輸入形式：(工序編號，工序分類，緊前工序)。以機加工為例，將加工特征分為24類[13]，即有24個工序分類，編號為MF1～MF24。假定零件及其加工任務(wù)如圖3所示，其對應(yīng)的任務(wù)描述如表1所示。

圖3 加工任務(wù)示意圖

2.2 任務(wù)匹配方式

任務(wù)匹配即建立任務(wù)需求參數(shù)和設(shè)備功能參數(shù)之間的映射關(guān)系，建立任務(wù)需求的參數(shù)集合A=(a1，a2,…,an)，設(shè)備的參數(shù)集合B=(b1，b2,…,bn)，并建立兩者之間的關(guān)聯(lián)向量C={f1(a1，b1),f2(a2,b2),…,fi(ai,bi)}。其中fi(ai,bi)(i=1,2,…，n)表示參數(shù)ai和bi之間的匹配函數(shù)。

表1 任務(wù)輸入示意表

仍以機加工為例,設(shè)集合A=(2 800,400,400,0.21,1.60)。一個銑床集合B的部分示例如表2所示。則兩者間的關(guān)聯(lián)向量為：

C={(a1≤b1),(a2≤b2),(a3≤b3),

(a4≥b4),(a5≥b5)}

表2 銑床參數(shù)集合示例

通過計算，最終匹配結(jié)果為編號“XA2010”的設(shè)備能夠完成該任務(wù)。

3 CPPS的調(diào)度策略

3.1 基于動態(tài)決策中心的雙層決策模式設(shè)計

制造系統(tǒng)中的智能設(shè)備依靠分布式節(jié)點自治協(xié)同地實施工作，需要設(shè)計智能設(shè)備間的組織形式；同時，為了保證制造系統(tǒng)整體以優(yōu)化的狀態(tài)運行，系統(tǒng)中需要有一個上層的調(diào)控者來保證整體的運行效果。為此，筆者設(shè)計了一種“基于動態(tài)決策中心的雙層決策模式”，其示意圖如圖4所示。該模式分為調(diào)控層和決策執(zhí)行層兩層。調(diào)控層負(fù)責(zé)收集和統(tǒng)計當(dāng)前系統(tǒng)和任務(wù)的相關(guān)信息，并計算出對應(yīng)的指標(biāo)，為決策執(zhí)行層在每次決策時提供依據(jù)。決策執(zhí)行層為各智能設(shè)備。每個智能設(shè)備均存在一個信息決策中心，任意兩者間可實現(xiàn)互相通訊。

圖4 基于動態(tài)決策中心的雙層決策模型示意圖

當(dāng)出現(xiàn)新的任務(wù)時，首先將任務(wù)信息輸入任務(wù)接收設(shè)備并將其信息決策中心激活，該中心將信息發(fā)送到相關(guān)設(shè)備，組成一個臨時的決策中心，根據(jù)調(diào)控層當(dāng)前發(fā)布的狀態(tài)指標(biāo)、各設(shè)備相關(guān)參數(shù)，進行分配工作；分配完畢后，該中心關(guān)閉，領(lǐng)取任務(wù)的智能設(shè)備的信息決策中心激活，進行任務(wù)并執(zhí)行和上一層同樣的信息發(fā)布和決策工作，直到任務(wù)全部完成。這樣，調(diào)度決策的實施便由傳統(tǒng)的集中式轉(zhuǎn)化為分布式，每個執(zhí)行任務(wù)的設(shè)備均是決策者，自發(fā)完成決策任務(wù)。

3.2 系統(tǒng)運行狀態(tài)和評價指標(biāo)

3.2.1 調(diào)控層監(jiān)測指標(biāo)

(1)

(2)

(3)

式中：tkij為工序Aij(任務(wù)i的工序j)在設(shè)備k上的加工時間；u表示工序Aij可以選擇的設(shè)備總數(shù)；ESij為每個工序的最早開始時間；LFij為每個工序的最遲結(jié)束時間；Cap為某類工序同一時間的最大進行數(shù)量；EXPi為任務(wù)i的交貨期。

3.2.2 決策執(zhí)行層指標(biāo)

3.3 任務(wù)分配策略

3.3.1 分配目標(biāo)

筆者選取最大化加工質(zhì)量和最小化加工成本與延期成本為目標(biāo)，進行任務(wù)分配。因此，目標(biāo)函數(shù)可以表示為：

Z={minC1,minC2,maxQ}

(4)

(5)

(6)

(7)

式中：di為任務(wù)i的完工時間；Pi為完工利潤;αi為延期懲罰系數(shù)。

3.3.2 調(diào)度策略

調(diào)度分配的執(zhí)行過程按照合同網(wǎng)的基本模式進行，即決策中心將任務(wù)以競標(biāo)的方式下達，不同設(shè)備對可以進行的任務(wù)進行投標(biāo)；決策中心從當(dāng)前調(diào)控層獲取數(shù)據(jù)指標(biāo)，計算不同設(shè)備的標(biāo)值，選取合適的設(shè)備，將任務(wù)分配；若一臺設(shè)備同時得到不同的任務(wù)，則根據(jù)投標(biāo)傾向度選擇任務(wù)簽約，并將其他任務(wù)返回。此時決策中心重新計算各設(shè)備標(biāo)值并發(fā)送簽約意向，直到簽約完畢。具體流程如圖5所示。標(biāo)值BVkij和投標(biāo)傾向值BIkij的計算公式為：

(8)

BIkij=γ1×pij-γ2×Ckij+γ3×TLt+γ4×LDij

(9)

其中，為了使不同參數(shù)量綱一致，需要進行歸一化處理，如式(10)所示。參數(shù)β1～β4則與系統(tǒng)中設(shè)備繁忙度和任務(wù)寬松度相關(guān)，總體原則為：設(shè)備負(fù)載率越高，β1和β2越??；任務(wù)越寬松，β3和β4越小。

(10)

圖5 任務(wù)競標(biāo)流程圖

4 實例驗證

為了驗證筆者所提供策略的有效性，現(xiàn)通過實例進行驗證。設(shè)共有3種工種，5臺設(shè)備，每臺設(shè)備可以接受的工種、加工質(zhì)量和單位時間成本如表3所示，且各設(shè)備處于待工狀態(tài)。

表3 各設(shè)備相關(guān)參數(shù)

現(xiàn)有3個任務(wù)同時到達系統(tǒng)，各任務(wù)的具體信息如表4所示。每個工序的相關(guān)信息如表5所示，各任務(wù)的工序按照串行順序進行。

表4 各任務(wù)相關(guān)信息

按照筆者所采取的策略，各工序的分配和執(zhí)行結(jié)果如表6所示，3個任務(wù)的結(jié)束時間分別為45、50和50，均在交貨期前完成。

表5 各工序相關(guān)信息

表6 分配和執(zhí)行結(jié)果

在時刻10，工序1.1和工序2.1完工后，均需進行工種2，但只有設(shè)備5可用。按照獲利公式計算，工序1.2和工序2.2的獲利歸一化后分別為0.81和1.00。因此在傳統(tǒng)的合同網(wǎng)中，設(shè)備5將進行工序2.2，從而使工序1.2的最早開始時間變?yōu)?0，這將造成任務(wù)1延期交貨；而加入寬松率這一指標(biāo)后，由于任務(wù)1的寬松率為0.86，較任務(wù)2的0.64更為緊迫，經(jīng)過加權(quán)計算接標(biāo)傾向，設(shè)備5選擇工序1.2進行加工，從而保證了所有任務(wù)在交貨期前完成。同樣，在時刻31，工序3.3需要在設(shè)備1和設(shè)備4間進行選擇，兩個設(shè)備的質(zhì)量、成本、等待時間和加工時間的歸一化參數(shù)分別為(0.8,1.0,1.0,1.0)和(1.0,0.8,1.0,1.0)，相差較小，對于不同的權(quán)重取值，可能會導(dǎo)致不同的選擇結(jié)果，如果選中設(shè)備4進行加工，則會推遲工序2.3的進行，從而造成其延期交貨；由于加入了負(fù)載率這一指標(biāo)，使得設(shè)備4的負(fù)載率明顯大于1，從而最終選擇了設(shè)備1，也保證了后面任務(wù)2在交貨期前完工。

從以上分析可知，筆者所采用的雙層決策模式，保證了每次決策時各參數(shù)的局部優(yōu)化；同時上層的運行指標(biāo)，也能有效協(xié)調(diào)分布式系統(tǒng)中局部優(yōu)化和全局優(yōu)化間的關(guān)系，使系統(tǒng)整體在一個優(yōu)化的狀態(tài)下運行。

5 結(jié)論

筆者結(jié)合當(dāng)前制造業(yè)的發(fā)展趨勢和特點，提出分布式智能制造系統(tǒng)的優(yōu)勢和實施的必要性。然后從系統(tǒng)運行邏輯模型、任務(wù)表達與匹配方式、系統(tǒng)運行與調(diào)度策略3方面進行了設(shè)計。為了解決分布式制造系統(tǒng)追求局部優(yōu)化而忽略整體優(yōu)化的問題，提出了一種基于動態(tài)決策中心的雙層決策模式，使得系統(tǒng)能夠以分布式的方式，自動接收、分析并分配執(zhí)行任務(wù)。最終通過實例驗證，證明了筆者所提出策略的有效性和優(yōu)越性。

[1] 鄭賢玲.工業(yè)4.0:為客戶創(chuàng)造價值的思維模式[J].今日工程機械, 2014 (11): 66-67.

[2] MONOSTORI L. Cyber-physical production systems: roots, expectations and R&D challenges[J]. Procedia Cirp,2014(17):9-13.

[3] ANIS A, SCHAFER W, NIGGEMANN O. A comparison of modeling approaches for planning in cyber physical production systems[C]∥Emerging Technology and Factory Automation.[S.L.]： IEEE,2014:1-8.

[4] 魯川.面向信息物理融合系統(tǒng)的實時時空調(diào)度算法[D].廣州:廣東工業(yè)大學(xué),2013.

[5] 倫永亮.信息物理融合系統(tǒng)優(yōu)化調(diào)度理論與方法的研究[D].廣州:廣東工業(yè)大學(xué),2012.

[6] 徐俊剛,戴國忠,王宏安.生產(chǎn)調(diào)度理論和方法研究綜述[J].計算機研究與發(fā)展,2004,41(2):257-267.

[7] PANESCU D, PASCAL C. Holonic coordination obtained by joining the contract net protocol with constraint satisfaction[J]. Computers in Industry, 2016, 81(C):36-46.

[8] YIN X F, LI P K, CHEN C H. A distributed agent system for port planning and scheduling[J]. Advanced Engineering Informatics, 2011, 25(3):403-412.

[9] 任海英,鄒艷蕊.基于多Agent的柔性作業(yè)車間預(yù)先/重調(diào)度系統(tǒng)[J].武漢理工大學(xué)學(xué)報(信息與管理工程版),2012,34(1):69-73.

[10] 袁崇義.Petri網(wǎng)應(yīng)用[M].北京:科學(xué)出版社,2013:12-13.

[11] 徐劍,葉文華,楊斌,等.基于擴展Petri網(wǎng)的飛機裝配線建模及平衡方法[J].計算機集成制造系統(tǒng),2015,21(10):2596-2603.

[12] 朱偉,徐克林,孫禹,等.Petri網(wǎng)融合蟻群算法的物流配送路徑規(guī)劃[J].浙江大學(xué)學(xué)報(工學(xué)版),2011,45(12):2229-2234.

[13] CHEN L, MACWAN A, CHEN L, et al. Optimal module selection for preliminary design of reconfigurable machine tools[J]. Journal of Manufacturing Science & Engineering, 2005,127(1):104-115.

[14] 于付龍,仲梁維,李陽.基于BP神經(jīng)網(wǎng)絡(luò)的焊接工時定額模型研究[J].現(xiàn)代制造工程,2014(4):17-21.

JIN Yang:Postgraduate;School of Mechanical and Electronic Control Engineering, Beijing Jiaotong University, Beijing 100044, China.

Dynamic Task Scheduling for Cyber-Physical Production Systems

JIN Yang, JIANG Zengqiang, E Mingcheng

Today’s market demands are with features of multi-product and small batch, to make manufacturing system meet this trend, the system architecture and optimizing technology on the operation of cyber-physical production systems (CPPS) has become research focus. After analyzing the background of CPPS and the research status of task scheduling, dynamic task scheduling method for CPPS is studied. Firstly, the logical model for system operation is built using Petri net. Then, the expression form of tasks and matching method with devices are designed, the method make system accept, analyze and execute tasks automatically. Secondly, to guarantee the overall operation effect of the distributed systems, a two-level decision model that based on dynamic decision center is designed, and the performance indicators and scheduling rules are described. Finally, through the example verification, it proves that the strategy proposed in this paper can not only meet the production requirements of the system, but also can guarantee the optimization of each index.

cyber-physical production systems; dynamic task scheduling; Petri net; two-level decision model

2095-3852(2017)03-0324-06

A

2016-12-29.

金陽(1991-)，男，河北滄州人，北京交通大學(xué)機械與電子控制工程學(xué)院碩士研究生，主要研究方向為制造與服務(wù)系統(tǒng)運行優(yōu)化理論與技術(shù).

國家科技支撐計劃基金項目(2015BAF08B02)；中央高?；究蒲袠I(yè)務(wù)費專項資金項目(2015JBM078).

TH186

10.3963/j.issn.2095-3852.2017.03.016