多約束條件下智能RGV 的動態(tài)調(diào)度策略

張雨萌，胡正凱，王保榮，吳宇航

(1. 華北理工大學(xué) 數(shù)學(xué)建模創(chuàng)新實(shí)驗(yàn)室，河北 唐山 063210；2. 華北理工大學(xué) 理學(xué)院，河北 唐山 063210； 3. 華北理工大學(xué) 電氣工程學(xué)院，河北 唐山 063210；4. 華北理工大學(xué) 化學(xué)工程學(xué)院，河北 唐山 063210； 5. 河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室，河北 唐山 063210；6. 唐山市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室，河北 唐山 063210)

0 引言

智能加工系統(tǒng)[1]由8 臺計算機(jī)數(shù)控機(jī)床（CNC）、1 輛軌道式自動引導(dǎo)車（RGV）、1 條RGV 直線軌道、1 條上料傳送帶、1 條下料傳送帶等附屬設(shè)備組成。RGV 是一個由機(jī)械手臂、兩只機(jī)械手爪和物料清洗槽組成的具有智能控制的小車，其清洗槽每次只能清洗1 個物料，機(jī)械手臂前端有2 個手爪，通過旋轉(zhuǎn)可以先后各抓取1 個物料，可以完成上下料作業(yè)，通過給CNC 進(jìn)行取放料，進(jìn)行動態(tài)調(diào)度，使其達(dá)到最優(yōu)的生產(chǎn)效率。通過研究確定了RGV 的調(diào)度策略、建立RGV 動態(tài)調(diào)度[2]模型，使得該系統(tǒng)在不同工作情況下具有最優(yōu)的工作效率。

1 基于路程時間差限定的放料順序的確定

對零件的加工分析，由于8 個CNC 工作臺初始狀態(tài)是都沒有放上需加工的零件的，首先，需要對8 個CNC 工作臺進(jìn)行放料工作，對8 個CNC 工作臺進(jìn)行全排列，選取其中一種排列方式進(jìn)行第一批放料工作，從而使得每個CNC 工作臺都會加工第一批加工器件，由于初始位置是CNC1#和CNC2#正中間，若對8 個CNC 工作臺進(jìn)行全排列，放定第一批的8 個器件，不同放料排列方式之間會產(chǎn)生初始的路程時間差，若選定了最優(yōu)的排列方式，可以將系統(tǒng)調(diào)制最優(yōu)狀態(tài)，初試的路程時間差可以忽略不計?？梢詫⒎胖玫谝粋€零件開始時刻定義為系統(tǒng)0 時刻。

對第一批放料的過程進(jìn)行模擬，將不同順序放料的零件進(jìn)行第一批放料，如下式：

其中，Lit→j表示從i位置到j(luò)位置所用時間，F(xiàn)tm、Ftn表示取放料所用時間，m為1、3、5、7，n為2、4、6、8，Jt表示零件加工時間，Qt表示零件清洗所用時間，En表示第n個零件加工結(jié)束時間，F(xiàn)n表示第n個零件放料結(jié)束時間，Dt表示CNC工作臺等待RGV小車的時間，Mt1→i表示從0時刻開始計時，從1位置放料開始到第i位置放料完成時間總和。

為了使系統(tǒng)達(dá)到最優(yōu)狀態(tài)應(yīng)使得所有的Dt總和達(dá)到最小，即此系統(tǒng)達(dá)到了最優(yōu)的工作效率，若初始的Dt總和達(dá)到了最小，往后的每批原件都會達(dá)到最優(yōu)，其間還應(yīng)考慮第一批最后一個零件清洗結(jié)束時間和第二批第一個零件的加工結(jié)束時間，若第一批最后一個零件清洗結(jié)束時間比第二批第一個零件的加工結(jié)束時間晚，可以使RGV小車沒有停留時間一直處于工作狀態(tài)。

第一批最后一個零件清洗結(jié)束時間為：

第二批第一個零件的加工結(jié)束時間為：

上述兩個時間差受 Lt總、Lt8→1、D1t大小所控制的系統(tǒng)，然而 Lt8→1、 D1t大小均受 Lt總所影響，因此通過這個限制條件從8 個CNC 工作臺全排列中選取最優(yōu)的一種排列方式，即可達(dá)到系統(tǒng)最優(yōu)。通過對此限制條件進(jìn)行求解計算出一道工序下第一組的最優(yōu)放料順序?yàn)?5281746，此種放料順序生產(chǎn)一批零件耗時最短，從而使整個系統(tǒng)達(dá)到最優(yōu)狀態(tài)。

2 基于約束條件下的排隊論模型

確定好放料順序后，采用就近原則下的仿真算法，正在服務(wù)的CNC 序號用1-8 表示，采用0 表示非加工狀態(tài)，1 表示加工狀態(tài)，同時累加CNC 的加工時間，RGV 記為4 個狀態(tài)，1 表示正在上下料，2 表示正在清洗，3 表示正在移動，0 表示等待狀態(tài)，CNC 處理工序的組合方式為窮舉法。

采用計時循環(huán)，以秒為單位，首先分別預(yù)計8 臺機(jī)床的過渡時間，采用DX 表示服務(wù)狀態(tài)，G 表示工序時間，XT 表示CNC 加工累計時間值，Z 表示正在服務(wù)的CNC 序號，F(xiàn)Z 表示正要或剛完成某序號的CNC 服務(wù)，j 表示8 個工序，X 表示加工或非加工狀態(tài)，T 表示正在執(zhí)行周期時間向量。

