基于電量和負(fù)載均衡約束的多AGV生產(chǎn)車間調(diào)度研究

陳 晨，張緒美，梁曉磊，鄢 威

（1.武漢科技大學(xué) 汽車與交通工程學(xué)院，武漢 430081；2.武漢科技大學(xué) 機(jī)械傳動(dòng)與制造工程湖北省重點(diǎn)實(shí)驗(yàn)室，武漢 430081）

0 引言

制造業(yè)的不斷發(fā)展，對(duì)企業(yè)生產(chǎn)加工過程的優(yōu)化提出了更高的要求，如何提高生產(chǎn)效率，成為企業(yè)亟需解決的問題。通過使用自動(dòng)引導(dǎo)小車（aotomated guided vehicle，AGV）對(duì)生產(chǎn)進(jìn)行調(diào)度優(yōu)化，可以大大提高企業(yè)生產(chǎn)效率，但是同時(shí)又會(huì)產(chǎn)生一些新的問題，如：負(fù)載不均造成的擁堵問題，或者因?yàn)锳GV電量約束產(chǎn)生的充電問題等。因此對(duì)生產(chǎn)車間，進(jìn)行含有AGV的多目標(biāo)調(diào)度優(yōu)化，成為了目前的一個(gè)研究熱點(diǎn)。

在傳統(tǒng)的生產(chǎn)車間調(diào)度研究中，最直接的提高生產(chǎn)效率的方式就是減少調(diào)度的時(shí)間，因此有學(xué)者對(duì)AGV調(diào)度時(shí)間進(jìn)行了優(yōu)化研究，如：Mahalakshmi等[1]將最小化AGV的總提前以及延誤的總時(shí)間作為目標(biāo)時(shí)間，采用人工免疫算法，對(duì)調(diào)度進(jìn)行優(yōu)化，李西興等[2]將調(diào)度最短時(shí)間作為優(yōu)化目標(biāo)，采用鯨魚算法引入遺傳算法的操作，提高算法全局搜索策略，進(jìn)行優(yōu)化。而實(shí)際調(diào)度中除了考慮系統(tǒng)的整體調(diào)度時(shí)間，還需要考慮AGV在運(yùn)行中的路徑?jīng)_突問題對(duì)調(diào)度的影響，鄧希等[3]通過與A*算法結(jié)合的混合遺傳算法解決路徑?jīng)_突以及AGV調(diào)度問題，對(duì)不同小車進(jìn)行優(yōu)先級(jí)分配，結(jié)合是否空載對(duì)路徑進(jìn)行再次規(guī)劃。W等[4]通過調(diào)整不同AGV小車在搬運(yùn)中的運(yùn)行速度，優(yōu)化AGV在路徑上的重疊問題，利用一種高效的MapReduce框架提高系統(tǒng)的決策效率，解決AGV路徑?jīng)_突問題。郭昆侖等[5]考慮AGV作業(yè)時(shí)間，沖突距離等因素，建立了多AGV的無沖突路徑規(guī)劃模型。Umar等[6]提出了一種多目標(biāo)自適應(yīng)權(quán)重方法，利用混合模糊邏輯以及啟發(fā)式局部搜索算法對(duì)多目標(biāo)遺傳算法進(jìn)行改進(jìn)。通過優(yōu)化策略以及改進(jìn)算法，對(duì)AGV調(diào)度中的時(shí)間及路徑進(jìn)行優(yōu)化，可以提高系統(tǒng)的整體調(diào)度效率，而在加工車間中，除了AGV調(diào)度時(shí)間和路徑外還有很多其他因素會(huì)影響調(diào)度效率。

