基于改進遺傳算法的軋輥磨削產線智能排程方法＊

陸耀珣 王立平 孫麗榮 楊金光 王 冬 李學崑

（①電子科技大學機械與電氣工程學院，四川 成都 611731；②清華大學機械工程系，北京 100084；③山東鋼鐵集團日照有限公司，山東 日照276806 ；④軋制技術及連軋自動化國家重點實驗室，遼寧 沈陽 110819）

鋼鐵行業是支撐國民經濟發展的重點行業，而軋輥磨削是軋鋼生產的重要組成，軋輥磨削產線的排程方案直接影響軋鋼生產的效率。與單一柔性作業車間或天車調度問題不同，軋輥磨削產線需要同時考慮多工件、多工序、多磨床和多天車，屬于柔性作業車間調度與天車調度的交叉耦合問題，調度規模大，影響因素多，排程極為困難。傳統基于人工經驗的專家系統雖能得到可行的排程方案，但無法保證方案的性能最優。如何在“工件-設備-天車”時空耦合的約束下實現高效智能排程，是當前軋輥磨削產線面臨的關鍵問題。

近年來柔性作業車間調度問題與天車調度問題受到國內外學者的持續關注和研究，智能調度排程算法是其中的關鍵研究內容。已有許多學者針對柔性作業車間調度問題展開研究，如Dang S 等[1]設計了一種改進遺傳算法解決了柔性作業車間調度問題；屈新懷等[2]將貪婪算法與遺傳算法相融合解決了柔性作業車間調度問題；趙小惠等[3]設計了一種改進蟻群算法解決了柔性作業車間調度問題；蔡敏等[4]融合了粒子群優化算法、模擬退火算法與改進人工蜂群算法，解決了模糊柔性作業車間調度問題。此外也有眾多學者針對天車調度問題進行了研究，如許少杰[5]借助遺傳算法完成了鋼廠天車的建模與調度優化；Meisel F 等[6]將免疫算法與粒子群優化算法相結合，研究了車間天車調度優化問題；徐樂[7]同時使用元胞自動機和遺傳算法完成了車間天車優化，其中元胞自動機負責天車建模，遺傳算法負責調度任務優化；雷兆明等[8]使用布谷鳥搜索算法優化了車間天車調度；楊坤鵬[9]設計了一種改進遺傳算法提高了連鑄-熱軋板坯車間天車效率，進而提升了入庫效率。部分學者進一步考慮調度運輸時間，在柔性作業車間中引入單天車系統。例如，Liu Z等[10]以綜合能耗為目標函數，使用遺傳算法求解包含單個天車的柔性作業車間調度問題。Li J 等[11]提出一種改進Jaya 遺傳算法求解考慮運輸時間的柔性作業車間調度問題。Wang H 等[12]使用遺傳算法求解考慮運輸過程的柔性作業車間調度問題。楊帆等[13]在柔性作業車間調度問題中加入運輸和裝配環節，并提出一種帶保優策略的遺傳-粒子群混合算法求解柔性作業車間多資源調度問題。但單天車系統回避了多天車干涉這一天車調度問題的核心。多天車之間的干涉與避讓導致調度運輸時間進一步增加，在天車實時位置未知的情況下時間增量具有不確定性。針對多工件、多工序、多磨床和多天車耦合的復雜作業系統，仍需要深入開展調度排程研究。

本文針對軋輥磨削產線調度問題，提出了一種基于改進遺傳算法的智能排程方法，以實現復雜約束下的智能求解。選擇最大完工時間作為目標函數，使用三層編碼方式分別對工件工序層、機器層和天車層進行編碼，使用君主染色體+POX 交叉的選擇、交叉方案，采用動態變異率提高后期跳出局部最優解的能力，最后設計了基于動作分解的天車解碼規則及系列算子，以實現產線智能排程，并使用自適應采樣時間算子提高計算效率。與經過最低限度改進的原始遺傳算法及基于人工經驗的排程方法對比，所提出的改進遺傳算法具有明顯優勢。

1 問題描述

