基于遺傳算法的板坯入庫梁式起重機(jī)調(diào)度優(yōu)化

大連理工大學(xué)機(jī)械工程學(xué)院 大連 116024

0 引言

梁式起重機(jī)(以下簡稱天車)被廣泛應(yīng)用于集裝箱碼頭、制造業(yè)企業(yè)車間等場合。隨著2025智能制造的發(fā)展，天車在制造業(yè)車間中發(fā)揮著愈發(fā)重要作用，科學(xué)合理的天車調(diào)度可大大提高作業(yè)效率，能最大化利用企業(yè)的資源，是智能車間的發(fā)展方向[1]。在連鑄-熱軋煉鋼工藝中，天車是核心的起重運(yùn)輸設(shè)備。在板坯車間，天車調(diào)度是指在滿足天車運(yùn)行空間約束和天車資源約束的條件下，合理分配天車完成板坯的吊運(yùn)任務(wù)，保證連鑄區(qū)生產(chǎn)任務(wù)有序、緊湊的進(jìn)行，使整體吊運(yùn)效率與生產(chǎn)目標(biāo)一致[2]。目前，天車調(diào)度問題大多針對碼頭集裝箱的調(diào)度[3-5]和制造車間的天車調(diào)度，而在連鑄-熱軋車間的板坯庫內(nèi)的天車調(diào)度問題研究較少，實(shí)際作業(yè)更多依賴調(diào)度人員的經(jīng)驗(yàn)，資源浪費(fèi)嚴(yán)重。

本文以某大型煉鋼廠的連鑄-熱軋車間的存儲車間（以下簡稱板坯車間）為研究對象，對天車進(jìn)行合理的調(diào)度安排，提高連鑄車間的產(chǎn)能，同時(shí)提高存儲車間的存放量。板坯存儲車間是連鑄板坯的成品外賣車間同時(shí)也是熱軋工藝的原料車間。因此，對板坯存儲車間的天車合理調(diào)度進(jìn)行研究，能夠更好地利用車間內(nèi)的倉儲空間，提高車間的倉儲量。在板坯車間內(nèi)，同一作業(yè)跨的軌道上有多臺規(guī)格同類和不同類型的天車，由連鑄作業(yè)跨鑄造的板坯經(jīng)輥道運(yùn)輸至板坯庫進(jìn)行儲存或者先進(jìn)行存放等待進(jìn)一步的熱軋工作，需要天車進(jìn)行搬運(yùn)作業(yè)。受板坯規(guī)格不同的影響，天車的運(yùn)輸任務(wù)就會多樣復(fù)雜化，且經(jīng)常會出現(xiàn)多塊板坯進(jìn)行同時(shí)運(yùn)輸?shù)那闆r，搬運(yùn)任務(wù)無論是在時(shí)間上還是在空間上都有很強(qiáng)的隨機(jī)性，導(dǎo)致天車在作業(yè)過程中容易產(chǎn)生沖突，所以板坯在輥道上運(yùn)至作業(yè)跨時(shí)，需要對天車進(jìn)行合理的調(diào)度安排。

本文運(yùn)用遺傳算法對天車的板坯入庫任務(wù)進(jìn)行分配，可避免天車之間的作業(yè)干擾，提高天車的作業(yè)效率，有序及時(shí)地將輥道運(yùn)來的板坯進(jìn)行入庫吊運(yùn)作業(yè)。

1 板坯庫的概況

圖1為某連鑄-熱軋工廠的板坯車間的其中一跨的布局圖，跨位上有數(shù)臺天車，且只能在同一跨位上進(jìn)行吊運(yùn)作業(yè)，在倉庫的長度方向上同一跨內(nèi)分為五個(gè)作業(yè)區(qū)，同作業(yè)跨的方向，每個(gè)作業(yè)區(qū)會分為若干行，每行上會有兩個(gè)板坯垛，板坯垛的方向與大車作業(yè)方向垂直，需將連鑄區(qū)生產(chǎn)的板坯經(jīng)輥道運(yùn)輸至倉儲板坯庫，選擇合適的天車將板坯從輥道上起吊放置在合適的垛位上。

