基于改進(jìn)粒子群算法的智能RGV動(dòng)態(tài)調(diào)度模型

張宇翔 佘俊陽 鄭祥

摘 要：本文針對智能RGV的動(dòng)態(tài)調(diào)度問題進(jìn)行了相關(guān)研究。主要涉及兩個(gè)核心問題，第一是CNC對于兩道工序的分配，第二是兩道不同工序CNC的位置對RGV調(diào)度的影響，前者是為了使得兩道工序的供求保持平衡，減少無用工序;后者的核心是減少CNC的等待時(shí)間。首先在分析兩道生產(chǎn)工序?qū)τ谡{(diào)度策略的約束后，本文提出了三個(gè)約束條件;其次建立總體最短路約束模型，使用改進(jìn)的粒子群算法（PSO）對最短路進(jìn)行求解;最后帶入相關(guān)數(shù)據(jù)得到工序分配方案。

關(guān)鍵詞：智能RGV ; 動(dòng)態(tài)調(diào)度 ; 粒子群算法

引言

RGV是一種無人駕駛、能在固定軌道上自由運(yùn)行的智能車，擁有一個(gè)機(jī)械手臂，手臂上有兩個(gè)機(jī)械手爪用來完成上下料操作，還攜帶一個(gè)清洗槽用來完成清洗熟料的任務(wù)。由8臺(tái)計(jì)算機(jī)數(shù)控機(jī)床（ComputerNumberController，CNC）與1輛軌道式自動(dòng)引導(dǎo)車（RailGuideVehicle，RGV）、1條RGV直線軌道、1條上料傳送帶、1條下料傳送帶組成的智能加工系統(tǒng)需要一個(gè)動(dòng)態(tài)調(diào)度策略使得RGV完成上下料及清洗作業(yè)等任務(wù)。

1 .篩選CNC

首先需要考慮的是如何分配生產(chǎn)工序一以及工序二的CNC數(shù)量及位置。針對這個(gè)問題，可以采用線性規(guī)劃的方式來進(jìn)行優(yōu)化處理;如果工序一與工序二的總時(shí)間差最小，即可認(rèn)為此時(shí)是最優(yōu)解。

如果完成一個(gè)熟料需要兩道工序，想實(shí)現(xiàn)在每班作業(yè)中效益的最大化，就應(yīng)追求完成一個(gè)熟料所需要的平均最短時(shí)間;核心問題仍然未變：使得CNC的等待時(shí)間越短以及RGV的移動(dòng)時(shí)間最短。

為了使得CNC的等待時(shí)間最短，提出總體最短路規(guī)劃：

定義dpq表示第p臺(tái)加工工序一的CNC到第q臺(tái)加工工序二的CNC的距離。為了使RGV花費(fèi)在路徑上的時(shí)間最短，要求路徑的長度之和最小，得到以下目標(biāo)函數(shù)：

約束條件1：同一時(shí)間，一個(gè)生料只能在一臺(tái)CNC上進(jìn)行加工。

約束條件2： 同一時(shí)間，一臺(tái)CNC只能加工一個(gè)生料的一個(gè)工序。

約束條件3：后一道工序只能在前一道工序完成后才能開始。

2 . 粒子群算法

粒子群算法（PSO）是一種利用種群中個(gè)體間的信息共享與競爭學(xué)習(xí)來形成群智能并指導(dǎo)優(yōu)化搜索的算法。

第2步：利用個(gè)體粒子和適應(yīng)度函數(shù)，計(jì)算粒子的適應(yīng)度值。

第3步：利用更新方程對個(gè)體粒子的速度和位置進(jìn)行重新計(jì)算。

第4步：比較當(dāng)前粒子和歷史最優(yōu)粒子的適應(yīng)度值，若當(dāng)代粒子的適應(yīng)度值比歷史最優(yōu)適應(yīng)度值好，則用當(dāng)代的替代歷史最優(yōu)適應(yīng)度值;反之，歷史最優(yōu)適應(yīng)度值不變。

第5步：在歷史最優(yōu)適應(yīng)度值中選擇最小的一個(gè)作為全局最優(yōu)適應(yīng)度值，優(yōu)化過程中，若所有的粒子個(gè)體的適應(yīng)度值中最好的優(yōu)于當(dāng)代全局適應(yīng)度值，則更新適應(yīng)度值，反之，保持全局適應(yīng)度值不變。

第6步：確定優(yōu)化是否結(jié)束。若滿足最大優(yōu)化次數(shù)等于50，則優(yōu)化結(jié)束，輸出算法的優(yōu)化結(jié)果;若未滿足，則繼續(xù)優(yōu)化。

3 .模型求解

步驟一：利用非線性規(guī)劃求解分別完成兩道工序的CNC臺(tái)數(shù);

步驟二：根據(jù)工序多余量最低原則，搜索CNC處理工序，安排兩種處理兩種工序的CNC位置;

步驟三：以兩點(diǎn)間移動(dòng)時(shí)間為路長，利用粒子群算法確定一條路長以及CNC等待時(shí)間最短的路徑;

步驟四：對RGV按規(guī)劃路徑工作進(jìn)行仿真，計(jì)算出規(guī)定工作時(shí)間內(nèi)完成的物料數(shù)目。最終模型求解結(jié)果如下：

表中數(shù)字代表第一組物料第一道工序的CNC位置，0代表第二道工序的位置。

結(jié)論：

一個(gè)主要由8臺(tái)CNC與1輛RGV組成的智能加工系統(tǒng)需要一個(gè)動(dòng)態(tài)調(diào)度策略使得整個(gè)系統(tǒng)的效率最高。本文認(rèn)為調(diào)動(dòng)策略的核心的是追求效益的最大化，在每個(gè)生料有兩道生產(chǎn)工序且CNC不發(fā)生故障的情形下讓所有的CNC單位時(shí)間內(nèi)生產(chǎn)出最多的熟料。

參考文獻(xiàn)：

[1]李文，伍鐵斌，趙全友，李玲香.改進(jìn)的混沌粒子群算法在TSP中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用研究，2015，32（07）：2065-2067.

[2]薛斐. 基于多層編碼的遺傳-粒子群融合算法流水線優(yōu)化控制[D].西安科技大學(xué)，2015.