軋輥磨削產線調度問題可描述為：對于n個工件，其組成的集合為J={J1,J2,···,Jn}，每個工件包含j道工序，則工件i對應工序集合為Oi={Oi1,Oi2,···,Oij}。將所有用于加工工件的生產設備及工位統稱為機器，整個軋輥磨削產線的全部m臺機器組成機器集合M={M1,M2,···,Mm}，q臺天車組成的集合為Q={Q1,Q2,···,Qq}。工件i的第j道工序Oij可用機器集合為Mij∈M。調度的目標是合理安排工件工序、機器、天車使得相關性能指標最優。

軋輥磨削產線中工件、機器和天車需滿足時空約束，如式（1）～（10）所示，符號變量如表1 所示。

表1 符號變量表

其中：式（1）表示工件某道工序在機器上的開始時間、加工時間、天車運輸時間三者之和不超過工件該工序的完成時間。式（2）表示工件某道工序的完工時間不超過下一工序的開始時間。式（1）和（2）聯立表示工件加工遵守工序順序約束。

式（3）表示任一工件加工時間不大于最大完工時間。

式（4）和（5）中H表示一個很大的數，兩式聯立表示任一時刻的任一機器只能加工一道工序。

式（6）表示某時刻一道工序只能由一臺機器加工。式（7）表示工件加工的開始時間和完成時間非負，且從0 時刻開始任意工件都可以加工。

式（8）表示每個吊運任務只能分配一輛天車。式（9）表示天車之間的距離要大于等于安全距離。式（10）表示在機器k上加工前，天車的運輸時間應等于天車導軌方向運動時間與垂直天車導軌方向運動時間中的最大值。

本文使用最大完工時間這一廣泛應用的性能指標作為約束優化問題目標函數，使求取的排程方案的最大完工時間最小。

2 改進遺傳算法

2.1 算法流程

首先對標準遺傳算法進行改進，解決軋輥磨削產線中的工件排程問題，進一步設計基于動作分解的天車無干涉解碼規則及系列算子，從而實現工件、機器和天車三者時空耦合條件下的軋輥磨削產線智能排程，其算法流程如圖1 所示，其步驟描述如下：

圖1 改進遺傳算法流程圖

步驟1：遺傳算法參數初始化。

步驟2：生成多個初始染色體，作為初始種群。

步驟3：遍歷初始種群中的每個染色體，對每個染色體執行不完全排程表變換，將染色體變換為包含工件工序與天車任務分配信息，但不包含工件工序與天車任務時間信息的不完全排程表。將不完全排程表作為輸入，執行天車解碼，得到包含工件工序與天車任務時間信息的完全排程表，并計算適應度。

步驟4：判斷染色體是否遍歷完成，是則前往步驟5，否則前往步驟3。

步驟5：將染色體按適應度升序，并更新最佳染色體。

步驟6：判斷是否到達最大遺傳代數G，是則前往步驟8，否則前往步驟7。

步驟7：選擇需要參與交叉的染色體，對每個選擇的染色體依次執行交叉、變異操作，并返回步驟3。

步驟8：對于最佳染色體，繪制甘特圖、算法收斂曲線圖、天車位移圖，輸出完全排程表，改進遺傳算法結束。

2.2 染色體編碼

本文使用一種三層編碼方式，即染色體具有3個基因串，分別為工序順序層JS、機器選擇層MS和天車選擇層PS。基因串長度為所有工件與所有工序的數目總和，3 個基因串長度相等，以[JS,MS,PS]的形式首尾連接，如圖2 所示。根據每一層的特點，又使用了不同的編碼規則，其中JS 使用基于工序的編碼規則，MS 使用相對機器編碼的編碼規則，PS 使用直接編碼規則。

圖2 三層染色體編碼方式

基于工序編碼的編碼規則可按如下方式描述：對于工序順序層JS，其為有序數列，其中第i位上的數字為x，代表工件編號為x。從第1 位起至第i位，x共出現了k次，則JS 的第i位代表Oxk，即工件x的第k道工序。如圖3 所示。

圖3 JS 基于工序編碼的編碼規則