經(jīng)典的天車調(diào)度問題是指：N個(gè)工件在M臺機(jī)床上加工，并且工件的加工順序及加工時(shí)間確定，一個(gè)工件同一時(shí)刻只能在一臺機(jī)器上加工，且開始加工后不能中斷。因此，可將板坯車間的天車調(diào)度問題進(jìn)行經(jīng)典調(diào)度問題轉(zhuǎn)化，設(shè)輥道上來的板坯數(shù)M，板坯庫內(nèi)作業(yè)天車為N，要將M個(gè)板坯用N臺天車進(jìn)行入庫吊運(yùn)，將天車看成機(jī)床，入庫的板坯看成待加工的工件，每塊板坯需要天車吊運(yùn)一次，并且入庫作業(yè)進(jìn)行一次即可。

圖1 板坯庫某一跨布局簡圖

1.1 問題描述

給定一個(gè)板坯的入庫計(jì)劃M，包括M個(gè)板坯吊運(yùn)任務(wù)，板坯吊運(yùn)任務(wù)i（i＝1,2，…，M）由板坯入庫的輥道位置Lsi開始和入庫的垛位位置Lfi結(jié)束，并且要求板坯i在相應(yīng)的起始時(shí)間（Lsi，Lfi）內(nèi)完成。作業(yè)天車的集合為N，包括N臺天車，天車k的起始作業(yè)位置Lk0,板坯的起吊時(shí)間α和放置庫內(nèi)垛位的時(shí)間β，以及天車的運(yùn)輸速度v都是根據(jù)天車的性能不變的，并且將板坯入庫時(shí)在垂直方向上的運(yùn)輸時(shí)間規(guī)劃至大車的運(yùn)輸時(shí)間內(nèi)。因此，板坯吊運(yùn)任務(wù)i的處理時(shí)間Ti＝α+β+|Lfi-Lsi|/v。同樣的，板坯吊運(yùn)任務(wù)i的垛放位置和下一個(gè)板坯吊運(yùn)任務(wù)j的開始起吊位置的距離Dij亦可以提前計(jì)算出來，在吊運(yùn)任務(wù)i開始的時(shí)刻指派相應(yīng)的天車去吊運(yùn)，天車吊運(yùn)板坯任務(wù)i后，由板坯吊運(yùn)結(jié)束位置垛位以天車自身運(yùn)輸速度v空載運(yùn)行至下一塊吊運(yùn)板坯位置處，即板坯入庫的輥道處。目標(biāo)函數(shù)為最小化板坯的入庫完成時(shí)間。

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

倉儲板坯車間的調(diào)度問題可以描述為M個(gè)待吊運(yùn)的板坯被N臺天車吊運(yùn)的，其數(shù)學(xué)模型為：

1）板坯集M＝{M1, M2, …, Mm}，Mi為第i塊待吊運(yùn)的板坯，i＝1，2，…，M ；

2）天車集N={N1, N2, …, Nn}，Nj為第j臺作業(yè)天車，j=1, 2, … , N ；

其他相關(guān)參數(shù)：Ψ為吊運(yùn)板坯之間的優(yōu)先級集合，表示Mi吊運(yùn)任務(wù)必須在Mj吊運(yùn)任務(wù)之前進(jìn)行完成，天車集包含有圖1中沿X軸正方向依次編號N={1, 2, …, N }，N為跨內(nèi)天車總數(shù)，Lk0為天車k開始作業(yè)前的起始位置；Lsi、Lfi為吊運(yùn)任務(wù)i的起始結(jié)束作業(yè)位置；Lsi、Lfi為任務(wù)i的起始、放置作業(yè)時(shí)間；v為天車的運(yùn)輸速度；δ為保證相鄰天車在作業(yè)過程中不會發(fā)生碰撞危險(xiǎn)的最小安全距離；Dij為任務(wù)i完成結(jié)束后再次到達(dá)任務(wù)j開始的位置的距離；Tm為計(jì)劃完成時(shí)間；Z為比較大的一個(gè)常數(shù)，作為任務(wù)約束的一個(gè)系數(shù)。

