任乃飛，于　璐

(江蘇大學(xué) 機(jī)械工程學(xué)院，江蘇 鎮(zhèn)江 212000)

基于混合遺傳算法的協(xié)同制造系統(tǒng)調(diào)度研究

任乃飛，于璐

(江蘇大學(xué) 機(jī)械工程學(xué)院，江蘇 鎮(zhèn)江 212000)

摘要研究由多個加工站、一個集中物料存儲區(qū)和一臺自動引導(dǎo)小車(AGV)組成的協(xié)同制造系統(tǒng)調(diào)度問題。針對該調(diào)度問題，建立了工件和AGV調(diào)度集成的數(shù)學(xué)模型。提出一種改進(jìn)的混合遺傳算法，在標(biāo)準(zhǔn)遺傳算法的基礎(chǔ)上引入模擬退火算法的Boltzmann生存機(jī)制，加快了算法收斂速度，克服了遺傳算法過早收斂的缺陷，同時對算法的變異、交叉算子和更新機(jī)制進(jìn)行了改進(jìn)。仿真實驗表明，改進(jìn)的混合遺傳算法能有效優(yōu)化作業(yè)順序和AGV行走路徑，為具有AGV約束的柔性生產(chǎn)調(diào)度提供一種有效的實踐途徑。

關(guān)鍵詞混合遺傳算法；自動引導(dǎo)小車；生產(chǎn)調(diào)度；協(xié)同制造系統(tǒng)；計算機(jī)仿真

隨著人們對多品種小批量產(chǎn)品的需求急劇增加，而傳統(tǒng)的大批量生產(chǎn)模式已不再滿足此類需求。因此，適合多品種生產(chǎn)的協(xié)同制造系統(tǒng)(Collaborative Manufacturing System，CMS)逐漸成為制造業(yè)的重要生產(chǎn)模式。自動引導(dǎo)小車(Automatic Guided Vehicle，AGV)作為協(xié)同制造系統(tǒng)的一部分，其主要功能是搬運工件，按照不同順序執(zhí)行任務(wù)，對系統(tǒng)的運行效率會有較大影響。因此，在協(xié)同制造系統(tǒng)中需要采用高效的調(diào)度算法對AGV和工件進(jìn)行綜合調(diào)度，以此優(yōu)化作業(yè)順序和AGV任務(wù)執(zhí)行順序。這對節(jié)省制造成本、縮短生產(chǎn)周期和提高系統(tǒng)生產(chǎn)效率具有重要意義。

目前，國內(nèi)外對AGV應(yīng)用于實際生產(chǎn)的相關(guān)研究主要集中在算法對AGV全局路徑的優(yōu)化和多AGV調(diào)度等方面[1]。但建立起AGV調(diào)度與工件調(diào)度相集成的調(diào)度模型，并采用智能算法進(jìn)行調(diào)度優(yōu)化的研究較少。文獻(xiàn)[2]對靜態(tài)環(huán)境下的AGV行走路徑進(jìn)行建模，并采用遺傳算法對該模型進(jìn)行路徑規(guī)劃。文獻(xiàn)[3]通過比較遺傳算子的性能，最終得到了AGV路徑規(guī)劃的優(yōu)化參數(shù)。文獻(xiàn)[4]建立了復(fù)雜約束的AGV多參數(shù)問題數(shù)學(xué)模型，采用混合遺傳算法優(yōu)化了調(diào)度總時間。文獻(xiàn)[5]針對多AGV系統(tǒng)，提出了一種基于階段控制策略的分布式控制算法，有效提高了多AGV系統(tǒng)的工作穩(wěn)定性。

本文對具有單AGV約束的協(xié)同制造系統(tǒng)調(diào)度問題進(jìn)行分析，建立了該問題的優(yōu)化模型，實現(xiàn)了工件與單AGV的集成化調(diào)度。針對標(biāo)準(zhǔn)遺傳算法的不足，采用了將模擬退火算法中的Boltzmann生存機(jī)制引入遺傳算法的遺傳、交叉操作的結(jié)合方式，以此控制子代染色體的選擇，并對標(biāo)準(zhǔn)遺傳算法的交叉、變異算子進(jìn)行改進(jìn)。

