基于電量和負載均衡約束的多AGV生產車間調度研究

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

（1.武漢科技大學 汽車與交通工程學院，武漢 430081；2.武漢科技大學 機械傳動與制造工程湖北省重點實驗室，武漢 430081）

0 引言

制造業的不斷發展，對企業生產加工過程的優化提出了更高的要求，如何提高生產效率，成為企業亟需解決的問題。通過使用自動引導小車（aotomated guided vehicle，AGV）對生產進行調度優化，可以大大提高企業生產效率，但是同時又會產生一些新的問題，如：負載不均造成的擁堵問題，或者因為AGV電量約束產生的充電問題等。因此對生產車間，進行含有AGV的多目標調度優化，成為了目前的一個研究熱點。

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

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

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

1 問題描述與建模

1.1 問題描述

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

為了簡化問題，存在以下假設：

1）AGV空載與負載搬運速度相同且恒定，充電時間恒定。

2）機器之間的搬運路線確定，不同機器只能加工對應工件的對應工序。

3）AGV一次只能搬運一個工件，機器一次只能加工一個工件。

4）不考慮AGV之間產生的路徑沖突問題。

5）AGV和機器在零時刻都是可以用的。

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

7）AGV可用電量可等價為AGV剩余可用時間。

1.2 數學模型

1.2.1 變量定義

索引及參數：

n工件總數。

m工序總數。

GAGV總數。

SAGV搬運任務總數。

K加工機器數。

i工件索引號；i∈{1,2,…,n}。

j工序索引號；j∈{1,2,…,m}。

gAGV索引號；g∈{1,2,…,G}。

sAGV搬運數索引號；s∈{1,2,…,S}。

k加工機器索引號；k∈{1,2,…,K}。

ω加工時間與均衡偏差之間的權重。

λAGV完成最短搬運時間任務并返回后剩余電量。

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

Ci,j加工工序Oij加工完成時間。

Di,j加工工序Oij加工開始時間。

Bk,k’工件從機器K搬運到機器K’的時間。

TBi,jAGV每次搬運時間。

HgN(AGV)g的第N次搬運結束時間。

Pi,jAGV第二段搬運開始時間。

Q一個很大的正整數。

Ng,s每個(AGV)g搬運的總次數。

ENg(AGV)g在工序Oij結束后的第N次搬運時的可用電量。

Gk,k’(AGV)g搬運工序Oij開始搬運時間。

TC充一次電的時間。

RAGV平均充電次數。

TAGV平均運行時間。

決策變量：

1.2.2 模型建立

本文的總調度任務為確定各工件工序的加工順序，加工機器及搬運AGV，平衡每輛AGV的負載，獲得各工件工序在機器上的最短加工完成時間。

優化目標1：選擇最小化最大加工完成時間。

優化目標2：最小化AGV的負載均衡偏差，使得每臺AGV分配的任務大致相當。通過最小化每臺AGV實際任務量與AGV平均任務量間差的絕對值，來進行計算。

優化總目標即為加工時間和AGV的均衡偏差最小。

工序加工完成時間等于工件的開始加工時間加上工件在機器上的加工時間。

工序加工開始時間等于工件的加工完成時間加上工件搬運的時間，其中工件第一次加工完成時間等于其搬運時間。

AGV的搬運時間由AGV從當前位置運行至工件位置的時間以及從工件位置運行至目標機器位置的時間，以及AGV等待工件加工完成時間，三部分組成。

AGV在從工件所在位置運行至目標位置時的開始搬運時間，即第二段搬運開始時間，將AGV上一道搬運的結束時間加上第一道搬運時間與工件上一道加工結束時間作比較，得到二者中的較大值，作為第二段搬運的開始時間，確保工件加工完成后再繼續搬運。

AGV的搬運結束時間。

工序Oi,j在搬運完成后才能加工。

當AGV要搬運兩個不同的工件時，緊前工序能被先AGV搬運，即保證在同一時刻，每個AGV只能搬運一個工件。

一道工序只能且必須選擇一臺機器進行加工。

同一道工序在緊前工序完成后才能進行下一道工序的加工。

同一機器，在面對不同工序時遵循先進先出原則，同時每個機器每次都只能加工一個工件。

機器只有在搬運完成后才能加工。

每一個AGV的總搬運次數。

AGV執行完當前搬運任務后的電量。

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

AGV執行完任務后，剩余電量可用時間大于返回充電樁所需時間。

AGV在充電時不能執行任務。

AGV平均運行時間

AGV平均充電次數。

2 算法設計

2.1 算法編碼

該問題分為工件工序分配，工序機器調度，AGV搬運任務分配三個方面，因此利用了三層編碼的結構，使用實數編碼的方式對染色體進行設計：

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

圖1 染色體編碼

2.2 種群初始化

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

MFC初始化步驟如下：

步驟1：定義工件對應工序加工機器，機器加工時間，機器之間的搬運路線，AGV電量，初始化當前機器運行時間，AGV運行時間。

步驟2：隨機生成工件加工工序。

步驟3：按順序選取工序，根據工序選擇可加工序的機器，搬運AGV。

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

