湯洪濤，王大國(guó)，支文全

(浙江工業(yè)大學(xué) 機(jī)械工程學(xué)院，浙江 杭州 310014)

0 引 言

混流車(chē)間的生產(chǎn)調(diào)度問(wèn)題是指當(dāng)不同型號(hào)的加工件到達(dá)生產(chǎn)線開(kāi)始加工任務(wù)時(shí)，在各類諸如緊急插單、機(jī)器故障等的動(dòng)態(tài)擾動(dòng)下，產(chǎn)品的加工序列需要重新調(diào)整，以使得調(diào)度目標(biāo)得到持續(xù)優(yōu)化[1]。

當(dāng)前，混流生產(chǎn)調(diào)度問(wèn)題受到了廣泛的關(guān)注。THOMOPOULO[2]通過(guò)最小化裝配線的等待和超載時(shí)間進(jìn)行建模，并采用了一種啟發(fā)式算法對(duì)其求解；HYUN等[3]提出的數(shù)學(xué)模型關(guān)注于物料消耗速率均衡化、生產(chǎn)成本最小化，創(chuàng)新設(shè)計(jì)了以PS-NC選擇機(jī)制為基礎(chǔ)的改進(jìn)遺傳算法；MULLEN MC等[4]將物料消耗均衡化及負(fù)荷平衡化作為優(yōu)化目標(biāo)進(jìn)行調(diào)度，設(shè)計(jì)了改進(jìn)的模擬退火算法進(jìn)行了求解；蔣艷等[5]以空閑與超載時(shí)間之的和值最小化為目標(biāo)進(jìn)行調(diào)度研究，提出了借鑒小生境技術(shù)的改進(jìn)遺傳算法進(jìn)行求解。

從文獻(xiàn)分析可以看出：以往多數(shù)研究的重調(diào)度背景是傳統(tǒng)生產(chǎn)環(huán)境，信息化程度低、信息采集緩慢，調(diào)度結(jié)果存在嚴(yán)重的遲滯性；另外，在求解方面也存在容易陷入局部最優(yōu)的問(wèn)題。

在混流生產(chǎn)調(diào)度的問(wèn)題上，本文將建立一種基于射頻識(shí)別技術(shù)(RFID)的物聯(lián)網(wǎng)制造環(huán)境，形成閉環(huán)調(diào)度系統(tǒng)，提升混流生產(chǎn)系統(tǒng)的魯棒性。

1 基于RFID的物聯(lián)網(wǎng)實(shí)時(shí)調(diào)度平臺(tái)構(gòu)建

混流生產(chǎn)的動(dòng)態(tài)調(diào)度需要建立及時(shí)的信息反饋環(huán)境，因此本文提出一個(gè)在混流生產(chǎn)車(chē)間實(shí)現(xiàn)信息共享的物聯(lián)網(wǎng)基礎(chǔ)架構(gòu)，采用RFID即插即用方式實(shí)現(xiàn)Multi-Agent封裝，構(gòu)建基于RFID-Bus的實(shí)時(shí)信息傳遞模式并提出相應(yīng)部署策略，為兩級(jí)動(dòng)態(tài)調(diào)度提供調(diào)度數(shù)據(jù)來(lái)源。

1.1 Multi-Agent封裝與接入

在混流生產(chǎn)實(shí)際環(huán)境下，本研究對(duì)設(shè)備、工具與RFID閱讀器等數(shù)據(jù)采集設(shè)備進(jìn)行綁定，將其封裝成主動(dòng)智能對(duì)象；對(duì)工件、操作者與RFID標(biāo)簽綁定，構(gòu)成被動(dòng)智能對(duì)象，這些智能對(duì)象通過(guò)部署在車(chē)間現(xiàn)場(chǎng)的無(wú)線傳感網(wǎng)絡(luò)組成Multi-Agent系統(tǒng)，從而實(shí)現(xiàn)實(shí)時(shí)信息之間的交互流轉(zhuǎn)[6]。RFID設(shè)備服務(wù)提供程序應(yīng)用接口(DSPI)定義了封裝RFID設(shè)備的驅(qū)動(dòng)程序，設(shè)定各設(shè)備的訪問(wèn)模式為同一方式，實(shí)現(xiàn)RFID設(shè)備的即插即用。

整體訪問(wèn)接入模型如圖1所示。

圖1 RFID訪問(wèn)接入模型

1.2 RFID-Bus實(shí)時(shí)響應(yīng)機(jī)制