1問題描述

協(xié)同制造系統(tǒng)的車間調(diào)度問題描述：n個工件在f臺設(shè)備上完成加工，每個工件都有j道工序。各工序的加工時間和加工次序已知。加工過程中有一臺AGV小車進(jìn)行工件搬運任務(wù)。調(diào)度目標(biāo)為：確定每臺加工設(shè)備上的加工工件排序和每道工序的初始加工時間，使系統(tǒng)的最大完工時間(Makespan)最小。

該調(diào)度問題包含的約束條件如下：(1)在零時刻，各加工設(shè)備都可用，物料存儲區(qū)的所有工件都可被加工；(2)開始加工之前，AGV小車?？吭谖锪洗鎯^(qū)；當(dāng)AGV完成當(dāng)前搬運任務(wù)時，就?？吭趧倛?zhí)行完任務(wù)的加工站旁，等待下一個任務(wù)的開始；(3)同一時刻，每臺設(shè)備僅能加工一個工件，且一旦開始就不可中斷；(4)工件每道工序的加工時間已確定，且每道工序的開始和結(jié)束均會有安裝和卸載時間；(5)AGV小車一次只能搬運一個工件；(6)AGV的行走速度為勻速，且在每臺加工設(shè)備上的安裝時間和卸載時間相同。

此外，假設(shè)AGV每一次搬運任務(wù)定義為如下4個步驟：從AGV當(dāng)前位置移動到待裝載位置；裝載工件；AGV移動到待卸載位置；卸載工件。

2數(shù)學(xué)模型的建立

在數(shù)學(xué)模型中，符號定義如表1所示。

表1　符號說明

按照調(diào)度問題的描述，建立如下數(shù)學(xué)模型：

目標(biāo)函數(shù)： min{max(Cij)}

s.t.Si0=0,?i

(1)

(2)

(3)

(4)

Cij=Sij+Tij,?i,j

(5)

Si(j+1)≥Cij,?i,j

(6)

(7)

當(dāng)工序O(i,j)的目標(biāo)加工設(shè)備未被占用時，即

(10)

目標(biāo)函數(shù)為最小化的最大完工時間；式(1)和式(2)表示設(shè)定系統(tǒng)的加工初始時刻為0；式(3)和式(4)分別表示AGV初始停靠位置和物料存儲位置都在物料存儲區(qū)；式(5)表示工序O(i,j)的完工時間；式(6)表示工件i的下一道工序必須在前一道工序完成之后進(jìn)行，即工序一旦開始，不得中斷；式(7)表示AGV的第K+1項搬運任務(wù)緊跟于AGV上一項搬運任務(wù)；式(8)和式(9)表示，當(dāng)目標(biāo)加工設(shè)備上存在未完工工件時，AGV的當(dāng)前搬運任務(wù)的完成時間和O(i,j)的完工時間；式(10)表示，當(dāng)目標(biāo)加工設(shè)備未被占用時，AGV的當(dāng)前搬運任務(wù)的完成時間和O(i,j)的完工時間。

3混合遺傳算法的模型求解

遺傳算法是在生物進(jìn)化理論的基礎(chǔ)上，通過自然選擇和適者生存的進(jìn)化機(jī)制來求解優(yōu)化問題[6]。針對本文協(xié)同制造系統(tǒng)調(diào)度問題的求解，恰好可利用其良好的全局搜索能力，在較大規(guī)模的解空間中搜索最優(yōu)解[7]。但遺傳算法存在早熟、局部搜索能力差等不足[8]。而模擬退火算法可通過其概率突跳性的特點，在解空間中快速找到最優(yōu)解，從而避免出現(xiàn)局部最優(yōu)解[9]。模擬退火算法雖能較大程度地保證所得解為全局最優(yōu)解，但算法的收斂速度較為緩慢。

