基于遺傳算法的RGV動(dòng)態(tài)調(diào)度模型

伊新銅　王紅雨　李文娟

摘 要：本文針對(duì)基于CNC和RGV構(gòu)成的智能加工系統(tǒng)的動(dòng)態(tài)調(diào)度進(jìn)行了詳細(xì)研究，分別建立了1道工序無故障的動(dòng)態(tài)優(yōu)化模型，并分別利用貪心算法和遺傳算法對(duì)所建優(yōu)化模型進(jìn)行求解。

關(guān)鍵詞：動(dòng)態(tài)調(diào)度模型；遺傳算法；搜索樹

DOI：10.16640/j.cnki.37-1222/t.2019.15.129

有8臺(tái)CNC和1輛REV小車構(gòu)成的一般智能RGV加工系統(tǒng)，RGV作為RGV加工系統(tǒng)中的主要作業(yè)設(shè)備，其運(yùn)輸線路對(duì)整個(gè)系統(tǒng)的工作效率有很大的影響。假設(shè)8臺(tái)CNC對(duì)有n（n=1）道工序的物料進(jìn)行加工，建立動(dòng)態(tài)優(yōu)化模型，目標(biāo)函數(shù)為使得智能RGV加工系統(tǒng)在一個(gè)班次內(nèi)生產(chǎn)的熟料個(gè)數(shù)最多，即所有CNC空閑狀態(tài)的時(shí)長最少。同樣時(shí)間內(nèi)，在滿足約束條件的情況下移動(dòng)時(shí)間的減少可使得對(duì)CNC作業(yè)的數(shù)量盡可能多，可達(dá)到CNC空閑狀態(tài)的時(shí)長最少的目的，此動(dòng)態(tài)優(yōu)化模型的目標(biāo)函數(shù)轉(zhuǎn)化為求RGV移動(dòng)路徑最短的問題。

考慮到一般RGV動(dòng)態(tài)調(diào)度模型的調(diào)度機(jī)制，RGV車對(duì)系統(tǒng)調(diào)度的影響主要為RGV車的行走問題上，CNC僅參與物料的加工以及對(duì)RGV發(fā)送需求信號(hào)，RGV作為RGV加工系統(tǒng)中的主要作業(yè)設(shè)備，其運(yùn)輸線路對(duì)整個(gè)系統(tǒng)的工作效率有很大的影響。并且假設(shè)每臺(tái)CNC前的傳送帶提供物料量足夠大的情況下，只對(duì)物料的開始加工時(shí)間有影響，在物料加工時(shí)間內(nèi)RGV車可以繼續(xù)為其他CNC服務(wù)，并且RGV距發(fā)送需求信號(hào)CNC的距離對(duì)物料加工線路的選擇也有一定的影響。

要使RGV系統(tǒng)作業(yè)效率盡可能提高，即令所有CNC空閑狀態(tài)時(shí)間盡可能減少，CNC等待的時(shí)間最少同時(shí)也是RGV移動(dòng)路徑最短，則需使RGV小車對(duì)發(fā)出需求指令的CNC確定進(jìn)行作業(yè)的順序。本組同學(xué)采用建立三層的搜索樹的方法尋找全局最優(yōu)線路。同樣時(shí)間內(nèi)，移動(dòng)時(shí)間的減少可使得同樣時(shí)間內(nèi)對(duì)CNC作業(yè)的數(shù)量盡可能多，從而處于空閑狀態(tài)的CNC少；對(duì)于有n（n=1）道加工工序的物料，將RGV的工作狀態(tài)分為第道工序進(jìn)行上下料幾個(gè)作業(yè)狀態(tài)，并考慮到n道加工順序和CNC出現(xiàn)故障后維修時(shí)間的連續(xù)性，找到一種可行的調(diào)度方案，使CNC在時(shí)間約束下空閑時(shí)間最小。

1 符號(hào)說明

2 模型假設(shè)