RFID設(shè)備所傳遞的實(shí)時(shí)信息采用RFID-Bus機(jī)制進(jìn)行響應(yīng)處理，該機(jī)制能夠?qū)θ罩?、訂閱、?dòng)作、消息等數(shù)據(jù)庫(kù)進(jìn)行管理，并且可以通過(guò)原語(yǔ)與第三方應(yīng)用連接，實(shí)現(xiàn)信息的響應(yīng)與處理。

1.3 兩級(jí)RFID-Bus物聯(lián)網(wǎng)環(huán)境建立

為實(shí)現(xiàn)不同層級(jí)的業(yè)務(wù)需要，本研究在混流生產(chǎn)物聯(lián)網(wǎng)環(huán)境中進(jìn)行兩級(jí)RFID-Bus的構(gòu)建。底層一級(jí)為部署在生產(chǎn)現(xiàn)場(chǎng)中的消息集成總線，實(shí)現(xiàn)Agent系統(tǒng)的信息傳遞與反饋?lái)憫?yīng)；上層一級(jí)為業(yè)務(wù)集成總線，以SOA架構(gòu)實(shí)現(xiàn)WebService消息服務(wù)，進(jìn)而對(duì)業(yè)務(wù)實(shí)現(xiàn)集成。體系結(jié)構(gòu)如圖2所示。

圖2 兩級(jí)RFID-Bus體系結(jié)構(gòu)

1.4 物聯(lián)網(wǎng)架構(gòu)組件部署

在完成Multi-Agent封裝、明確響應(yīng)機(jī)制后，本研究將物聯(lián)網(wǎng)環(huán)境下的基礎(chǔ)組件在混流生產(chǎn)環(huán)境中進(jìn)行正確部署。其中，RFID中間件和消息集成總線安置在實(shí)際環(huán)境中信息采集設(shè)備等主動(dòng)智能體上，這些設(shè)備與被動(dòng)智能體進(jìn)行交互后將消息傳送至消息集成總線進(jìn)行相應(yīng)反饋。業(yè)務(wù)集成總線布局在企業(yè)業(yè)務(wù)服務(wù)器上，接收底層消息總線及系統(tǒng)管理程序的消息，同時(shí)與ERP等系統(tǒng)進(jìn)行交互。由此，建立的物聯(lián)網(wǎng)環(huán)境即可為實(shí)時(shí)自適應(yīng)調(diào)度提供反饋。

2 混流生產(chǎn)預(yù)調(diào)度與算法設(shè)計(jì)

在完成物聯(lián)網(wǎng)環(huán)境構(gòu)建之后，本研究根據(jù)車(chē)間生產(chǎn)能力和加工任務(wù)即開(kāi)始進(jìn)行車(chē)間生產(chǎn)的預(yù)調(diào)度，在擾動(dòng)發(fā)生后可以根據(jù)此調(diào)度結(jié)果進(jìn)行重調(diào)度動(dòng)態(tài)優(yōu)化。

2.1 問(wèn)題描述

裝配線待加工產(chǎn)品序列中有M種產(chǎn)品，總裝線包含N個(gè)工作站，流水線速度v恒定，各種產(chǎn)品的待加工量為Di(i=1，2，…，M)，產(chǎn)品i在第n道工位的加工時(shí)間為tin。設(shè)生產(chǎn)循環(huán)次數(shù)為r，則在一個(gè)最小生產(chǎn)單元內(nèi)，每種產(chǎn)品的裝配量di=Di/r，對(duì)其進(jìn)行排序，r次循環(huán)之后，即能夠?qū)崿F(xiàn)排產(chǎn)期的生產(chǎn)調(diào)度。

2.2 預(yù)調(diào)度模型建立

混流生產(chǎn)車(chē)間的調(diào)度是一個(gè)復(fù)雜優(yōu)化問(wèn)題，因此，混流生產(chǎn)的預(yù)調(diào)度建模即考慮以物料消耗速率均衡化、最短化最小生產(chǎn)周期作為雙重優(yōu)化目標(biāo)。

在最小生產(chǎn)循環(huán)周期中，物料消耗速率均衡化的目標(biāo)為：

(1)

式中：di—M種型號(hào)產(chǎn)品對(duì)應(yīng)的需求量；Kij—型號(hào)i(i=1，2，…，M)需要零件j(j=1，2，…L)的數(shù)量；XRi—前R個(gè)產(chǎn)品中，M種產(chǎn)品型號(hào)的數(shù)量。

設(shè)第R個(gè)產(chǎn)品在工位n的開(kāi)始作業(yè)時(shí)間為SRn，作業(yè)持續(xù)時(shí)間為T(mén)Rn，則其完成時(shí)間為ERn=SRn+TRn。假設(shè)最小生產(chǎn)循環(huán)周期為EdN，則最短化最小生產(chǎn)循環(huán)周期的目標(biāo)為：

