蔣佳烜，朱天奇，李俊良，吳宇航

(1. 華北理工大學(xué)數(shù)學(xué)建模創(chuàng)新實(shí)驗(yàn)室，河北 唐山 063210；2. 華北理工大學(xué)理學(xué)院，河北 唐山 063210；3. 華北理工大學(xué) 機(jī)械學(xué)院，河北 唐山 063210；4. 華北理工大學(xué)機(jī)械工程學(xué)院，河北 唐山市 063210；5. 華北理工大學(xué)，河北 唐山 063210)

0 引言

在傳統(tǒng)的自動(dòng)生產(chǎn)線中，搬運(yùn)裝置一般采用PLC 定時(shí)或檢測(cè)每個(gè)工位光電開(kāi)關(guān)的狀態(tài)等簡(jiǎn)單的順序步進(jìn)控制調(diào)度策略。這種“靜態(tài)”調(diào)度的搬運(yùn)設(shè)備需要在線等待在加工工件，并且不能及時(shí)適應(yīng)不確定因素的影響，往往會(huì)造成物料傳輸鏈的阻塞，形成生產(chǎn)線物流瓶頸，制約生產(chǎn)線設(shè)備的利用率和生產(chǎn)率。因此急需設(shè)計(jì)一種智能加工系統(tǒng)，能夠在接到任務(wù)后作出最優(yōu)處理方案，以此來(lái)提高生產(chǎn)線的工作效率[1]。

RGV 是一種無(wú)人駕駛、能在固定軌道上自由運(yùn)行的智能車。它根據(jù)指令能自動(dòng)控制移動(dòng)方向和距離，并自帶一個(gè)機(jī)械手臂、兩只機(jī)械手爪和物料清洗槽，能夠完成上下料及清洗物料等作業(yè)任務(wù)，但不能智能選擇最優(yōu)化方案，為了更好地解決以上問(wèn)題，本文提出了以下三種情況，針對(duì)這三種情況建立模型來(lái)提高生產(chǎn)效率。

（1）一道工序的物料加工作業(yè)情況，每臺(tái)CNC 安裝同樣的刀具，物料可以在任一臺(tái)CNC 上加工完成；

（2）兩道工序的物料加工作業(yè)情況，每個(gè)物料的第一和第二道工序分別由兩臺(tái)不同的CNC 依次加工完成；

（3）CNC 在加工過(guò)程中可能發(fā)生故障（據(jù)統(tǒng)計(jì)：故障的發(fā)生概率約為1%）的情況，每次故障排除（人工處理，未完成的物料報(bào)廢）時(shí)間介于10～20 分鐘之間，故障排除后即刻加入作業(yè)序列。要求分別考慮一道工序和兩道工序的物料加工作業(yè)情況。

1 構(gòu)建一道工序的物料加工作業(yè)的RGV 動(dòng)態(tài)調(diào)度模型

首先用線性加權(quán)的方式將CNC 平均等候時(shí)間和RGV 所走路徑作為優(yōu)化目標(biāo)組合成一個(gè)新的評(píng)價(jià)函數(shù)，即多目標(biāo)距離函數(shù)，并由此評(píng)價(jià)函數(shù)來(lái)衡量RGV 智能車的操作性能，最終選擇在滿足約束條件前提下的具有最小距離函數(shù)值得RGV 的路徑。

1.1 平均等候時(shí)間

等候時(shí)間，就是指從CNC 完成作業(yè)后發(fā)出需求信號(hào)到RGV 到達(dá)此發(fā)出需求信號(hào)的CNC 所經(jīng)過(guò)的時(shí)間。而平均等候時(shí)間就是所有CNC 需要等候時(shí)間的平均值，這也是RGV 在調(diào)度策略中的重要指標(biāo)[2]。等候時(shí)間包括CNC 發(fā)出需求信號(hào)后，RGV 處理其他CNC 的時(shí)間和RGV 從上一個(gè)CNC 到發(fā)出需求信號(hào)的CNC 過(guò)程中所需要的時(shí)間?？捎萌缦卤磉_(dá)式計(jì)算：