受AGV電池容量限制，在AGV運(yùn)行過程中，需要考慮AGV續(xù)航及充電等問題對(duì)調(diào)度的影響，針對(duì)帶有電池電量以及充電時(shí)間約束的AGV調(diào)度問題進(jìn)行研究，李錚峰等[7]建立了考慮充電的AGV搬運(yùn)模型，試驗(yàn)結(jié)果表明：搬運(yùn)時(shí)間越長對(duì)AGV充電的影響越大，AGV數(shù)量越多對(duì)AGV充電的影響反而會(huì)逐漸減小。Moussa等[8]以最小化完工時(shí)間為目標(biāo)，研究了不同的充電策略下，機(jī)器、AGV以及充電站的最佳安排方式，運(yùn)用基于GVNS的啟發(fā)式算法，優(yōu)化了AGV調(diào)度。同時(shí)隨著AGV數(shù)量的增加，系統(tǒng)還按照時(shí)間最優(yōu)的策略來進(jìn)行調(diào)度，就會(huì)產(chǎn)生負(fù)載不均的問題，這些問題主要分為三類：1）機(jī)器負(fù)載不均，即某工序的加工機(jī)器持續(xù)工作，而其他的機(jī)器負(fù)荷較少，會(huì)造成加工工件在某一機(jī)器前排隊(duì)；2）路網(wǎng)負(fù)載不均，如路網(wǎng)中有些節(jié)點(diǎn)經(jīng)過的AGV較少，另外一些節(jié)點(diǎn)則比較繁忙，可能會(huì)產(chǎn)生局部擁堵；3）AGV負(fù)載不均，即由于搬運(yùn)任務(wù)分配不均，導(dǎo)致一些AGV持續(xù)性工作，另外一些AGV間歇性工作，使得AGV間產(chǎn)生沖突的可能性增加，同時(shí)降低了AGV利用率。因此，在機(jī)器負(fù)載優(yōu)化中，Yuan等[9]將最大完工時(shí)間、總延誤、機(jī)器總負(fù)荷和總能耗最小作為目標(biāo)，建立了智能制造車間資源調(diào)度模型以及基于排序水平和擁擠度的評(píng)價(jià)函數(shù)，減輕了機(jī)器在生產(chǎn)中的負(fù)荷。鄒裕吉等[10]在時(shí)間和路徑的基礎(chǔ)上將機(jī)器總負(fù)荷也作為優(yōu)化目標(biāo)，通過優(yōu)化算法對(duì)車間集成調(diào)度問題進(jìn)行了研究。在路網(wǎng)負(fù)載優(yōu)化中，張得志等[11]在對(duì)AGV分揀系統(tǒng)的研究中發(fā)現(xiàn)AGV在某個(gè)時(shí)間的某個(gè)節(jié)點(diǎn)負(fù)載量不均衡是造成擁堵的主要原因，利用整數(shù)規(guī)劃優(yōu)化模型，對(duì)分揀系統(tǒng)負(fù)載量均衡做了優(yōu)化。在AGV負(fù)載優(yōu)化中，Udhayakumar等[12]根據(jù)平衡的工作負(fù)荷，利用遺傳算法來尋找兩臺(tái)自動(dòng)導(dǎo)引車的最優(yōu)的調(diào)度，平衡任務(wù)，提高了自動(dòng)導(dǎo)引車的利用率。

綜上所述，對(duì)于AGV車輛影響因素可以從這幾方面進(jìn)行考慮?，F(xiàn)階段的研究多偏向于機(jī)器以及路網(wǎng)負(fù)載不均兩方面，而在AGV負(fù)載均衡方面的研究，大多是通過對(duì)比AGV間不同的工作負(fù)荷，來重新分配調(diào)度任務(wù)，使每個(gè)AGV達(dá)到負(fù)載均衡，提高調(diào)度的整體效率。但在實(shí)際中，AGV負(fù)載不均對(duì)調(diào)度產(chǎn)生的影響不是孤立的，AGV續(xù)航時(shí)間不夠長或充電頻率太高都會(huì)對(duì)調(diào)度產(chǎn)生較大的影響，因此現(xiàn)階段將電池續(xù)航、充電問題與負(fù)載均衡問題結(jié)合，是十分有意義的。針對(duì)此問題，本文將在AGV續(xù)航有限且需要考慮充電，這兩個(gè)約束的基礎(chǔ)上，通過均衡性這一目標(biāo)，對(duì)調(diào)度進(jìn)行優(yōu)化，其中均衡性是指系統(tǒng)在調(diào)度分配過程中，平衡每輛AGV的分配任務(wù)數(shù)，使得每輛AGV執(zhí)行的任務(wù)量都基本相當(dāng)，其中每輛AGV任務(wù)量與所有AGV平均任務(wù)量的差值叫做均衡性偏差，偏差越小說明系統(tǒng)中每輛AGV間的任務(wù)量調(diào)度越優(yōu)。設(shè)計(jì)了AGV最小化最大運(yùn)行時(shí)間及最小化最大均衡偏差的雙目標(biāo)優(yōu)化模型，利用改進(jìn)的自適應(yīng)遺傳算法，提出了三段式的編碼方式，通過MFC（Minimum time selection for charged volume constraint）初始化策略，生成染色體后通過自適應(yīng)的交叉變異方式，對(duì)生產(chǎn)車間多AGV與機(jī)器進(jìn)行集成調(diào)度，根據(jù)不同的AGV數(shù)量對(duì)作業(yè)的影響[13]，研究了不同數(shù)量、不同電量的AGV在不同均衡性下的表現(xiàn)。