綜合遺傳算法和模擬退火算法的優(yōu)點和不足，本文將模擬退火算法中的Boltzmann生存機(jī)制引入標(biāo)準(zhǔn)遺傳算法，并設(shè)計出兩種算法的結(jié)合方式，使得改進(jìn)的混合遺傳算法克服了標(biāo)準(zhǔn)遺傳算法易于早熟的缺點，從而提高了算法全局搜索的效率。

3.1改進(jìn)的算法流程

混合遺傳算法首先通過遺傳算法進(jìn)行種群進(jìn)化，再通過模擬退火算法對產(chǎn)生的新解進(jìn)行接受，算法基本步驟如下：(1)設(shè)置算法參數(shù);(2)進(jìn)行編碼，隨機(jī)產(chǎn)生初始種群;(3)設(shè)計易于實現(xiàn)的適應(yīng)度函數(shù)，以評估每個個體的適應(yīng)度值;(4)根據(jù)適應(yīng)度值排列并選擇個體，記錄適應(yīng)度值最高的個體;(5)根據(jù)交叉概率，進(jìn)行交叉操作，并采用模擬退火算法的Boltzmann生存機(jī)制決定是否接受交叉后的新個體;(6)根據(jù)變異概率，進(jìn)行變異操作，并采用模擬退火算法的Boltzmann生存機(jī)制決定是否接受交叉后的新個體;(7)進(jìn)化次數(shù)k=k+1，進(jìn)行降溫操作tk+1=λtk;(8)判斷是否達(dá)到終止條件，如果達(dá)到終止條件，轉(zhuǎn)(9)；否則轉(zhuǎn)(3);(9)輸出最優(yōu)解。

3.2編碼和解碼方式

基于工序的編碼方法[10]可描述為：在染色體中，每個工件的工序都采用該工件的工件編號表示，某工件編號在染色體序列中第r次出現(xiàn)則代表該工件的第r道工序。例如：染色體為[323121321]，其中工件編號為3的基因在染色體中第2次出現(xiàn)，則表示這是3號工件的第2道工序。

染色體解碼過程：根據(jù)染色體中每個基因位的信息，確定每臺加工設(shè)備上的工件加工順序和每道工序的加工起始時間、加工結(jié)束時間[11]。依據(jù)每道工序的加工起始時間，按照升序排列基因。AGV依據(jù)重新排列后的基因順序進(jìn)行運輸服務(wù)，實現(xiàn)AGV調(diào)度的優(yōu)化。

3.3適應(yīng)度函數(shù)設(shè)計

適應(yīng)度函數(shù)設(shè)計為

f=1/Makespan

(11)

式中Makespan為最大完工時間；由于目標(biāo)函數(shù)是求解最小的最大完工時間。因此，要使得目標(biāo)函數(shù)越小，適應(yīng)度值應(yīng)越大。適應(yīng)度值越大，則該染色體被選擇的幾率越大。

3.4選擇、交叉、變異算子

選擇操作采用輪盤賭賦值法與精英策略相結(jié)合的選擇算子。首先按照輪盤賭賦值法，計算所有個體的適應(yīng)度值，個體適應(yīng)度值越高，則被選入下一代種群的概率越大。找出當(dāng)前群體中適應(yīng)度值最高的個體Pmax和適應(yīng)度值最低的個體Pmin，若迄今為止群體的最佳個體PBEST的適應(yīng)度值高于Pmax，就用Pbest替代Pmin；若Pmax的適應(yīng)度值高于Pbest，則用Pmax取代Pbest。

為保證算法產(chǎn)生染色體的多樣性，這里采用線性交叉方式。交叉過程如圖1描述如下：按照交叉概率隨機(jī)選取待交叉染色體parent1和parent2，在兩條染色體中隨機(jī)選擇兩個對應(yīng)交叉點，將兩交叉點之間的基因段進(jìn)行交叉；交叉完畢后，分別找出parent1和parent2中未交叉部分的基因段，依次記為a1和a2，將a1和a2分別按照其原來在parent2和parent1中的順序，依次填入parent2和parent1中的未交換位置，就得到了子代染色體son2和son1。