其中T 代表CNC 等待RGV 服務(wù)時(shí)間，TMT表示RGV 運(yùn)行到發(fā)出需求信號(hào)的CNC 所需要的時(shí)間。TAT表示RGV 處理其他CNC 的時(shí)間。 T1表示RGV 移動(dòng)一個(gè)單位所需要的時(shí)間， T2表示RGV 移動(dòng)兩個(gè)單位所需要的時(shí)間， T3表示移動(dòng)三個(gè)單位所需要的時(shí)間。 T4表示上下料所需時(shí)間， T5表示清洗所需要的時(shí)間。

1.2 用動(dòng)態(tài)規(guī)劃算法求解RGV 所走路徑

設(shè)RGV 對(duì)CNC 進(jìn)行一班次連續(xù)作業(yè)為T 個(gè)小時(shí)?，F(xiàn)有n（n=8）個(gè)CNC 可供RGV 進(jìn)行連續(xù)作業(yè)處理，這n 種物品的編號(hào)分別為1,2, … ,n。每個(gè)CNC 需要被處理的時(shí)間為t1,t2···,tn，每次RGV 對(duì)CNC處理所移動(dòng)的單位長(zhǎng)度為 s1, s2, ···,sn。每個(gè)CNC 被處理的次數(shù)為 xj（xj≥ 0且為整數(shù)， j∈ {1,2,…, n}）。求解如何選擇對(duì)CNC 進(jìn)行處理，使RGV 移動(dòng)的總距離S 達(dá)到最大。（其中T , t1, t2,… , tn和 s1, s2,…, sn均為整數(shù)）。

建立其模型為：

（1）劃分階段K：將8 個(gè)CNC 按1,2, … ,n排序，每個(gè)階段RGV 對(duì)一臺(tái)CNC 進(jìn)行加工處理。

（2）確定決策變量： xk，對(duì)第k 個(gè)階段CNC 進(jìn)行處理的總次數(shù)； Tk，對(duì)第k 個(gè)階段對(duì)CNC 進(jìn)行作業(yè)操作耗費(fèi)的總時(shí)間。

（3）建立狀態(tài)轉(zhuǎn)移方程：Tk=Tk-1+ tk· xk

（4）建立遞歸方程：

最后根據(jù)確定的優(yōu)化目標(biāo)，確定多目標(biāo)距離函數(shù)公式為：

其中， wi即評(píng)價(jià)函數(shù)的參數(shù)，0≤ wi≤ 1且 w1+w2= 1； fw( i )為RGV 到達(dá)第i 個(gè)CNC 時(shí)CNC 需要等候的時(shí)間， fc( i )表示RGV 到達(dá)第i 個(gè)CNC 時(shí)所需要經(jīng)過(guò)的路程。 fw*表示期望等候時(shí)間； fc*表示期望移動(dòng)距離。

由于這兩個(gè)指標(biāo)的量綱不同，為了量綱統(tǒng)一化，需要對(duì)對(duì)應(yīng)的目標(biāo)函數(shù)進(jìn)行統(tǒng)一量綱處理，即在目標(biāo)函數(shù)中引入期望等候時(shí)間、期望移動(dòng)距離 fc*[3]。

1.3 基于排隊(duì)論的仿真模擬

M/M/1/N/∝排隊(duì)模型表示CNC 向RGV 發(fā)出的需求指令為無(wú)限，各個(gè)CNC 發(fā)送指令相互獨(dú)立，指令發(fā)送規(guī)律服從泊松分布，CNC 發(fā)送指令平均速率為λ；單服務(wù)臺(tái)，隊(duì)長(zhǎng)限制為N（即系統(tǒng)中最多允許有N 個(gè)CNC 在排隊(duì)），先到先服務(wù)，RGV 在為各CNC 服務(wù)的時(shí)間相互獨(dú)立，且服從負(fù)指數(shù)分布，RGV 上下料的平均速率為μ。

圖1 智能RGV 的工作流程 Fig.1 Intelligent RGV workflow

根據(jù)智能加工系統(tǒng)所給信息對(duì)相應(yīng)的參數(shù)進(jìn)行賦值：

CNC 發(fā)送指令的平均速率λ=0.1 個(gè)/分鐘

RGV 上下料的平均速率μ=1 臺(tái)/分鐘

最多等待服務(wù)CNC 臺(tái)數(shù)N=8 臺(tái)

仿真時(shí)間Total_time=480 分鐘