f2=min(EdN)

(2)

具體約束如下：

在投產(chǎn)順序中每個(gè)位置有且只能有一個(gè)產(chǎn)品，XRi表示前R個(gè)位置，i種產(chǎn)品的型號(hào)數(shù)量為：

(3)

每種型號(hào)的產(chǎn)品在調(diào)度序列中出現(xiàn)的次數(shù)正好等于該產(chǎn)品的需求產(chǎn)量，Xdi表示一個(gè)最小循環(huán)生產(chǎn)周期中，i種產(chǎn)品型號(hào)的數(shù)量為：

Xdi=di

(4)

在加工過(guò)程中，一個(gè)工位在同一時(shí)間能且只能加工唯一一種產(chǎn)品，PRn為0-1變量，如果工位n上的產(chǎn)品為第R個(gè)產(chǎn)品，則PRn=1，否則為0，即：

(5)

后一個(gè)產(chǎn)品只能等待該工位加工完成，才能在該工位進(jìn)行加工，即：

SRn-E(R-1)n≥0

(6)

在加工過(guò)程中，同一個(gè)產(chǎn)品只能在上道工序生產(chǎn)完之后，才能送去下道工序加工，即：

SRn-ER(n-1)≥0

(7)

2.3 預(yù)調(diào)度求解算法設(shè)計(jì)

布谷鳥(niǎo)算法是由YANG等[7]提出的，其在路徑規(guī)劃、生產(chǎn)調(diào)度等方面有著成熟的應(yīng)用[8-11]。后來(lái)，國(guó)外SRIVASTAVA P R等[12-14]對(duì)CS算法進(jìn)行了改進(jìn)，國(guó)內(nèi)王李進(jìn)等[15-17]也對(duì)CS算法進(jìn)行了研究。但原始CS比較適合連續(xù)型優(yōu)化問(wèn)題的求解，對(duì)離散性、有約束的多目標(biāo)問(wèn)題還需進(jìn)一步研究。本文將小生境技術(shù)融入CS算法，將種群劃分成若干塊，之后依據(jù)適應(yīng)度函數(shù)值挑選出每塊中適應(yīng)度值最佳的個(gè)體組成一個(gè)精英群體，以此來(lái)求解多目標(biāo)的優(yōu)化問(wèn)題。算法具體設(shè)計(jì)如下：

(1)初始化。設(shè)定解的維數(shù)M，宿主個(gè)數(shù)N，被宿主發(fā)現(xiàn)的概率Pa，最大迭代次數(shù)為K，搜索上界為ub，下界lb，其中初始檔案為空集(Archive=[])，小生境半徑為σs，最大容量為ArchiveMax，初始迭代次數(shù)t=0，并隨機(jī)生成M*N的初始鳥(niǎo)巢位置矩陣y0(t)；

(2)編碼與解碼。采用基于位置的編碼方式，設(shè)定每個(gè)鳥(niǎo)巢都是一個(gè)n維向量，代表工序的排列;

(3)若t>k，則停止計(jì)算，輸出Archive，否則轉(zhuǎn)(4)；

(4)位置更新。根據(jù)Levy飛行原理，將鳥(niǎo)巢的位置更新，新的鳥(niǎo)巢矩陣為y1(t):

(5)適應(yīng)度的擇優(yōu)。找出鳥(niǎo)巢的最優(yōu)位置，計(jì)算鳥(niǎo)巢的矩陣y’的適應(yīng)度值，根據(jù)適應(yīng)度值進(jìn)行排序，將前N個(gè)對(duì)應(yīng)解作為新矩陣y2(t)；

(6)隨機(jī)淘汰。設(shè)定隨機(jī)數(shù)wi，根據(jù)被宿主發(fā)現(xiàn)概率Pa來(lái)淘汰y2(t)中的解，可以得到新矩陣y3(t):

(7)適應(yīng)度的擇優(yōu)。重復(fù)(4)計(jì)算y2(t)與y3(t)組成的矩陣的適應(yīng)度，擇優(yōu)組成新的矩陣y4(t);

(8)檔案的更新以及預(yù)處理。將y4(t)放入檔案Archive中，則Archive=[Archive,y4(t)]，按照Pareto支配關(guān)系，剔除被支配解，并保留非支配解；

(9)檔案縮減。當(dāng)檔案中解的個(gè)數(shù)大于ArchiveMax時(shí)，則通過(guò)小生境技術(shù)進(jìn)行檔案縮減，檔案中解的個(gè)數(shù)剛好在檔案的限制范圍內(nèi)時(shí)，則得到新的檔案集并返回到(2)中繼續(xù)搜索，直至滿足終止條件。