變異操作能使搜索過程擺脫局部最優(yōu)解，從而保證了算法的有效性。變異方式為：選取染色體上的一定長度基因段，對基因段上的基因進(jìn)行逆序排列。該方式既增加了解的多樣性，又不影響解的可行性。

3.5新解的接受機(jī)制

在標(biāo)準(zhǔn)遺傳算法的交叉和變異算子中引入Boltzmann生存機(jī)制：設(shè)新產(chǎn)生的染色體的適應(yīng)度值為f′，舊染色體的適應(yīng)度值為f，二者的差值Δf=f′-f。根據(jù)概率

(12)

對新個體進(jìn)行接受選擇,其中，Tk為模擬退火溫度冷卻參數(shù)。

3.6終止條件

算法終止條件預(yù)設(shè)為最大進(jìn)化代數(shù)N，當(dāng)進(jìn)化代數(shù)達(dá)到N時，迭代停止，輸出最優(yōu)解。

4仿真實驗結(jié)果和分析

4.1實驗條件

仿真實驗是基于本校數(shù)字化設(shè)備研究所現(xiàn)有的協(xié)同制造系統(tǒng)進(jìn)行的。該系統(tǒng)由4個加工站(編號為1～4，每個加工站各有一臺加工設(shè)備)，一臺AGV小車和一個立體倉庫(編號為0)組成，布局如圖2所示。整個系統(tǒng)有立體倉庫一個公共緩沖區(qū)。實驗采用4種不同類型的工件，每種工件都具有4道加工工序。這4種工件每道工序的加工時間矩陣Tx和加工設(shè)備矩陣Fx如下所示，T(i,j)表示第i種工件的第j道工序的加工時間，F(xiàn)(i,j)表示第i種工件的第j道工序的加工設(shè)備編號。AGV運輸時間和動作集合如表2和表3所示。AGV卸載與裝載時間均為5 s。

AGV移動路線(站點-站點)AGV移動時間/sAGV移動路線(站點-站點)AGV移動時間/s0-1154-250-2104-300-353-1100-453-254-1102-15

表3　AGV動作集合

4.2實驗結(jié)果與分析

仿真實驗中，分別采用前述改進(jìn)的混合遺傳算法和標(biāo)準(zhǔn)遺傳算法來搜索最優(yōu)解。算法參數(shù)取種群規(guī)模為100，交叉概率Pc為0.8，變異概率Pm為0.01，最大進(jìn)化代數(shù)N為50。冷卻系數(shù)λ=0.9，初始溫度T0=1/2 000。

仿真實驗獲得8個工件進(jìn)行加工的最佳調(diào)度甘特圖如圖3所示，甘特圖中橫坐標(biāo)表示加工站，縱坐標(biāo)表示加工時間。不同顏色的矩形代表不同工件的每道工序，矩形上的數(shù)字代表工件號。圖中黑色曲線表示AGV工作時所處位置與動作持續(xù)時間的對應(yīng)關(guān)系。