上式1 表示剛完成服務(wù)的CNC，式子2 表示正在服務(wù)的CNC,式子3 表示CNC 加工狀態(tài)，式子4表示CNC 等待狀態(tài)，通過計算RGV 上下料時間，移動到各CNC 所需的時間，清洗時間等，需要考慮各個CNC 剩余的加工時間與RGV 移動至CNC 的較大時間，因此對RGV 判斷判定如下：

上式1 表示處于上下料階段，式子2 處于清洗階段，式子3 處于運(yùn)動階段，式子4 處于RGV 等待狀態(tài)。F 表示的是RGV 計數(shù)變量，CT 表示執(zhí)行命令累加時間向量。

綜上所述，通過就近原則的仿真得到對于一道工序的器件，在第一組生產(chǎn)數(shù)據(jù)下可以生產(chǎn)376 件，在第二組生產(chǎn)數(shù)據(jù)下可以生產(chǎn)359 件，在第三組生產(chǎn)數(shù)據(jù)下可以生產(chǎn)385 件。

3 兩道工序的調(diào)度模型的改進(jìn)

3.1 兩道工序的生產(chǎn)過程分析

與上述一道工序的研究相比，兩道工序的生產(chǎn)過程實(shí)質(zhì)是在此基礎(chǔ)上加入了“分組”的情況，即兩個CNN 工作臺為一組共同處理物料，不同的分組會使RGV 在移動過程中耗時不同進(jìn)而產(chǎn)生生產(chǎn)效率的差別[3]。于是，通過改進(jìn)遺傳算法來確定對CNN 的分組情況及RGV 移動的最優(yōu)路徑[4]。

3.2 遺傳算法的引入與改進(jìn)

（1）種群初始化

種群初始化是對遺傳個體進(jìn)行編碼，8 個CNN 工作臺編號分別為 1、2、3、4、5、6、7、8，RGV有4 個位置編號分別為1、2、3、4，當(dāng)RGV 處在位置編號1、2、3、4 時分別為CNN 工作臺1 和2號、3 和4 號、5 和6 號、7 和8 號提供服務(wù)。然后，隨機(jī)選定4 個工作臺作為第一道工序的加工器，另外4 個作為第二道工序的加工器，兩種加工器自由結(jié)合實(shí)現(xiàn)分組，生成種群個體[5]。

（2）選擇

計算每個個體的目標(biāo)函數(shù)值。首先，在加工生產(chǎn)物料時，RGV完成最后一個清洗任務(wù)所用的時間即為完成此組任務(wù)所用的時間，即為一個個體的目標(biāo)函數(shù)值，具體包括上下料時間、加工時間、清洗時間、移動時間。然后，用基于排序的適應(yīng)度分配方法[7]計算每個個體的適應(yīng)度fi=2-p+2(p-1)(n-1）/(N-1)p∈[1,2]，其中fi為個體i的適應(yīng)度，N為種群大小，n為個體在種群中的序位，p為選擇壓差。最后，計算每個個體的選擇概率，通過隨機(jī)遍歷抽樣法[7]可得到第i個個體的選擇概率Fi。此過程中，選擇的個體數(shù)目M=N×G，其中M為選擇的個數(shù)；G為代溝，取值為0.7～0.9。

最后計算每個人個體的選擇概率

式中：Fi為第i個個體的選擇概率，選取的方式采用隨機(jī)遍歷抽樣法。

（3）交叉

交叉操作產(chǎn)生全局較優(yōu)解。此處采用部分匹配交叉的方法進(jìn)行交叉操作[8]，首先在2個父個體中隨機(jī)選擇2個交叉點(diǎn)，如表1所示。

表1 有2個插入點(diǎn)的2個父個體Table 1 Two Parents with Two Insertion Points

然后交換中間的基因段，保留2 個父個體中兩端與中間段不重復(fù)的任務(wù)基因段， 并根據(jù)中間段的任務(wù)對應(yīng)關(guān)系，得到2 個子個體，如表2 所示。

表2 交叉完成后的2 個子個體 Table 2 Two Subindividuals after Cross Completion

（4）變異

通過變異產(chǎn)生更多種類的個體，來局部優(yōu)化[9]個體。

（5）判斷

判斷是否滿足終止條件，終止條件包括是否到達(dá)終止代數(shù)，目標(biāo)值、適應(yīng)度是否滿足要求等[10]。滿足終止條件時終止得到CNN 的最優(yōu)分組，否則開始下一次循環(huán)。

通過采用遺傳算法迭代與仿真技術(shù)的結(jié)合[11]，模擬加工過程，主要分為判斷清洗料的屬性、計算移動后裝載的時間變化、記錄車的料等。對工序機(jī)進(jìn)行約束，零件1 計數(shù)變量用NA 表示，零件2 計數(shù)變量用NB 表示，NA＞NB, 在第二道工序的CNC 中取較小者，NA = NB, 在第二道工序的CNC 中取較小者，NB＞NA, 在所有CNC 的較大時間中取較小者。同時記錄總加工量、剩余未完成的加工量和組合最佳方案等[12]。 最終得到在第一組生產(chǎn)數(shù)據(jù)下可以生產(chǎn)211 件，在第二組生產(chǎn)數(shù)據(jù)下可以生產(chǎn)182件，在第三組生產(chǎn)數(shù)據(jù)下可以生產(chǎn)222 件。

4 結(jié)論

本文給出了基于路程時間差限定的放料順序的確定模型和基于約束條件下的排隊論模型以及對兩道加工工序的改進(jìn)方法，最終確定了最優(yōu)的放料順序?yàn)?5281746，基于排隊論模型的加工順序增加了加工件數(shù)。運(yùn)用遺傳算法對兩道工序的加工方法進(jìn)行改進(jìn)，很大程度上提高了系統(tǒng)的工作效率。