3 混流車(chē)間重調(diào)度研究

3.1 重調(diào)度策略

重調(diào)度對(duì)原有生產(chǎn)計(jì)劃進(jìn)行更新，因此也會(huì)對(duì)原有計(jì)劃完成時(shí)間產(chǎn)生影響，在重調(diào)度實(shí)施中既要注重調(diào)度的有效性，同時(shí)也要避免調(diào)整的偏差性過(guò)大造成完工時(shí)間劇烈波動(dòng)。本文選用以工件數(shù)量進(jìn)行衡量的滾動(dòng)窗口技術(shù)，同時(shí)基于事件驅(qū)動(dòng)與周期混合的再調(diào)度策略在擾動(dòng)發(fā)生后進(jìn)行動(dòng)態(tài)調(diào)度，先把調(diào)度過(guò)程分解成連續(xù)的靜態(tài)調(diào)度區(qū)間，然后進(jìn)行每個(gè)區(qū)間的調(diào)度優(yōu)化。

滾動(dòng)重調(diào)度窗口如圖3所示。

圖3 基于工件的滾動(dòng)重調(diào)度窗口

3.2 重調(diào)度實(shí)施流程

(8)

當(dāng)擾動(dòng)事件發(fā)生時(shí)，本研究將還未進(jìn)行調(diào)度處理的完工時(shí)間與預(yù)調(diào)度方案中完工時(shí)間的偏離度θ代表評(píng)估擾動(dòng)事件影響的指標(biāo)，其計(jì)算式為：

(9)

因此，本研究設(shè)定一個(gè)效能偏差值ρ，若θ≤ρ，則不需要進(jìn)行重調(diào)度，只需要利用車(chē)間內(nèi)部的調(diào)整來(lái)消除擾動(dòng)事件的影響。通過(guò)ρ可以消除影響較小的擾動(dòng)動(dòng)事件，減少系統(tǒng)的負(fù)擔(dān)，從而保持整個(gè)調(diào)度系統(tǒng)的穩(wěn)定性。

3.3 重調(diào)度算法設(shè)計(jì)

重調(diào)度算法同樣是基于布谷鳥(niǎo)算法進(jìn)行改進(jìn)設(shè)計(jì)，與預(yù)調(diào)度算法相較之下，重調(diào)度算法需要依據(jù)擾動(dòng)事件的具體情況進(jìn)行構(gòu)建。設(shè)定擾動(dòng)發(fā)生時(shí)刻為t，則重調(diào)度從t時(shí)刻開(kāi)始。對(duì)于正在加工的工件，其下一道工序的開(kāi)始時(shí)間是這個(gè)工件在該工序的加工完成時(shí)間與上一個(gè)工件在下道工序的完工時(shí)間的最大值。對(duì)于未加工的工件，其第一道工序的開(kāi)始時(shí)間是t時(shí)刻與前一個(gè)工件在第一道工序加工的完成時(shí)間的最大值。算法流程如圖4所示。

圖4 重調(diào)度算法流程

4 實(shí)例仿真

本研究選取某公司5種產(chǎn)量較大且工藝近似的產(chǎn)品(A、B、C、D、E)為調(diào)度仿真對(duì)象，對(duì)預(yù)調(diào)度、重調(diào)度的模型及算法進(jìn)行驗(yàn)證。5種產(chǎn)品的工序及工藝時(shí)間如表1所示。

表1 產(chǎn)品工藝及時(shí)間

同時(shí)，以上5種產(chǎn)品的月訂單量已知，如表2所示。

表2 各產(chǎn)品月訂單量

4.1 預(yù)調(diào)度仿真

本研究選用Matlab作為程序開(kāi)發(fā)平臺(tái)，采用混合布谷鳥(niǎo)搜索算法對(duì)預(yù)調(diào)度模型進(jìn)行求解，參數(shù)取值解的維數(shù)M=10，宿主個(gè)數(shù)N=30，被宿主發(fā)現(xiàn)概率Pa=0.25，步長(zhǎng)因子a=0.5，迭代次數(shù)K=100，小生境半徑為σs=0.05，最大容量為ArchiveMax=100。同時(shí)為了充分驗(yàn)證本文所提算法具備良好的搜索、收斂性能，選取遺傳算法、蟻群算法算法在該算例下同步運(yùn)行。其中：遺傳算法的種群規(guī)模P=100,交叉概率Pc=0.8，變異概率Pm=0.1，終止代數(shù)為200；蟻群算法中，啟發(fā)因子α=2，期望啟發(fā)式因子β=2，信息素?fù)]發(fā)因子ρ=0.15，螞蟻數(shù)量m=100，信息總量Q=20，迭代次數(shù)NC=200。3種算法求得的Pareto解集如圖5所示。