1 問題描述與建模

1.1 問題描述

生產(chǎn)車間調(diào)度問題一般為n件帶有加工工序約束的工件，在m臺(tái)機(jī)器上進(jìn)行加工，機(jī)器必須完成緊前工序才能進(jìn)行下一工件的加工，工件在機(jī)器之間的搬運(yùn)由多個(gè)AGV來完成，AGV的調(diào)度優(yōu)化是通過最大加工完成時(shí)間的最小值來實(shí)現(xiàn)。然而在AGV搬運(yùn)中每運(yùn)行單位距離都會(huì)消耗單位電量，因此AGV在調(diào)度前必須考慮有余電可以返回充電，同時(shí)充電中的AGV不能進(jìn)行搬運(yùn)。另外，在多個(gè)AGV調(diào)度時(shí)，會(huì)出現(xiàn)各AGV之間負(fù)載不均的情況，以此會(huì)造成出入口擁堵，以及部分AGV持續(xù)運(yùn)行，而另一部分AGV間歇性運(yùn)行，工況不均的問題。因此AGV的電量約束和負(fù)載均衡性是必須要考慮的兩個(gè)方面。參考了AGV在融合調(diào)度中的運(yùn)行方式[2]，使用兩段搬運(yùn)的方式，進(jìn)行搬運(yùn)。第一段搬運(yùn)為AGV先從當(dāng)前位置運(yùn)行至工件所在位置，第二段搬運(yùn)則再從工件所在位置運(yùn)行至目標(biāo)位置，按照最短路的原則進(jìn)行調(diào)度安排，設(shè)置了AGV任務(wù)均衡性的目標(biāo)函數(shù)，通過最小化均衡偏差值進(jìn)行優(yōu)化。

為了簡(jiǎn)化問題，存在以下假設(shè)：

1）AGV空載與負(fù)載搬運(yùn)速度相同且恒定，充電時(shí)間恒定。

2）機(jī)器之間的搬運(yùn)路線確定，不同機(jī)器只能加工對(duì)應(yīng)工件的對(duì)應(yīng)工序。

3）AGV一次只能搬運(yùn)一個(gè)工件，機(jī)器一次只能加工一個(gè)工件。

4）不考慮AGV之間產(chǎn)生的路徑?jīng)_突問題。

5）AGV和機(jī)器在零時(shí)刻都是可以用的。

6）AGV和工件都是從初始倉庫出發(fā)，且在初始位置充電。

7）AGV可用電量可等價(jià)為AGV剩余可用時(shí)間。

1.2 數(shù)學(xué)模型

1.2.1 變量定義

索引及參數(shù)：

n工件總數(shù)。

m工序總數(shù)。

GAGV總數(shù)。

SAGV搬運(yùn)任務(wù)總數(shù)。

K加工機(jī)器數(shù)。

i工件索引號(hào)；i∈{1,2,…,n}。

j工序索引號(hào)；j∈{1,2,…,m}。

gAGV索引號(hào)；g∈{1,2,…,G}。

sAGV搬運(yùn)數(shù)索引號(hào)；s∈{1,2,…,S}。

k加工機(jī)器索引號(hào)；k∈{1,2,…,K}。

ω加工時(shí)間與均衡偏差之間的權(quán)重。

λAGV完成最短搬運(yùn)時(shí)間任務(wù)并返回后剩余電量。

Oi,j工件i的第j道工序。

Ci,j加工工序Oij加工完成時(shí)間。

Di,j加工工序Oij加工開始時(shí)間。

Bk,k’工件從機(jī)器K搬運(yùn)到機(jī)器K’的時(shí)間。

TBi,jAGV每次搬運(yùn)時(shí)間。

HgN(AGV)g的第N次搬運(yùn)結(jié)束時(shí)間。

Pi,jAGV第二段搬運(yùn)開始時(shí)間。

Q一個(gè)很大的正整數(shù)。

Ng,s每個(gè)(AGV)g搬運(yùn)的總次數(shù)。

ENg(AGV)g在工序Oij結(jié)束后的第N次搬運(yùn)時(shí)的可用電量。

Gk,k’(AGV)g搬運(yùn)工序Oij開始搬運(yùn)時(shí)間。

TC充一次電的時(shí)間。

RAGV平均充電次數(shù)。

TAGV平均運(yùn)行時(shí)間。

決策變量：

1.2.2 模型建立

