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

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

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

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

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

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

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

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

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

2 基于約束條件下的排隊(duì)論模型

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

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

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

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

綜上所述，通過(guò)就近原則的仿真得到對(duì)于一道工序的器件，在第一組生產(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)過(guò)程分析

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

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

（1）種群初始化

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

（2）選擇

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

最后計(jì)算每個(gè)人個(gè)體的選擇概率

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

（3）交叉

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

表1 有2個(gè)插入點(diǎn)的2個(gè)父?jìng)€(gè)體Table 1 Two Parents with Two Insertion Points

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

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

（4）變異

通過(guò)變異產(chǎn)生更多種類的個(gè)體，來(lái)局部?jī)?yōu)化[9]個(gè)體。

（5）判斷

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

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

4 結(jié)論

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