基于改進(jìn)遺傳算法的軋輥磨削產(chǎn)線智能排程方法＊

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

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

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

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

本文針對軋輥磨削產(chǎn)線調(diào)度問題，提出了一種基于改進(jìn)遺傳算法的智能排程方法，以實(shí)現(xiàn)復(fù)雜約束下的智能求解。選擇最大完工時間作為目標(biāo)函數(shù)，使用三層編碼方式分別對工件工序?qū)印C(jī)器層和天車層進(jìn)行編碼，使用君主染色體+POX 交叉的選擇、交叉方案，采用動態(tài)變異率提高后期跳出局部最優(yōu)解的能力，最后設(shè)計(jì)了基于動作分解的天車解碼規(guī)則及系列算子，以實(shí)現(xiàn)產(chǎn)線智能排程，并使用自適應(yīng)采樣時間算子提高計(jì)算效率。與經(jīng)過最低限度改進(jìn)的原始遺傳算法及基于人工經(jīng)驗(yàn)的排程方法對比，所提出的改進(jìn)遺傳算法具有明顯優(yōu)勢。

1 問題描述

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

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

表1 符號變量表

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

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

式（4）和（5）中H表示一個很大的數(shù)，兩式聯(lián)立表示任一時刻的任一機(jī)器只能加工一道工序。

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

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

本文使用最大完工時間這一廣泛應(yīng)用的性能指標(biāo)作為約束優(yōu)化問題目標(biāo)函數(shù)，使求取的排程方案的最大完工時間最小。

2 改進(jìn)遺傳算法

2.1 算法流程

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

圖1 改進(jìn)遺傳算法流程圖

步驟1：遺傳算法參數(shù)初始化。

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

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

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

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

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

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

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

2.2 染色體編碼

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

圖2 三層染色體編碼方式

基于工序編碼的編碼規(guī)則可按如下方式描述：對于工序順序?qū)覬S，其為有序數(shù)列，其中第i位上的數(shù)字為x，代表工件編號為x。從第1 位起至第i位，x共出現(xiàn)了k次，則JS 的第i位代表Oxk，即工件x的第k道工序。如圖3 所示。

圖3 JS 基于工序編碼的編碼規(guī)則

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

圖4 MS 基于相對機(jī)器編號的編碼規(guī)則

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

2.3 染色體選擇與交叉

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

2.4 染色體變異

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

同時，為緩解迭代后期種群陷入局部最優(yōu)解，使用隨迭代次數(shù)變化的動態(tài)變異率：

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

2.5 基于動作分解的天車解碼規(guī)則

基于動作分解的天車解碼規(guī)則是通過模擬天車調(diào)度運(yùn)輸?shù)囊幌盗袆幼?，并以一定的采樣時間間隔更新天車坐標(biāo)、天車狀態(tài)和運(yùn)動時間，從而實(shí)現(xiàn)工件與天車調(diào)度排程。天車動作表如表2 所示，表中動作1～8 構(gòu)成天車一次完整調(diào)度動作。分析可知，天車動作可分為兩類調(diào)度動作，第一類為天車靜止動作，此時天車在軌道上保持靜止，僅天車上的小車與鉤爪可進(jìn)行運(yùn)動，放鉤、裝載、卸載和收鉤屬于第一類，耗時可視為定值。第二類為天車移動動作，此時天車在軌道上移動，而天車上的小車和鉤爪將相對于天車保持靜止，前往始發(fā)地、前往目的地屬于第二類。進(jìn)一步分析可知，天車前往始發(fā)地與前往目的地本質(zhì)是一個動作，皆為從軌道上一點(diǎn)移動至另一點(diǎn)。此外，第二類天車動作耗時與天車速度及位移有關(guān)。

表2 天車動作表

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

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

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

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

步驟3：根據(jù)天車間距離判斷是否發(fā)生干涉。是則調(diào)用天車干涉算子collision，collision 進(jìn)一步調(diào)用move；否則調(diào)用天車調(diào)度算子transfer，transfer進(jìn)一步調(diào)用天車移動算子move。算子返回天車坐標(biāo)、天車狀態(tài)，并記錄任務(wù)時間。

步驟4：使用自適應(yīng)采樣時間算子change_dtime 確定下一個采樣時間點(diǎn)，以提高計(jì)算效率。

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

需要說明的是，天車避讓使用基于優(yōu)先級的避讓策略，根據(jù)天車的運(yùn)行狀態(tài)制定優(yōu)先級，如表3所示。優(yōu)先級低的天車需避讓優(yōu)先級高的天車，當(dāng)兩天車優(yōu)先級相同時采取輪流避讓策略。

表3 天車優(yōu)先級制定

表4 給出了本文所提出方法相對標(biāo)準(zhǔn)遺傳算法的改進(jìn)部分及作用。

表4 本文所提出方法相對標(biāo)準(zhǔn)遺傳算法的改進(jìn)部分及作用

3 實(shí)例求解及結(jié)果分析

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

表5 車間環(huán)境變量設(shè)置

表6 工序流程及其耗時

圖6 車間布局示意圖

改進(jìn)遺傳算法及原始遺傳算法的參數(shù)設(shè)置為：種群規(guī)模NP=50，最大迭代次數(shù)G=20，交叉概率Pc=0.8，初始變異概率Pm0=0.01。重復(fù)進(jìn)行5 次實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果中各算法最大完工時間見表7，調(diào)度運(yùn)輸時長見表8。

由表7 和表8 可知，改進(jìn)遺傳算法生成的調(diào)度方案在最大完工時間指標(biāo)上全面優(yōu)于原始遺傳算法，5 次實(shí)驗(yàn)中改進(jìn)遺傳算法的最差排程結(jié)果仍優(yōu)于原始遺傳算法的排程結(jié)果；相對于原始遺傳算法，改進(jìn)遺傳算法的最大完工時間平均減少10.78%，調(diào)度運(yùn)輸耗時平均減少21.62%。此外，改進(jìn)遺傳算法也全面優(yōu)于企業(yè)排程方法；相對于5 次實(shí)驗(yàn)結(jié)果完全相同的企業(yè)排程方法，改進(jìn)遺傳算法的最大完工時間和調(diào)度運(yùn)輸耗時分別平均減少了15.49%和28.08%。

表7 各算法最大完工時間

表8 各算法調(diào)度運(yùn)輸耗時

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

圖7 改進(jìn)遺傳算法與原始遺傳算法的進(jìn)化曲線

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

圖8 改進(jìn)遺傳算法最佳調(diào)度方案對應(yīng)甘特圖

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

圖9 改進(jìn)遺傳算法最佳調(diào)度方案對應(yīng)天車位移圖

圖10 兩天車保持安全距離

上述結(jié)果充分證明了所提出基于改進(jìn)遺傳算法的智能排程方法的有效性和優(yōu)越性。

4 結(jié)語

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