本文的總調(diào)度任務(wù)為確定各工件工序的加工順序，加工機(jī)器及搬運(yùn)AGV，平衡每輛AGV的負(fù)載，獲得各工件工序在機(jī)器上的最短加工完成時(shí)間。

優(yōu)化目標(biāo)1：選擇最小化最大加工完成時(shí)間。

優(yōu)化目標(biāo)2：最小化AGV的負(fù)載均衡偏差，使得每臺(tái)AGV分配的任務(wù)大致相當(dāng)。通過最小化每臺(tái)AGV實(shí)際任務(wù)量與AGV平均任務(wù)量間差的絕對(duì)值，來進(jìn)行計(jì)算。

優(yōu)化總目標(biāo)即為加工時(shí)間和AGV的均衡偏差最小。

工序加工完成時(shí)間等于工件的開始加工時(shí)間加上工件在機(jī)器上的加工時(shí)間。

工序加工開始時(shí)間等于工件的加工完成時(shí)間加上工件搬運(yùn)的時(shí)間，其中工件第一次加工完成時(shí)間等于其搬運(yùn)時(shí)間。

AGV的搬運(yùn)時(shí)間由AGV從當(dāng)前位置運(yùn)行至工件位置的時(shí)間以及從工件位置運(yùn)行至目標(biāo)機(jī)器位置的時(shí)間，以及AGV等待工件加工完成時(shí)間，三部分組成。

AGV在從工件所在位置運(yùn)行至目標(biāo)位置時(shí)的開始搬運(yùn)時(shí)間，即第二段搬運(yùn)開始時(shí)間，將AGV上一道搬運(yùn)的結(jié)束時(shí)間加上第一道搬運(yùn)時(shí)間與工件上一道加工結(jié)束時(shí)間作比較，得到二者中的較大值，作為第二段搬運(yùn)的開始時(shí)間，確保工件加工完成后再繼續(xù)搬運(yùn)。

AGV的搬運(yùn)結(jié)束時(shí)間。

工序Oi,j在搬運(yùn)完成后才能加工。

當(dāng)AGV要搬運(yùn)兩個(gè)不同的工件時(shí)，緊前工序能被先AGV搬運(yùn)，即保證在同一時(shí)刻，每個(gè)AGV只能搬運(yùn)一個(gè)工件。

一道工序只能且必須選擇一臺(tái)機(jī)器進(jìn)行加工。

同一道工序在緊前工序完成后才能進(jìn)行下一道工序的加工。

同一機(jī)器，在面對(duì)不同工序時(shí)遵循先進(jìn)先出原則，同時(shí)每個(gè)機(jī)器每次都只能加工一個(gè)工件。

機(jī)器只有在搬運(yùn)完成后才能加工。

每一個(gè)AGV的總搬運(yùn)次數(shù)。

AGV執(zhí)行完當(dāng)前搬運(yùn)任務(wù)后的電量。

判斷AGV剩余電量能否完成當(dāng)前最短時(shí)間的搬運(yùn)任務(wù)（minTBi,j）并能夠返回(Bk,1)。

AGV執(zhí)行完任務(wù)后，剩余電量可用時(shí)間大于返回充電樁所需時(shí)間。

AGV在充電時(shí)不能執(zhí)行任務(wù)。

AGV平均運(yùn)行時(shí)間

AGV平均充電次數(shù)。

2 算法設(shè)計(jì)

2.1 算法編碼

該問題分為工件工序分配，工序機(jī)器調(diào)度，AGV搬運(yùn)任務(wù)分配三個(gè)方面，因此利用了三層編碼的結(jié)構(gòu)，使用實(shí)數(shù)編碼的方式對(duì)染色體進(jìn)行設(shè)計(jì)：

如圖1所示，O表示的是工件的索引號(hào)，該索引號(hào)第幾次出現(xiàn)，就代表此時(shí)為該工件的第幾道工序，如O21代表工件2的第一道工序。M為對(duì)應(yīng)工序所選擇的機(jī)器，在可加工該工序的機(jī)器中的序號(hào)，K是其該序號(hào)代表的機(jī)器索引號(hào)。G對(duì)應(yīng)AGV小車的索引號(hào)，該索引號(hào)出現(xiàn)次數(shù)即為AGV執(zhí)行任務(wù)數(shù)。工序O21-O31-O11-O2-O22-O32-O33-O13-O23對(duì)應(yīng)的加工機(jī)器是K4-K2-K3-K5-K2-K4-K4-K2-K1，對(duì)應(yīng)搬運(yùn)的AGV為G1-G2-G3-G2-G1-G2-G1-G3-G2。O-M-AGV三段編碼的組合即為染色體的編碼方式。