圖5 3種算法的Pareto前沿求解結(jié)果

以上3個(gè)算法中，混合布谷鳥(niǎo)算法完成求解的時(shí)間為6.49 s，蟻群算法為9.23 s，遺傳算法為10.14 s。同時(shí)由圖5可以看出：混合布谷鳥(niǎo)算法產(chǎn)生的解數(shù)量更多，分布較為均勻，并且能較好地靠近Pareto前沿。

在混合布谷鳥(niǎo)算法運(yùn)算結(jié)果下經(jīng)層次分析選出Pareto最優(yōu)解為：f1=51.8，f2=873。預(yù)調(diào)度的甘特圖如圖6所示。

圖6 預(yù)調(diào)度甘特圖

預(yù)調(diào)度第一個(gè)循環(huán)周期裝配時(shí)間為873 s，總時(shí)間為468 405 s，而車(chē)間自主調(diào)度結(jié)果中第一個(gè)循環(huán)周期裝配時(shí)間為1 021 s，總時(shí)間為504 517 s，可以證實(shí)預(yù)調(diào)度結(jié)果是有效可行的。

4.2 重調(diào)度仿真

本研究分別對(duì)插單、物料延遲到達(dá)、機(jī)器故障這3類擾動(dòng)實(shí)施重調(diào)度仿真。重調(diào)度策略參數(shù)取值為pk=1，1-a=0.05，β=0.1，ρ=0.001。

(1)插單。在t=11 752 s時(shí)刻，接到緊急訂單F，其訂單數(shù)量為1 000，交貨期為5 d，產(chǎn)品在各個(gè)工序的加工時(shí)(24,27,25,31,22,28,26,25,29,32,34,31,26,30,19,0,24,21,23,27)，故一個(gè)生產(chǎn)循環(huán)周期生產(chǎn)內(nèi)A∶B∶C∶D∶E∶F=5∶4∶4∶3∶2∶5，循環(huán)周期數(shù)為200，θ=0.06，采用局部重調(diào)度策略，自第25個(gè)循環(huán)周期開(kāi)始，利用混合布谷鳥(niǎo)搜索算法進(jìn)行局部重調(diào)度，重調(diào)度后的總加工時(shí)間為495 405 s；

(2)機(jī)器故障。在t=8 750 s時(shí)刻，生產(chǎn)設(shè)備出現(xiàn)故障，導(dǎo)致A生產(chǎn)停滯，設(shè)備修復(fù)時(shí)間為1 500 s,則θ=0.003，故采用右移重調(diào)度，重調(diào)度后的總加工時(shí)間為468 312 s；

(3)物料延遲。在t=214 760 s，產(chǎn)品B的物料發(fā)生延遲，延遲時(shí)間為t=61 000 s，則θ=0.13，采取完全重調(diào)度策略，在第442個(gè)循環(huán)周期中，利用混合布谷鳥(niǎo)搜索算法進(jìn)行重調(diào)度，重調(diào)度后的總加工時(shí)間為478 612 s。

將各擾動(dòng)事件的重調(diào)度結(jié)果與預(yù)調(diào)度方案進(jìn)行比較，結(jié)果如表3所示。

表3 重調(diào)度結(jié)果與預(yù)調(diào)度方案進(jìn)行比較

由表3可知：除了物料延遲對(duì)預(yù)調(diào)度方案產(chǎn)生較大影響外，其余擾動(dòng)的重調(diào)度方案結(jié)果與預(yù)調(diào)度差別不大且有效性良好，證明重調(diào)度的實(shí)施較好地解決了擾動(dòng)對(duì)混流生產(chǎn)的影響。

5 結(jié)束語(yǔ)

本文以混流生產(chǎn)車(chē)間為研究對(duì)象，構(gòu)建了以Multi-Agent系統(tǒng)、RFID-Bus機(jī)制為基礎(chǔ)的物聯(lián)網(wǎng)制造環(huán)境，建立了以物料消耗速率均衡化、最小生產(chǎn)循環(huán)周期最短化為目標(biāo)的預(yù)調(diào)度模型，并為其設(shè)計(jì)了混合布谷鳥(niǎo)搜索算法，根據(jù)發(fā)生的擾動(dòng)情況，重新構(gòu)建了混合布谷鳥(niǎo)求解算法。

仿真實(shí)例驗(yàn)證了調(diào)度模型、策略以及混合布谷鳥(niǎo)搜索算法的有效性。