模型決策因素：tfi為板坯吊運(yùn)任務(wù)i的期望完成時(shí)間；Xk（t）表示t時(shí)刻天車k在作業(yè)跨上的位置。

Yijk取值1表示天車吊運(yùn)板坯i后吊運(yùn)下一塊板坯j，進(jìn)行連續(xù)的吊運(yùn)作業(yè)；取值0表示天車吊運(yùn)板坯i后未有下一吊運(yùn)任務(wù)。

建立車間板坯調(diào)度模型為

其中，式（1）為目標(biāo)函數(shù)板坯最小入庫完成時(shí)間；式（2）和式（3）表示板坯的入庫作業(yè)只能由一臺天車吊運(yùn)一次；式（4）為天車作業(yè)中的速度約束；式（5）表示同一作業(yè)跨上相鄰的兩臺作業(yè)天車的最小距離要大于完全距離，避免相鄰天車發(fā)生碰撞事故 ；式（6）和式（7）為時(shí)間約束，要求板坯的開始吊運(yùn)時(shí)間和吊運(yùn)過程使用的時(shí)間要在板坯的最后計(jì)劃時(shí)間前完成；式（8）表示板坯i的吊運(yùn)要在板坯j吊運(yùn)之前完成；式(9)為定義的相應(yīng)變量的取值范圍。

2 遺傳算法（GA）設(shè)計(jì)求解

本文采用遺傳算法（GA）作為群體進(jìn)化方法，進(jìn)化步驟為：

1)對參數(shù)進(jìn)行初始化設(shè)置：假設(shè)種群的規(guī)模為S，迭代K次完成群體的進(jìn)化，得到當(dāng)前群體的最優(yōu)解Xb，并且種群收斂于最優(yōu)解，最優(yōu)解出現(xiàn)的次數(shù)Nb，保持上一代的最優(yōu)解數(shù)量Nf，b。

2)對種群進(jìn)行初始化設(shè)置：S（1），設(shè)置S′（1）：＝?；

For k＝1：K

For i＝ 1：S/2

3）返回輸出當(dāng)代最好的。

2.1 群體的編碼和解碼

個(gè)體s的編碼采用單鏈?zhǔn)骄幋a的方式，取編碼的長度為N，如圖2所示，其中M為需要入庫的板坯的總數(shù)，也代表著吊運(yùn)的任務(wù)總數(shù)，位置i為第i個(gè)需要吊運(yùn)入庫的板坯吊運(yùn)任務(wù)，Ni為吊運(yùn)板坯i的天車編號。解碼的過程就是根據(jù)個(gè)體s的編碼，運(yùn)用離散事件動態(tài)仿真方法執(zhí)行吊運(yùn)任務(wù)的過程。

圖2 個(gè)體編碼

2.2 初始種群的產(chǎn)生

1)令i＝0，生成[1，N]內(nèi)的隨機(jī)數(shù)，填入對應(yīng)的i的位置；

2)令i＝i+1，重復(fù)步驟1），填入對應(yīng)的下一位置，直到滿足i＝N，保證每臺天車都已填入位置；

3)不斷地重復(fù)步驟1）和步驟2）直到S次，生成初始種群。

2.3 交叉操作

種群通過交叉操作獲得新的染色體，從而實(shí)現(xiàn)種群的進(jìn)化。為了增加種群的多樣性，設(shè)置一個(gè)交叉概率為Pc的交叉算子，并根據(jù)式（10）進(jìn)行自適應(yīng)的調(diào)整，以控制種群的交叉操作。

式中：f為每次個(gè)體交叉中最大的目標(biāo)函數(shù)值，fmax、fmin、favg為所隨機(jī)產(chǎn)生的初始種群中最大、最小和平均目標(biāo)函數(shù)值。交叉算子指在父代的兩個(gè)個(gè)體的編碼中，隨機(jī)選中編碼中同一位置的編碼，對應(yīng)位置的編碼進(jìn)行交換，其他位置上的編碼不變，形成兩個(gè)新的子代個(gè)體 s＇1和 s＇2。