（1）CNC系統(tǒng)在整個(gè)系統(tǒng)運(yùn)行過程中，保持正常運(yùn)行；

（2）RGV調(diào)度系統(tǒng)無故障，可實(shí)時(shí)了解材料加工情況和RGV的實(shí)時(shí)位置。

3 模型的建立與求解

假定在8臺(tái)CNC上加工且CNC發(fā)生故障的概率約為1%，每件物料加工完成有相同的n（n=1，2）道工序，有一臺(tái)RGV在加工系統(tǒng)中作業(yè)，RGV在運(yùn)輸過程中按照規(guī)定的路線行駛。

約束條件為：

（1）第i個(gè)CNC空閑狀態(tài)的時(shí)間為從系統(tǒng)運(yùn)行到結(jié)束，此次加工完成時(shí)間到下一次RGV為其上下料作業(yè)時(shí)間差的和；

（2）對(duì)于第i個(gè)CNC來說，第k次加工完成時(shí)間到下一次RGV為其上下料的時(shí)間差大于等于0；

（3）智能加工系統(tǒng)作業(yè)的時(shí)長為一個(gè)班次，為8小時(shí)；

（4）RGV在直線軌道上移動(dòng)，可連續(xù)移動(dòng)1個(gè)單位（兩臺(tái)相鄰CNC間的距離）、2個(gè)單位（三臺(tái)相鄰CNC間的距離）和3個(gè)單位（四臺(tái)相鄰CNC間的距離）；

（5）對(duì)于2道加工工序，8臺(tái)CNC的分配根據(jù)加工第i道工序所用時(shí)間與加工完成所有工序時(shí)間的按比例分配加工第i道工序CNC數(shù)量為；

（6）CNC發(fā)生故障的概率約為1%，每次故障排除時(shí)間介于10～20分鐘之間，未完成的物料報(bào)廢。

調(diào)度的目標(biāo)為在給定約束條件下，CNC加工完成的熟料最多，即所有CNC空閑狀態(tài)時(shí)間最少。按照問題描述所建立的數(shù)學(xué)模型如下：

式中表示在整個(gè)系統(tǒng)工作工程中，某一時(shí)刻的時(shí)間；表示RGV位置的隨著時(shí)間的變化；表示編號(hào)為i的CNC發(fā)生故障的概率；表示2道加工工序中，用于加工第j道工序的CNC數(shù)量，表示CNC加工完成一個(gè)多道工序物料的第j道工序所需時(shí)間，即對(duì)8臺(tái)CNC進(jìn)行按比例分配，加工第j道工序所需時(shí)間越長，則用于加工第j道工序的CNC越多，根據(jù)實(shí)際情況分析此分配方案是合理的。

模型中，式（1）表示極小化所有CNC的空閑狀態(tài)時(shí)間；式（2）為編號(hào)為i的CNC空閑時(shí)間的表示；式（3）保證了第k次加工完成時(shí)間到下一次RGV為其上下料的時(shí)間差大于等于0；式（4）和式（5）分別保證了整個(gè)智能加工系統(tǒng)作業(yè)的時(shí)長為一個(gè)班次、RGV在RGV直線軌道上移動(dòng)；式（6）保證了在2道工序物料加工情況下，用于加工第j道工序的CNC數(shù)量分配的合理性。

4 模型結(jié)果分析

本文中一共建立了個(gè)2相關(guān)的模型，一道工序模型開始的8個(gè)順序1，2，7，8，4，3，6，5，通過運(yùn)行算法輸出第一組、第二組、第三組產(chǎn)出熟料的數(shù)量分別為371、346、371。

參考文獻(xiàn)：

[1]孫志峻，朱劍英.含機(jī)器人的作業(yè)車間雙資源智能優(yōu)化調(diào)度[J].機(jī)器人，2002，24（07）：342-345.

[2]李敏強(qiáng)，寇紀(jì)淞，林丹等.遺傳算法的基本理論與應(yīng)用[M].北京：科學(xué)出版社，2002.