根據(jù)CNC 發(fā)送指令平均速率λ 和RGV 上下料的平均速率為μ 來(lái)確定每個(gè)CNC 從發(fā)送指令到接受上下料服務(wù)的時(shí)間間隔和上下料時(shí)間間隔。上下料間隔時(shí)間可以用負(fù)指數(shù)分布函數(shù)exprnd 來(lái)生成[4]。由于泊松過(guò)程的時(shí)間間隔也服從負(fù)指數(shù)分布，故亦可由此函數(shù)生成實(shí)現(xiàn)CNC 指令到達(dá)的時(shí)間間隔。根據(jù)該算法對(duì)RGV 動(dòng)態(tài)調(diào)度進(jìn)行仿真，得到以下兩個(gè)仿真曲線。

圖2 CNC 發(fā)送指令時(shí)間與RGV 提供服務(wù)時(shí)間的曲線圖 Fig.2 Curve diagram of CNC sending instruction time and RGV providing service time

圖3 CNC 等待上料時(shí)間與發(fā)出指令到接受服務(wù)時(shí)間的曲線圖 Fig.3 Curve diagram of CNC waiting for feeding time and sending instructions to receiving service time

通過(guò)仿真曲線可以看出建立的RGV 動(dòng)態(tài)調(diào)度模型可以很好地指導(dǎo)RGV 完成上下料和清洗工作，在該模型的調(diào)度中，CNC 發(fā)送指令時(shí)間與RGV 提供服務(wù)時(shí)間高度吻合，說(shuō)明CNC 從發(fā)出需求指令到接受RGV 服務(wù)不需要經(jīng)歷很長(zhǎng)的等待時(shí)間，在該調(diào)度模型中RGV 可以在接收指令后及時(shí)的提供服務(wù)，實(shí)現(xiàn)了對(duì)時(shí)間的準(zhǔn)確把握，提高了工作效率。

2 構(gòu)建兩道工序的物料加工作業(yè)的RGV 動(dòng)態(tài)調(diào)度模型

2.1 CNC 最短流程時(shí)間組合

把Johnson算法用于一般的n/m/P/maxF（最長(zhǎng)流程時(shí)間），目標(biāo)函數(shù)是使最長(zhǎng)流程時(shí)間最短[5]。maxF等于一批物料最長(zhǎng)完工時(shí)間Cmax。設(shè)n個(gè)物料的加工順序?yàn)镾={s1,s2,…,sn}，其中si為排在第i位加工的物料的代號(hào)。以csik表示物料si在機(jī)器Mk上的完工時(shí)間，tsik表示物料si在Mk上的加工時(shí)間，i=1,2,…,n；k=1,2,…,m，則csik按以下公式計(jì)算：

當(dāng)ri=0, i=1,2, ···, n 時(shí)，最大流程時(shí)間為

當(dāng)由（3）式得出csnm時(shí)， Fmax就求得了。

對(duì)于兩道工序的物料加工所需時(shí)間為T ，公式為T = t1+ t2，其中 ti為第i 道工序所需加工時(shí)間（ i=1,2）。對(duì)于兩道工序的問(wèn)題，其中m=4，首先，把8 臺(tái)機(jī)器系統(tǒng)的每?jī)膳_(tái)機(jī)器組成一組，產(chǎn)生4個(gè)兩臺(tái)機(jī)器問(wèn)題的集合，然后利用Johnson 的兩臺(tái)機(jī)器算法改良成四臺(tái)機(jī)器的算法得到4 個(gè)加工順序，最后選擇其中最好的一個(gè)作為近似最優(yōu)解。再將8 臺(tái)機(jī)器兩兩進(jìn)行組合排列共有4!種可能，將這24種可能全部按Johnson 算法進(jìn)行最大流程時(shí)間的求解，我們?nèi)∵@24 組解中，用時(shí)最短的一組排列組合。

2.2 RGV 動(dòng)態(tài)調(diào)度優(yōu)化設(shè)計(jì)

確定每一道工序在某一具體時(shí)間開(kāi)始設(shè)備上加工，保證RGV 所移動(dòng)距離最小并盡可能對(duì)更多的物料進(jìn)行加工，所以，我們建立如下的目標(biāo)函數(shù)：

式中，Ei為任務(wù)提前懲罰； Di為任務(wù)拖期懲罰。約束條件如下所述：

（1）完工時(shí)間約束：