應(yīng)用混合遺傳算法時，最佳調(diào)度方案甘特圖如圖3(a)所示。系統(tǒng)的總加工時間為1 900 s，設(shè)備的總工作時間為1 310 s，AGV的行走序列為：H-B-I-D-H-C-I-D-H-A-I-D-H-C-I-N-H-D-I-C-H-D-I-H-C-I-D-H-B-I-G-H-D-I-H-C-I-M-H-D-I-H-A-I-F-H-D-I-B-H-D-I-H-B-I-D-H-C-I-Q-H-D-I-A-H-F-I-D-H-A-I-E-H-D-I-C-H-D-I-H-C-I-D-H-B-I-G-H-D-I-H-C-I-M-H-D-I-C-H-M-I-E-H-G-I-D-H-B-I-G-H-D-I-A-H-F-I-Q-H-M-I-D-H-C-I-N-H-D-I-H-B-I-L-H-D-I-H-A-I-F-H-D-I-H-C-I-Q-H-D-I-A-H-D-I-H-A-I-E-H-G-I-D-H-B-I-G-H-D-I-H-C-I-Q-H-D-I-H-C-I-M-H-D-I-H-A-I-E-H-D-I-C-H-D-I-H-C-I-D-H-B-I-L-H-D-I-C-H-D-I-B-H-D-I-C-H-D-I。染色體序列[68534278568123523123574167841764]。

在相同條件下，應(yīng)用標(biāo)準(zhǔn)遺傳算法得出的最佳調(diào)度甘特圖如圖3(b)所示，系統(tǒng)的總加工時間為2 280 s，設(shè)備總工作時間為1 310 s，AGV行走序列：H-C-I-D-H-A-I-D-H-C-I-D-H-B-I-G-H-D-I-C-H-D-I-H-C-I-N-H-D-I-H-B-I-D-H-C-I-M-H-D-I-H-A-I-F-H-D-I-A-H-D-I-H-A-I-E-H-D-I-H-B-I-D-H-C-I-Q-H-D-I-C-H-D-I-H-C-I-N-H-D-I-A-H-E-I-D-H-C-I-Q-H-M-I-E-H-D-I-H-B-I-G-H-D-I-H-C-I-M-H-D-I-H-A-I-E-H-G-I-Q-H-N-I-L-H-F-I-Q-H-D-I-H-C-I-D-H-A-I-E-H-D-I-C-H-D-I-H-C-I-D-H-B-I-L-H-D-I-H-A-I-F-H-D-I-B-H-D-I-H-B-I-D-H-C-I-Q-H-D-I-H-C-I-M-H-D-I-C-H-M-I-D-H-C-I-N-H-D-I-C-H-D-I-A-H-F-I-Q-H-D-I-C-H-D-I。染色體序列: [65433884376482552171482712765631]。

圖3　分別應(yīng)用混合遺傳算法和標(biāo)準(zhǔn)遺傳算法時8個工件的調(diào)度結(jié)果對比

在不同工件數(shù)目的情況下，分別采用標(biāo)準(zhǔn)遺傳算法和改進(jìn)的混合遺傳算法對協(xié)同制造系統(tǒng)調(diào)度模型進(jìn)行調(diào)度仿真，得到結(jié)果如表4所示。在相同的設(shè)備平均加工時間條件下，改進(jìn)的混合遺傳算法的設(shè)備平均利用率約為68%，而標(biāo)準(zhǔn)遺傳算法的設(shè)備平均利用率約為57%。可見，較之標(biāo)準(zhǔn)遺傳算法，改進(jìn)的混合遺傳算法能較大程度地減少系統(tǒng)的總加工時間、提高設(shè)備平均利用率。此外，隨著加工工件數(shù)目的增多，相對于標(biāo)準(zhǔn)遺傳算法，改進(jìn)的混合遺傳算法節(jié)省的系統(tǒng)總加工時間也逐步增加，設(shè)備的平均利用率也有增加趨勢。

表4　不同工件數(shù)情況下兩種算法的調(diào)度對比結(jié)果

5結(jié)束語

建立了具有單AGV約束的協(xié)同制造系統(tǒng)調(diào)度模型，該模型通過改進(jìn)的混合遺傳算法求解實現(xiàn)工件與單AGV的集成調(diào)度優(yōu)化。仿真實驗證明該算法是可行的，與標(biāo)準(zhǔn)遺傳算法相比，能有效優(yōu)化AGV運動路徑、提高系統(tǒng)調(diào)度效率和設(shè)備利用率、降低系統(tǒng)總加工時間。為具有AGV約束的柔性生產(chǎn)調(diào)度系統(tǒng)提供一種有效的實踐途徑。針對該模型，還可進(jìn)一步考慮實際生產(chǎn)中的一些動態(tài)因素，例如緊急任務(wù)的下達(dá)、設(shè)備故障以及工序延誤等情況，這些突發(fā)狀況的處理亟待深入研究。