圖1 染色體編碼

2.2 種群初始化

種群初始化的算子，將直接影響算法的收斂效率及搜索結(jié)果，本文在三層編碼結(jié)構(gòu)上，提出了一種基于AGV帶電量約束的最短時(shí)間選擇（Minimum time selection for charged volume constraint，MFC）的初始化方案，對(duì)工序O采用隨機(jī)生成策略，根據(jù)工序可加工機(jī)器M，選擇對(duì)應(yīng)AGV采用MFC策略。

MFC初始化步驟如下：

步驟1：定義工件對(duì)應(yīng)工序加工機(jī)器，機(jī)器加工時(shí)間，機(jī)器之間的搬運(yùn)路線，AGV電量，初始化當(dāng)前機(jī)器運(yùn)行時(shí)間，AGV運(yùn)行時(shí)間。

步驟2：隨機(jī)生成工件加工工序。

步驟3：按順序選取工序，根據(jù)工序選擇可加工序的機(jī)器，搬運(yùn)AGV。

步驟4：根據(jù)機(jī)器加工時(shí)間和AGV搬運(yùn)時(shí)間判斷電量是否滿足搬運(yùn)條件。如果不滿足則進(jìn)行判斷，若AGV余電小于閾值A(chǔ)GV需要返回充電，若AGV余電大于閾值，則等待下一次分配，如果多次電量超過閾值但無法分配，AGV需要返回充電，如果AGV要充電，本次搬運(yùn)時(shí)間需要加上充電時(shí)間，滿足則不需要充電。

步驟5：更新此機(jī)器及AGV的全局運(yùn)行時(shí)間，全局運(yùn)行時(shí)間由機(jī)器當(dāng)前運(yùn)行時(shí)間和此工序加工時(shí)間，AGV當(dāng)前運(yùn)行時(shí)間和AGV此工序搬運(yùn)時(shí)間組成。

步驟6：根據(jù)全局時(shí)間選擇最短時(shí)間，根據(jù)最短時(shí)間生成對(duì)應(yīng)的機(jī)器索引號(hào)和AGV索引號(hào)。

步驟7：更新機(jī)器時(shí)間表，AGV時(shí)間表，AGV剩余電量。跳至第二步繼續(xù)循環(huán)，直至所有工序被分配完成。

圖2使用MFC選擇策略根通過初始工序算子1122，以上步驟，得到的對(duì)應(yīng)機(jī)器編碼為1231，AGV編碼為2121，所以此基因編碼為112212312121。

圖2 初始化策略

2.3 適應(yīng)度函數(shù)

為了研究AGV工作的平衡性與調(diào)度時(shí)間之間的沖突關(guān)系，需要在兩個(gè)目標(biāo)之間分配不同的權(quán)重來進(jìn)行比較，再通過最小化調(diào)度時(shí)間與均衡偏差，來得到優(yōu)化結(jié)果。但是時(shí)間與均衡偏差不是同一個(gè)量綱，所以需要將其進(jìn)行標(biāo)準(zhǔn)化的處理，才能進(jìn)行計(jì)算，結(jié)合不同的數(shù)據(jù)標(biāo)準(zhǔn)化方法[14]，因比重法具有不改變?cè)u(píng)價(jià)對(duì)象內(nèi)部以及評(píng)價(jià)對(duì)象互相之間的差異性，縮放無關(guān)性等優(yōu)點(diǎn)，因此作為本文標(biāo)準(zhǔn)化的方法。適應(yīng)度函數(shù)將兩目標(biāo)分配權(quán)重后求最小值，i代表基于基因序號(hào)，n為總基因數(shù)。

2.4 交叉變異

算法采用自適應(yīng)交叉和變異的方法[15]，在種群適應(yīng)度值相對(duì)分散時(shí)，降低交叉和變異的概率，保護(hù)優(yōu)勢(shì)個(gè)體的生存。當(dāng)種群的個(gè)體適應(yīng)度值趨于相同或局部最優(yōu)時(shí)，增加交叉和變異的概率，避免產(chǎn)生局部最優(yōu)解。交叉概率和變異概率的公式為：

Pc,Pm是交叉與變異的概率，Pc1,Pc2,Pm1,Pm2是設(shè)定的參數(shù)，F(xiàn)min和-F分別是適應(yīng)度的最小值與平均值，F(xiàn),F’是分別是交叉染色體中適應(yīng)度值較大的個(gè)體適應(yīng)值及突變個(gè)體的適應(yīng)值。