式中， tEijmk為任務(wù)i ( i=1,2, ···) 的工序 j ( j=1,2)在設(shè)備組 m(m=1,2,3,4)內(nèi)設(shè)備k 的結(jié)束加工時(shí)間。

（2）動(dòng)態(tài)擾動(dòng)約束：

式中 t′ij為調(diào)度方案中任務(wù)i 的第j 道工序的開(kāi)工時(shí)間； tij為預(yù)調(diào)度方案中i的第j道工序的開(kāi)工時(shí)間。

設(shè)備平衡約束：

式中， TPvjmk為物料v 的工序j 在設(shè)備組m 內(nèi)設(shè)備k 的加工時(shí)間； Tavg為所有設(shè)備的平均加工時(shí)間；Xijmk為0-1 變量，1 表示任務(wù)i 在設(shè)備組m 中設(shè)備k 上先于任務(wù)j 加工。

（3）加工時(shí)間約束：

式中，Sijmkt 為任務(wù)i 的工序j 在設(shè)備組m 內(nèi)設(shè)備k 的開(kāi)始加工時(shí)間。SvjmkT為表示物料v 的工序j 在設(shè)備組m 內(nèi)設(shè)備k 的加工準(zhǔn)備時(shí)間。

3 CNC 發(fā)生故障時(shí)，別基于一道與兩道工序建立RGV 動(dòng)態(tài)調(diào)度模型

3.1 序故障情況建立RGV 動(dòng)態(tài)調(diào)度模型

1.建立最小加工時(shí)間公式

m：CNC總數(shù)；

n：待加工物料總數(shù)；

si：排在第i個(gè)位置的物料，i=1,2,···,n；

S：物料排列集合，S=｛s1,s2,···,sn｝；

p(i,j)：物料i在第j臺(tái)CNC上的加工時(shí)間，相互獨(dú)立的隨機(jī)變量，i=1,2,···,n；j=1,2,···,8；

Bj：CNCj的連續(xù)可用時(shí)間，即CNCj從開(kāi)始(或修復(fù)后重新)運(yùn)轉(zhuǎn)到下次發(fā)生故障期間的運(yùn)轉(zhuǎn)時(shí)間，隨機(jī)變量j=1,2,···,8；

Rj：CNCj的故障修復(fù)時(shí)間，隨機(jī)變量j=1,2,···8；

t(i,j)：物料i在CNCj上的開(kāi)始加工時(shí)刻；

c(i,j)：物料i在CNCj上的完工時(shí)刻；

C(i)：物料i在最后一臺(tái)CNC上的加工完成時(shí)刻；

Cmax：所有物料加工的最大完成時(shí)刻；

EX：隨機(jī)變量X的期望值，例如，Ep(i,j)表示加工時(shí)間的期望值。

當(dāng)僅考慮加工時(shí)間隨機(jī)時(shí)，對(duì)應(yīng)于排列S的各個(gè)物料在每臺(tái)CNC上的完成時(shí)間描述如下：

目標(biāo)是最小化最大完工時(shí)間，即

以最小化最大完工時(shí)間(ECmax)為目標(biāo)的 SF-SSP 調(diào)度問(wèn)題就是確定 n 個(gè)物料的加工順序使得ECmax最小，其最優(yōu)結(jié)果記作ECm*a，即：

2.ECmax的求解算法

為合理地計(jì)算故障發(fā)生的期望時(shí)刻和相應(yīng)的目標(biāo)值 E Cmax，設(shè)計(jì)了兩類計(jì)算規(guī)則，用以計(jì)算不同CNC 工作方式下的故障發(fā)生時(shí)刻，并計(jì)算物料i (i=1,2, ···,n)在CNC j ( j=1,2, ···, 8)上的完工時(shí)間期望值[6]。假設(shè)一個(gè)物料正在CNC 上加工時(shí)CNC 出現(xiàn)故障，修好后，被故障中斷的物料的工序在原來(lái)已加工的基礎(chǔ)上繼續(xù)加工，其計(jì)算規(guī)則如下：

假定在初始時(shí)刻，所有CNC 可用，且物料可以加工，有：