步驟5：更新此機器及AGV的全局運行時間，全局運行時間由機器當前運行時間和此工序加工時間，AGV當前運行時間和AGV此工序搬運時間組成。

步驟6：根據全局時間選擇最短時間，根據最短時間生成對應的機器索引號和AGV索引號。

步驟7：更新機器時間表，AGV時間表，AGV剩余電量。跳至第二步繼續循環，直至所有工序被分配完成。

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

圖2 初始化策略

2.3 適應度函數

為了研究AGV工作的平衡性與調度時間之間的沖突關系，需要在兩個目標之間分配不同的權重來進行比較，再通過最小化調度時間與均衡偏差，來得到優化結果。但是時間與均衡偏差不是同一個量綱，所以需要將其進行標準化的處理，才能進行計算，結合不同的數據標準化方法[14]，因比重法具有不改變評價對象內部以及評價對象互相之間的差異性，縮放無關性等優點，因此作為本文標準化的方法。適應度函數將兩目標分配權重后求最小值，i代表基于基因序號，n為總基因數。

2.4 交叉變異

算法采用自適應交叉和變異的方法[15]，在種群適應度值相對分散時，降低交叉和變異的概率，保護優勢個體的生存。當種群的個體適應度值趨于相同或局部最優時，增加交叉和變異的概率，避免產生局部最優解。交叉概率和變異概率的公式為：

Pc,Pm是交叉與變異的概率，Pc1,Pc2,Pm1,Pm2是設定的參數，Fmin和-F分別是適應度的最小值與平均值，F,F’是分別是交叉染色體中適應度值較大的個體適應值及突變個體的適應值。

種群采用單點交叉的方式，針對交叉產生的子代染色體不能保證工件號i有且僅出現ni次的問題進行改進，同時根據調整后的工序再調整機器和AGV。若需要調度的工件總數為n，工件ni對應mj道工序，首先從種群中根據交叉概率選取兩條染色體，在染色體的前位中隨機選擇交叉點進行單點交叉，交叉后某些工件的工序多余，某些工件的工序缺失，因此把工件工序多余的操作變為工件工序缺失的操作，并按照交叉前個體的操作機器和AGV，來調整位的加工機器，以及位的搬運AGV。其操作如圖3所示。

圖3 交叉及修復

2.5 算法流程

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

圖4 算法流程圖

3 實驗分析

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

表1 機器編號

表2 工件加工時間

表3 搬運時間

3.1 算法有效性驗證

實驗首先與沒有改進的遺傳算法行對比，從而驗證算法的質量。算法參數設置為種群規模N=50,迭代次數iteration=100，代溝GGAP=0.9，交叉率Pc1=0.7，Pc2=0.3，變異率Pm1=0.25，Pm2=0.18，AGV數量為6，電池容量為50，調度時間與均衡偏差權重比為1:1。

tGA算法表示采用傳統遺傳算法后的優化結果，iGA算法表示改進算法的優化結果。圖5給出了在帶有充電約束的AGV調度中不同算法種群均值的變化情況。從圖中可以看出，iGA算法初始解就優于tGA算法，收斂速度更快，同時iGA算法的完工時間是遠遠小于tGA算法的，即iGA算法具有更強的尋優能力。

圖5 算法有效性對比

3.2 參數分析

在帶有AGV的車間調度問題中，AGV作為搬運的主體，在AGV電量一定時，不同數量的AGV會影響搬運任務的分配，同時當AGV數量一定時，不同電量的AGV運行時間不同，進而對調度也產生很大的影響。因此接下來將通過AGV數量一定時不同電量AGV以及AGV電量一定時不同數量AGV，兩種情況下各自有什么樣的表現，分別觀察這兩個條件對調度的影響。

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

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

表4 不同容量電池實驗結果

表5 不同數量AGV實驗結果

3.2.1 AGV電池容量分析

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

圖6 AGV充電頻率

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

3.2.2 AGV數量影響分析

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

圖7 均衡性和時間變化

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

圖8 不同AGV均衡性變化

4 結語

本文針對帶有電量約束條件下的AGV任務分配不均問題，通過建立帶有最小化最大完工時間以及最小化均衡偏差的雙目標優化模型，利用一種改進的自適應遺傳算法，研究了相同電池容量下不同數量的AGV，以及相同數量下不同電池容量AGV，在不同權重中下如何能夠均衡每輛小車的任務量。得到結論如下：

1）AGV隨著均衡偏差權重的增加，均衡性的變化率呈現出先增后減的趨勢，而時間的變化率較均衡性的變化會遲一步。

2）針對不同數量AGV，在電量相同的情況下，應選擇權重在1:1至1:2之間進行優化。

3）AGV數量相同的情況下，由于充電問題，調度優化的結果會隨著電池電量的減少急劇惡化。

本文是在AGV電量或者數量一定時，通過改變另一個量來對這種綜合性調度問題進行研究。但在AGV數量和電量都不確定時，考慮在調度時間最短的基礎上，如何均衡AGV的負載，本文還尚未考慮，因此將作為接下來的研究重點。