MS 使用相對機器編碼的編碼規則，可按如下方式描述：對于MS，其為有序數列，從左到右人為規定每一位所對應的工件與工序。對于某一位i，事先設定其對應的工件工序可用的機器集合M，M中的元素為機器編號，則MS 中第i位上的數字MS(i)對應的機器編號為M(MS(i))。如圖4 所示。

圖4 MS 基于相對機器編號的編碼規則

PS 使用直接編碼的編碼方式，基因上的數字即為天車號，對應工序同MS。

2.3 染色體選擇與交叉

本文中的選擇操作使用了輪盤賭法與精英保留策略；交叉操作中，對于JS 使用了君主染色體方案與POX 交叉相結合的方案，對于MS、PS 使用多點交叉方案。

2.4 染色體變異

對于JS，因受到嚴格約束，為防止出現不可行解，使用染色體上兩個不同基因互換的策略，而對于MS 與PS，使用單點變異策略。

同時，為緩解迭代后期種群陷入局部最優解，使用隨迭代次數變化的動態變異率：

其中：Pm為變異率，Pm0為初始變異率，gen為當前迭代次數，G為迭代次數上限。隨著當前迭代次數的不斷增大，變異率不斷增大，能夠一定程度上緩解陷入局部最優解的問題。

2.5 基于動作分解的天車解碼規則

基于動作分解的天車解碼規則是通過模擬天車調度運輸的一系列動作，并以一定的采樣時間間隔更新天車坐標、天車狀態和運動時間，從而實現工件與天車調度排程。天車動作表如表2 所示，表中動作1～8 構成天車一次完整調度動作。分析可知，天車動作可分為兩類調度動作，第一類為天車靜止動作，此時天車在軌道上保持靜止，僅天車上的小車與鉤爪可進行運動，放鉤、裝載、卸載和收鉤屬于第一類，耗時可視為定值。第二類為天車移動動作，此時天車在軌道上移動，而天車上的小車和鉤爪將相對于天車保持靜止，前往始發地、前往目的地屬于第二類。進一步分析可知，天車前往始發地與前往目的地本質是一個動作，皆為從軌道上一點移動至另一點。此外，第二類天車動作耗時與天車速度及位移有關。

表2 天車動作表

根據天車動作，本文設計了排程表變換算子schedule_transfer、天車移動算子move、天車調度動作算子transfer、天車干涉算子collision、自適應采樣時間算子change_dtime，并進一步設計了一種基于動作分解的天車解碼規則。解碼流程如圖5 所示，具體步驟如下：

圖5 基于動作分解的天車解碼流程圖

步驟1：將已完成選擇、交叉、變異操作的染色體，通過不完全排程表變換算子schedule_transfer，使抽象的染色體變換為易于閱讀的不完全排程表。不完全排程表包含工件號job、工件工序號job_pro、始發地start、目的地target、分配的天車號portal，但不包含各工件工序的開始、結束時間和天車調度任務的開始、結束時間。

步驟2：將不完全排程表作為輸入，根據天車干涉發生與否分別使用天車干涉算子collision、天車調度動作算子transfer 計算并記錄各個工件的加工開始時間j_starttime、結束時間j_endtime、各個天車調度任務的開始時間p_starttime、結束時間p_starttime、各個天車橫坐標隨時間的變化[coord_x,t]。

步驟3：根據天車間距離判斷是否發生干涉。是則調用天車干涉算子collision，collision 進一步調用move；否則調用天車調度算子transfer，transfer進一步調用天車移動算子move。算子返回天車坐標、天車狀態，并記錄任務時間。

步驟4：使用自適應采樣時間算子change_dtime 確定下一個采樣時間點，以提高計算效率。

步驟5：判斷是否完成全部調度任務，是則生成包含調度時間信息的完全排程表并輸出，基于動作分解的天車解碼完成；否則根據步驟4 更新時間，回到步驟3。

需要說明的是，天車避讓使用基于優先級的避讓策略，根據天車的運行狀態制定優先級，如表3所示。優先級低的天車需避讓優先級高的天車，當兩天車優先級相同時采取輪流避讓策略。