（1）情況1：CNC 從加工第一個(gè)物料開(kāi)始運(yùn)轉(zhuǎn)，一直運(yùn)轉(zhuǎn)到故障發(fā)生或所有物料結(jié)束，任意時(shí)刻都可能發(fā)生故障。CNCj 的故障時(shí)刻期望值為CNCj 的開(kāi)始工作時(shí)刻期望值Et ( s1, j )（或上次故障修復(fù)的時(shí)刻）與CNC 連續(xù)可用時(shí)間期望值EBj之和物料在上的完工時(shí)間期望值計(jì)算如下：

“×”表示故障，“EA”表示故障的期望發(fā)生時(shí)刻，如圖所示，若故障發(fā)生在EA 時(shí)刻：

其中，如果

說(shuō)明故障可以在CNC 正常閑置時(shí)間修好，因此這種故障不會(huì)影響生產(chǎn)。若故障發(fā)生在EB 時(shí)刻，則有

說(shuō)明這種故障導(dǎo)致物料i 的第j 道工序的完成時(shí)間后延jR 。

（2）情況2：CNC 從加工第一個(gè)物料開(kāi)始運(yùn)轉(zhuǎn)，一直運(yùn)轉(zhuǎn)到故障發(fā)生或所有物料結(jié)束，且CNC只有在加工過(guò)程中才可能發(fā)生故障。當(dāng) CNCj 的故障時(shí)間期望值存在于非加工時(shí)間區(qū)間上時(shí)，令故障時(shí)刻期望值等于，由此保證CNC 在非加工時(shí)間內(nèi)不會(huì)出現(xiàn)故障，即不存在圖1 中EA 類故障時(shí)刻；當(dāng)不屬于區(qū)間時(shí)，CNC 的故障時(shí)刻期望值計(jì)算規(guī)則同情況 1。物料在上的完工時(shí)間期望值計(jì)算方法如下：

3.2 針對(duì)兩道工序故障情況建立RGV 動(dòng)態(tài)調(diào)度模型

兩道工序在一道工序的基礎(chǔ)上，增加了CNC 對(duì)物料進(jìn)行不同的加工處理。在問(wèn)題二已經(jīng)解出了最優(yōu)組合。

一道工序與兩道工序的共同點(diǎn)：當(dāng)CNC 發(fā)生故障后，不論是當(dāng)時(shí)物料在進(jìn)行第一道工序還是第二道工序，發(fā)生故障后，物料都被報(bào)廢，都需要從第一道工序進(jìn)行。因此CNC 出現(xiàn)故障對(duì)物料加工的順序與應(yīng)用CNC 的順序發(fā)生改變，最終導(dǎo)致物料加工完成的數(shù)量減少。

一道工序與兩道工序的不同點(diǎn)：兩道工序加工時(shí)間長(zhǎng)，且有最優(yōu)組合方案，完成一個(gè)物料加工相比一道工序的CNC 少。所以，我們只要分別基于問(wèn)題一二對(duì)一道工序與兩道工序的物料加工問(wèn)題，考慮CNC 故障，并依據(jù)表一所給的數(shù)據(jù)，我們就能得出再進(jìn)行作業(yè)操作時(shí)，CNC 出現(xiàn)故障，物料進(jìn)行加工開(kāi)始的時(shí)間與完工的時(shí)刻，從而得出我們需要的結(jié)果。

4 結(jié)論

進(jìn)行基于排隊(duì)論的仿真模擬，仿真結(jié)果表明在該調(diào)度模型中CNC 從發(fā)出需求指令到接受RGV 服務(wù)不需要經(jīng)歷很長(zhǎng)的等待時(shí)間，RGV 可以在接收指令后及時(shí)的提供服務(wù)，實(shí)現(xiàn)了對(duì)時(shí)間的準(zhǔn)確把握，提高了工作效率。

CNC 出現(xiàn)故障對(duì)物料加工的順序與應(yīng)用CNC 的順序發(fā)生改變，最終導(dǎo)致物料加工完成的數(shù)量減少?？紤]加工時(shí)間隨機(jī)性和對(duì)應(yīng)于排列各個(gè)物料在每臺(tái)CNC 上的完成時(shí)間，計(jì)算故障發(fā)生的期望時(shí)刻和相應(yīng)的目標(biāo)值，結(jié)合前兩問(wèn)的算法建立考慮CNC 可能故障的情況下的RGV 動(dòng)態(tài)調(diào)度模型。進(jìn)而針對(duì)RGV 所有情況的調(diào)度模型都建立完成。