種群采用單點(diǎn)交叉的方式，針對(duì)交叉產(chǎn)生的子代染色體不能保證工件號(hào)i有且僅出現(xiàn)ni次的問題進(jìn)行改進(jìn)，同時(shí)根據(jù)調(diào)整后的工序再調(diào)整機(jī)器和AGV。若需要調(diào)度的工件總數(shù)為n，工件ni對(duì)應(yīng)mj道工序，首先從種群中根據(jù)交叉概率選取兩條染色體，在染色體的前位中隨機(jī)選擇交叉點(diǎn)進(jìn)行單點(diǎn)交叉，交叉后某些工件的工序多余，某些工件的工序缺失，因此把工件工序多余的操作變?yōu)楣ぜば蛉笔У牟僮鳎凑战徊媲皞€(gè)體的操作機(jī)器和AGV，來調(diào)整位的加工機(jī)器，以及位的搬運(yùn)AGV。其操作如圖3所示。

圖3 交叉及修復(fù)

2.5 算法流程

本文整體的算法流程框架圖如圖4所示。算法在遺傳算法的基礎(chǔ)上，針對(duì)本模型提出了一種新的MFC初始化策略，使用隨機(jī)遍歷的方法進(jìn)行選擇，交叉變異概率進(jìn)行自適應(yīng)調(diào)整，進(jìn)行求解。

圖4 算法流程圖

3 實(shí)驗(yàn)分析

為了驗(yàn)證算法的有效性，實(shí)驗(yàn)使用下表所示實(shí)例進(jìn)行仿真實(shí)驗(yàn)。實(shí)例設(shè)置6個(gè)工件，每個(gè)工件對(duì)應(yīng)6道工序，在9臺(tái)機(jī)器上由分別由4、5、6臺(tái)AGV進(jìn)行搬運(yùn)，AGV電量分別設(shè)置為30、40、50、60，充電時(shí)間為10。表1表示的是機(jī)器編號(hào)，由工件與工序來確定，如(1,4)表示工件1的第4道工序可以在機(jī)器2上加工，也可以在機(jī)器9上加工。表2表示的是工件加工時(shí)間，由工序與機(jī)器來確定，如(1,4)表示工件1的第4道工序在機(jī)器2上加工時(shí)間為5，在機(jī)器9上的加工時(shí)間為4。AGV在不同機(jī)器間的搬運(yùn)時(shí)間如表3所示，其中0表示原材料倉庫，X表示成品倉庫，所有工件都將從0處出發(fā)，在工序結(jié)束后在X處卸載，如(1,2)表示AGV從0出發(fā)到1號(hào)機(jī)器需要時(shí)間為2。

表1 機(jī)器編號(hào)

表2 工件加工時(shí)間

表3 搬運(yùn)時(shí)間

3.1 算法有效性驗(yàn)證

實(shí)驗(yàn)首先與沒有改進(jìn)的遺傳算法行對(duì)比，從而驗(yàn)證算法的質(zhì)量。算法參數(shù)設(shè)置為種群規(guī)模N=50,迭代次數(shù)iteration=100，代溝GGAP=0.9，交叉率Pc1=0.7，Pc2=0.3，變異率Pm1=0.25，Pm2=0.18，AGV數(shù)量為6，電池容量為50，調(diào)度時(shí)間與均衡偏差權(quán)重比為1:1。

tGA算法表示采用傳統(tǒng)遺傳算法后的優(yōu)化結(jié)果，iGA算法表示改進(jìn)算法的優(yōu)化結(jié)果。圖5給出了在帶有充電約束的AGV調(diào)度中不同算法種群均值的變化情況。從圖中可以看出，iGA算法初始解就優(yōu)于tGA算法，收斂速度更快，同時(shí)iGA算法的完工時(shí)間是遠(yuǎn)遠(yuǎn)小于tGA算法的，即iGA算法具有更強(qiáng)的尋優(yōu)能力。

圖5 算法有效性對(duì)比

3.2 參數(shù)分析

在帶有AGV的車間調(diào)度問題中，AGV作為搬運(yùn)的主體，在AGV電量一定時(shí)，不同數(shù)量的AGV會(huì)影響搬運(yùn)任務(wù)的分配，同時(shí)當(dāng)AGV數(shù)量一定時(shí)，不同電量的AGV運(yùn)行時(shí)間不同，進(jìn)而對(duì)調(diào)度也產(chǎn)生很大的影響。因此接下來將通過AGV數(shù)量一定時(shí)不同電量AGV以及AGV電量一定時(shí)不同數(shù)量AGV，兩種情況下各自有什么樣的表現(xiàn)，分別觀察這兩個(gè)條件對(duì)調(diào)度的影響。

