基于遺傳算法的板坯入庫梁式起重機調度優化

大連理工大學機械工程學院 大連 116024

0 引言

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

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

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

1 板坯庫的概況

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

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

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

1.1 問題描述

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

1.2 數學模型

倉儲板坯車間的調度問題可以描述為M個待吊運的板坯被N臺天車吊運的，其數學模型為：

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

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

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

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

Yijk取值1表示天車吊運板坯i后吊運下一塊板坯j，進行連續的吊運作業；取值0表示天車吊運板坯i后未有下一吊運任務。

建立車間板坯調度模型為

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

2 遺傳算法（GA）設計求解

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

1)對參數進行初始化設置：假設種群的規模為S，迭代K次完成群體的進化，得到當前群體的最優解Xb，并且種群收斂于最優解，最優解出現的次數Nb，保持上一代的最優解數量Nf，b。

2)對種群進行初始化設置：S（1），設置S′（1）：＝?；

For k＝1：K

For i＝ 1：S/2

3）返回輸出當代最好的。

2.1 群體的編碼和解碼

個體s的編碼采用單鏈式編碼的方式，取編碼的長度為N，如圖2所示，其中M為需要入庫的板坯的總數，也代表著吊運的任務總數，位置i為第i個需要吊運入庫的板坯吊運任務，Ni為吊運板坯i的天車編號。解碼的過程就是根據個體s的編碼，運用離散事件動態仿真方法執行吊運任務的過程。

圖2 個體編碼

2.2 初始種群的產生

1)令i＝0，生成[1，N]內的隨機數，填入對應的i的位置；

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

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

2.3 交叉操作

種群通過交叉操作獲得新的染色體，從而實現種群的進化。為了增加種群的多樣性，設置一個交叉概率為Pc的交叉算子，并根據式（10）進行自適應的調整，以控制種群的交叉操作。

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

2.4 變異操作

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

3 算例設計及仿真結果分析

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

表1 算例參數設置

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

表2 算例的仿真結果

從表2的運行結果中可知，遺傳算法能在較短的時間內求得目標函數比較接近的優解，但是隨著種群規模的增大，算法的時間也隨之加長，二者成正比例的關系，通過對比8個算例的運行結果可以得出結論：1）作業跨上的天車數量保持不變，增加板坯的入庫數量，板坯入庫的時間就隨之增大，二者呈正相關。2）當入庫的板坯數量不變的時候，作業跨上的天車增多能夠降低板坯入庫的時間，但是降低的時間不太顯著，這是因為天車運行之間出現干擾，使天車出現較多的空載或被動運輸。

如圖3所示，遺傳算法（GA）的目標函數值迭代曲線在設定的迭代次數內能夠平緩的收斂于最優值；而平均函數值在前期會處于震蕩的趨勢，在迭代到種群規模的最后收斂于最優平均值。

圖3 目標函數的最優迭代值和平均迭代值

4 結論

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