2.4 變異操作

種群的進(jìn)化過程中，種群中的個(gè)體會出現(xiàn)染色體變異的情況，因此，在求解過程中添加概率為Pm的變異算子，對個(gè)體進(jìn)行變異操作。變異算子是指在當(dāng)代個(gè)體的染色體編碼中，有些位置的基因發(fā)生突變形成新的變異子代個(gè)體s″。

3 算例設(shè)計(jì)及仿真結(jié)果分析

根據(jù)實(shí)地考察板坯庫，板坯庫內(nèi)的工作區(qū)域每跨劃分成兩行垛位，相鄰兩行垛位的距離為5 m，跨位上有2～3臺天車進(jìn)行板坯的吊運(yùn)作業(yè)，天車在作業(yè)跨上作業(yè)的起始位置隨機(jī)設(shè)置，天車的運(yùn)行速度設(shè)定為10 m/s，相鄰天車間的安全距離為5 m。取該板坯車間8組不同的板坯入庫數(shù)據(jù)，進(jìn)行仿真測試天車的調(diào)度算法設(shè)計(jì)。算例參數(shù)見表1。

表1 算例參數(shù)設(shè)置

遺傳算法（GA）采用個(gè)體編碼、解碼的方式進(jìn)行編碼、解碼操作；運(yùn)用輪盤賭的方法進(jìn)行選擇，采用交叉算子和變異算子進(jìn)行種群的進(jìn)化，增加種群的多樣性。對遺傳算的參數(shù)進(jìn)行設(shè)置：種群規(guī)模S＝20，進(jìn)行迭代的次數(shù)K＝20，交叉概率Pc＝0.85，變異概率Pm＝0.01，對8組算例進(jìn)行求解，每組算例運(yùn)行5次，取其中最優(yōu)的結(jié)果。表2所示，其中，T為算法運(yùn)行的時(shí)間，O為每個(gè)算例得到的目標(biāo)函數(shù)的值。

表2 算例的仿真結(jié)果

從表2的運(yùn)行結(jié)果中可知，遺傳算法能在較短的時(shí)間內(nèi)求得目標(biāo)函數(shù)比較接近的優(yōu)解，但是隨著種群規(guī)模的增大，算法的時(shí)間也隨之加長，二者成正比例的關(guān)系，通過對比8個(gè)算例的運(yùn)行結(jié)果可以得出結(jié)論：1）作業(yè)跨上的天車數(shù)量保持不變，增加板坯的入庫數(shù)量，板坯入庫的時(shí)間就隨之增大，二者呈正相關(guān)。2）當(dāng)入庫的板坯數(shù)量不變的時(shí)候，作業(yè)跨上的天車增多能夠降低板坯入庫的時(shí)間，但是降低的時(shí)間不太顯著，這是因?yàn)樘燔囘\(yùn)行之間出現(xiàn)干擾，使天車出現(xiàn)較多的空載或被動運(yùn)輸。

如圖3所示，遺傳算法（GA）的目標(biāo)函數(shù)值迭代曲線在設(shè)定的迭代次數(shù)內(nèi)能夠平緩的收斂于最優(yōu)值；而平均函數(shù)值在前期會處于震蕩的趨勢，在迭代到種群規(guī)模的最后收斂于最優(yōu)平均值。

圖3 目標(biāo)函數(shù)的最優(yōu)迭代值和平均迭代值

4 結(jié)論

針對鋼鐵連鑄-熱軋之間的板坯車間的天車調(diào)度問題，對板坯的入庫建立作業(yè)天車調(diào)度的仿真模型，并進(jìn)行算例的仿真分析。運(yùn)用遺傳算法（GA）對仿真模型進(jìn)行求解，對板坯入庫的特點(diǎn)，進(jìn)行遺傳算法的交叉、變異等操作，對板坯入庫的模型進(jìn)行測試，證明遺傳算法能夠有效地解決天車調(diào)度的問題。