本文的算例是在車間調(diào)度經(jīng)典算例FT06的基礎(chǔ)上進(jìn)行的拓展，附加了AGV的數(shù)量與電量等相關(guān)數(shù)據(jù)，采用文獻(xiàn)[2]中對(duì)測(cè)試算例AGV與機(jī)器數(shù)量比例安排規(guī)則，選取AGV數(shù)量與機(jī)器數(shù)量比例為1:2，得到AGV數(shù)量應(yīng)設(shè)置為5輛，為了研究不同數(shù)量AGV的影響，添加數(shù)量單位為1的左右鄰域，將AGV數(shù)量分別設(shè)置為4、5、6輛。為了保證搬運(yùn)需求，故設(shè)置AGV數(shù)量為6，先分析了不同容量電池對(duì)調(diào)度的影響，找到最優(yōu)的電池容量，在此基礎(chǔ)上，再研究不同數(shù)量AGV對(duì)調(diào)度影響。在考慮如何設(shè)置權(quán)重比時(shí)，參考了Udhayakumar[12]的權(quán)重比設(shè)置方案，此方案能確保AGV可以在負(fù)載平衡和搬運(yùn)時(shí)間最短的條件下，找到一個(gè)接近最優(yōu)的調(diào)度方式。本文在此方案的基礎(chǔ)上進(jìn)行分析，通過前期實(shí)驗(yàn)發(fā)現(xiàn)，AGV負(fù)載均衡與最短調(diào)度時(shí)間之間是一組非線性沖突關(guān)系，在調(diào)度時(shí)間最短時(shí)AGV的負(fù)載均衡性最差，因此先研究了在權(quán)重比ω1:ω2為1:0時(shí)，即在時(shí)間最短條件下的調(diào)度情況作為參考，同時(shí)在原方案基礎(chǔ)上向左右兩個(gè)方向上拓展權(quán)重比，再與權(quán)重比為1：0時(shí)進(jìn)行參考，發(fā)現(xiàn)在權(quán)重比在7:1-1:7內(nèi)，整體調(diào)度影響不大，均衡性卻發(fā)生了顯著變化，因此將接下來的的權(quán)重比變化設(shè)置為7:1-1:7。

表4是AGV數(shù)量為6時(shí)，不同電池容量的AGV的實(shí)驗(yàn)結(jié)果。表5則給出了電量為50的不同數(shù)量的AGV，在考慮任務(wù)均衡條件下的總體調(diào)度時(shí)間F1、均衡性偏差F2、AGV平均充電次數(shù)R、AGV運(yùn)平均行時(shí)間T的實(shí)驗(yàn)結(jié)果。

表4 不同容量電池實(shí)驗(yàn)結(jié)果

表5 不同數(shù)量AGV實(shí)驗(yàn)結(jié)果

3.2.1 AGV電池容量分析

表4中加粗部分即為均衡偏差變化達(dá)到高峰的位置，從表中可以看到在電池容量為50或60時(shí)，對(duì)應(yīng)權(quán)重比為1:1-1:2階段，在電池容量為40或30時(shí)，對(duì)應(yīng)權(quán)重比為1:2-1:3階段。在此實(shí)例下可以看出50電池容量AGV是轉(zhuǎn)折點(diǎn)，這是因?yàn)榈陀?0容量后，由于在任務(wù)不變的情況下加大了AGV的任務(wù)量，導(dǎo)致充電頻次急劇增大，且由圖6可以看出，當(dāng)電池容量由60轉(zhuǎn)化為50后，充電頻率在0-1之間，50減少至40后，充電頻率在2-3.5之間，40減少至30后，充電頻率在5-6.5之間，容量平均每減少10，頻率增加的次數(shù)卻不呈平均增加。

圖6 AGV充電頻率