表3 天車優先級制定

表4 給出了本文所提出方法相對標準遺傳算法的改進部分及作用。

表4 本文所提出方法相對標準遺傳算法的改進部分及作用

3 實例求解及結果分析

本節對改進遺傳算法、原始遺傳算法（經過最低限度改進以保證生成可行解的遺傳算法）及某企業目前使用的排程方法的排程效果進行對比分析。軋輥磨削產線布局如圖6 所示。相關環境變量設置如表5 所示，其中天車裝載/卸載時間已包含對應收放鉤耗時。工序流程及耗時如表6 所示，其中“-”表示該任務為調度任務而非加工任務。

表5 車間環境變量設置

表6 工序流程及其耗時

圖6 車間布局示意圖

改進遺傳算法及原始遺傳算法的參數設置為：種群規模NP=50，最大迭代次數G=20，交叉概率Pc=0.8，初始變異概率Pm0=0.01。重復進行5 次實驗。實驗結果中各算法最大完工時間見表7，調度運輸時長見表8。

由表7 和表8 可知，改進遺傳算法生成的調度方案在最大完工時間指標上全面優于原始遺傳算法，5 次實驗中改進遺傳算法的最差排程結果仍優于原始遺傳算法的排程結果；相對于原始遺傳算法，改進遺傳算法的最大完工時間平均減少10.78%，調度運輸耗時平均減少21.62%。此外，改進遺傳算法也全面優于企業排程方法；相對于5 次實驗結果完全相同的企業排程方法，改進遺傳算法的最大完工時間和調度運輸耗時分別平均減少了15.49%和28.08%。

表7 各算法最大完工時間

表8 各算法調度運輸耗時

圖7 為改進遺傳算法與原始遺傳算法的進化曲線圖。由圖可知，標準遺傳算法在第2 輪迭代即找到了一局部最優解，此后趨于平緩；而改進遺傳算法直至第7 輪迭代時仍保持下降趨勢，從第8 輪迭代開始趨于平緩，且改進遺傳算法找到的最優解要優于原始遺傳算法的最優解，說明改進遺傳算法的全局尋優能力與跳出局部最優解的能力要強于原始遺傳算法。

圖7 改進遺傳算法與原始遺傳算法的進化曲線

圖8 為改進遺傳算法中最佳排程方案的甘特圖，圖中矩形無重疊部分，證明排程方案的合理性。

圖8 改進遺傳算法最佳調度方案對應甘特圖

圖9 為天車沿軌道方向的位移圖，將圖9 局部放大得圖10。圖中兩折線分別為兩天車位移隨時間的變化，易知兩折線斜率相同，避讓操作期間兩天車的運動趨勢相同。設置天車間安全距離為5 m，由圖可知157 s 時兩天車的位移為26 m、32 m，164 s時兩天車的位移為30 m、36 m，即位移差值恒為6 m，避讓操作期間兩天車間距始終保持恒定且大于安全距離；如不伴隨，兩折線距離將不斷減小并最終相交，即天車發生碰撞。

圖9 改進遺傳算法最佳調度方案對應天車位移圖

圖10 兩天車保持安全距離

上述結果充分證明了所提出基于改進遺傳算法的智能排程方法的有效性和優越性。

4 結語

本文針對軋輥磨削產線調度問題，提出了一種基于改進遺傳算法的智能排程方法。從編碼、選擇、交叉和變異等4 個方面對遺傳算法進行了改進，設計了基于動作分解的天車解碼規則及系列算子，有效解決了多天車運動干涉問題，最終實現了“工件-設備-天車”復雜時空耦合約束下的高效智能排程。驗證結果顯示，與原始遺傳算法和企業排程方法相比，所提出智能排程方法的最大完工時間平均縮短10.78%與15.49%，調度運輸耗時平均縮短21.62%與28.08%，因此，所提出的智能排程方法明顯更優。相關研究成果可為提升軋輥磨削產線的調度效率與智能化水平提供核心算法支撐。