參考文獻(xiàn)

[1]周巧.面向緩存有限的柔性制造系統(tǒng)單AGV調(diào)度研究[D].廣州:廣東工業(yè)大學(xué),2014.

[2]夏謙,雷勇,葉小勇.遺傳算法在AGV全局路徑優(yōu)化中的應(yīng)用[J].四川大學(xué)學(xué)報:自然科學(xué)版,2008,45(5):1129-1136.

[3]李莉,張立明,詹躍東.求解AGV路徑優(yōu)化問題的遺傳算法參數(shù)優(yōu)化[J].昆明理工大學(xué)學(xué)報,2006,31(4):26-29,38.

[4]杜亞江,鄭向東,亢麗君.基于遺傳禁忌搜索算法的AGV物料輸送調(diào)度問題研究[J].物流科技,2013(7):1-4.

[5]李惠光,賈建成,冷春輝.基于分步控制算法的多AGV路徑規(guī)劃[J].控制工程,2010(S2):93-96.

[6]Goldberg D E.Genetic algorithms in search, optimization and machine learning[M]. MA,USA: Addison-Wesley, 1989.

[7]趙衛(wèi).模擬退火遺傳算法在車間作業(yè)調(diào)度中的應(yīng)用[J].計算機(jī)仿真,2011,28(7):361-364.

[8]王全.混合遺傳算法及其改進(jìn)[J].安徽建筑工業(yè)學(xué)院學(xué)報:自然科學(xué)版,1999,7(4):59-62.

[9]Abdelsalam H M E,Bao Han P.A simulation-based optimization framework for product development cycle time reduction[J].IEEE Transactions on Engineering Management,2006,53(1):69-85.

[10]Holsapple C W,Jacob V S,Pakath R,et al.A genetics-based hybrid scheduler for generating static schedules in flexible manufacturing contexts[J]. IEEE Transactions on Systems, Man and Cybernetics,1993,23(4):953-971.

[11]董義軍,張功,張潔.單無人搬運車/單緩沖區(qū)約束的柔性生產(chǎn)系統(tǒng)調(diào)度研究[J].上海交通大學(xué)學(xué)報,2010,44(4):528-534.

Research on Scheduling for Collaborative Manufacturing System Based on Hybrid Genetic Algorithm

REN Naifei，YU Lu

(School of Mechanical Engineering, Jiangsu University, Zhenjiang 212013, China)

AbstractBased on the Collaborative Manufacturing System (CMS) consisting of multiple processing stations, a centralized storage area and an Automatic Guided Vehicle (AGV), a mathematical model was built on analysis of the resource constrained problem. The architecture of a dispatching approach with hybrid genetic algorithm was proposed to solve the scheduling problem under resource constraint of the single AGV. This modified hybrid genetic algorithm improved the method of coding, crossover and mutation, which can optimize the job’s machining sequence and the action sequences of AGV movement effectively. Finally, the simulation experiment results in CMS showed that the proposed method is feasible for the integrated scheduling for CMS with the AGV constraint.

Keywordshybrid genetic algorithm; automatic guided vehicle; production scheduling; collaborative manufacturing system; computer simulation

收稿日期:2015-10-25

作者簡介:任乃飛(1964-)，男，博士，教授，博士生導(dǎo)師。研究方向：現(xiàn)代集成制造。于璐(1990-)，女，碩士研究生。研究方向：柔性制造系統(tǒng)關(guān)鍵技術(shù)。

doi:10.16180/j.cnki.issn1007-7820.2016.06.009

中圖分類號TP306.1；TH165

文獻(xiàn)標(biāo)識碼A

文章編號1007-7820(2016)06-029-05