從AGV的單個(gè)平均運(yùn)行時(shí)間上也可以看出，容量為60的AGV在搬運(yùn)時(shí)間上比容量為50的AGV僅降低了5%左右，但是容量為40的的AGV相比容量為30的AGV則降低了17%。說明不同電池容量的AGV，由于充電頻率的惡化，導(dǎo)致搬運(yùn)時(shí)間會(huì)突然增加，因此其調(diào)度時(shí)間和任務(wù)均衡偏差的權(quán)值也會(huì)隨之變化，而不再是某一確定的值。根據(jù)表4比較調(diào)度時(shí)間，可以看出在權(quán)重比為1:2時(shí)，電池容量為50的AGV僅比容量為60的AGV平均調(diào)度時(shí)間增加5.4%，整體調(diào)度時(shí)間增加了1.73%，這說明使用容量為50的AGV即可基本實(shí)現(xiàn)搬運(yùn)優(yōu)化，繼續(xù)增大電池容量，并不能明顯提升AGV的搬運(yùn)效率。

3.2.2 AGV數(shù)量影響分析

從表5可以看出，隨著均衡偏差權(quán)重的增加調(diào)度的時(shí)間會(huì)逐漸增加，均衡偏差的值逐漸減小，這說明AGV的任務(wù)分配越來越均衡，同時(shí)AGV充電時(shí)間和搬運(yùn)時(shí)間會(huì)有一定的增加。AGV數(shù)量一定，如當(dāng)AGV數(shù)量為6時(shí)，權(quán)重在調(diào)度時(shí)間與均衡性之間的影響如圖7所示，均衡性變化通過后一權(quán)重均衡性偏差值較前一均衡偏差值的減少量來觀察，時(shí)間變化率為后一權(quán)重的調(diào)度時(shí)間相對(duì)前一時(shí)間的增加速度，可以看出均衡偏差的變化率與時(shí)間變化率都呈現(xiàn)出先增后減的趨勢(shì)，而時(shí)間的變化率較均衡偏差的變化會(huì)遲一步，在權(quán)重為1：1時(shí)均衡性的變化達(dá)到最高峰，在權(quán)重比為1:2時(shí)，時(shí)間變化率達(dá)到高峰。說明在AGV數(shù)量一定時(shí)，不同的權(quán)重對(duì)調(diào)度產(chǎn)生的影響是不同的，在某一權(quán)重下在達(dá)到均衡偏差值變化最大的同時(shí)，避免了時(shí)間變化率最大導(dǎo)致調(diào)度時(shí)間增加過多的問題。

圖7 均衡性和時(shí)間變化

同時(shí)通過表5可以看出，在權(quán)重比為1:1時(shí)，相對(duì)于不考慮均衡性的情況調(diào)度時(shí)間僅增加了5.4%，但是均衡性卻大大提升。圖8為均衡偏差值的變化，可以明顯的看出在不同數(shù)量的AGV其均衡性變化規(guī)律都是，都是隨著均衡偏差權(quán)重的增加，均衡偏差的值呈現(xiàn)出先緩慢減小在權(quán)重比為1:2時(shí)突然降低，隨后再緩慢減小至0的一個(gè)過程，同時(shí)在這個(gè)過程中，均衡性的變化會(huì)先達(dá)到最大，隨后在下一階段時(shí)間的增加率會(huì)達(dá)到最大，如表5中加粗部分所示，不同數(shù)量的AGV不會(huì)對(duì)此權(quán)重產(chǎn)生影響。

圖8 不同AGV均衡性變化

4 結(jié)語

本文針對(duì)帶有電量約束條件下的AGV任務(wù)分配不均問題，通過建立帶有最小化最大完工時(shí)間以及最小化均衡偏差的雙目標(biāo)優(yōu)化模型，利用一種改進(jìn)的自適應(yīng)遺傳算法，研究了相同電池容量下不同數(shù)量的AGV，以及相同數(shù)量下不同電池容量AGV，在不同權(quán)重中下如何能夠均衡每輛小車的任務(wù)量。得到結(jié)論如下：

1）AGV隨著均衡偏差權(quán)重的增加，均衡性的變化率呈現(xiàn)出先增后減的趨勢(shì)，而時(shí)間的變化率較均衡性的變化會(huì)遲一步。

2）針對(duì)不同數(shù)量AGV，在電量相同的情況下，應(yīng)選擇權(quán)重在1:1至1:2之間進(jìn)行優(yōu)化。

3）AGV數(shù)量相同的情況下，由于充電問題，調(diào)度優(yōu)化的結(jié)果會(huì)隨著電池電量的減少急劇惡化。

本文是在AGV電量或者數(shù)量一定時(shí)，通過改變另一個(gè)量來對(duì)這種綜合性調(diào)度問題進(jìn)行研究。但在AGV數(shù)量和電量都不確定時(shí)，考慮在調(diào)度時(shí)間最短的基礎(chǔ)上，如何均衡AGV的負(fù)載，本文還尚未考慮，因此將作為接下來的研究重點(diǎn)。