王一荻，李志偉，張文新*，李鐵克，王柏琳

（1.北京科技大學(xué)經(jīng)濟(jì)管理學(xué)院，北京 100083；2.鋼鐵生產(chǎn)制造執(zhí)行系統(tǒng)技術(shù)教育部工程研究中心（北京科技大學(xué)），北京 100083；3.寧波鋼鐵有限公司，浙江寧波 315807）

0 引言

板坯的熱軋生產(chǎn)階段指將板坯加熱后經(jīng)粗軋和精軋機(jī)組進(jìn)行軋制加工，熱軋工藝復(fù)雜導(dǎo)致其生產(chǎn)調(diào)度結(jié)果直接影響訂單交貨期、生產(chǎn)效益和效率等。熱軋批量調(diào)度是熱軋生產(chǎn)階段的重要內(nèi)容，用于確定板坯在熱軋工序的分組和排序，不僅考慮板坯間的工藝約束，同時(shí)還考慮與其他工序的銜接問題［1］。因此，研究熱軋批量調(diào)度問題對(duì)于加速鋼鐵企業(yè)技術(shù)的發(fā)展有重要的理論基礎(chǔ)和現(xiàn)實(shí)意義。

熱軋批量調(diào)度是一類典型的NP 難問題，一直受到眾多國內(nèi)外學(xué)者的研究和關(guān)注。文獻(xiàn)［1］將板坯熱軋批量調(diào)度問題抽象為板坯分配和排序兩個(gè)子問題，并針對(duì)這兩個(gè)部分設(shè)計(jì)了指派啟發(fā)式和排序啟發(fā)式算法；文獻(xiàn)［2］將熱軋批量調(diào)度問題歸結(jié)為帶軟時(shí)間窗的車輛路徑問題，運(yùn)用約束滿足技術(shù)進(jìn)行求解；文獻(xiàn)［3］針對(duì)熱軋批量調(diào)度問題，建立帶鋼分配和排序兩階段問題模型，設(shè)計(jì)兩階段啟發(fā)式規(guī)則對(duì)該模型求解；文獻(xiàn)［4］針對(duì)熱軋批量調(diào)度問題采用改進(jìn)的兩階段人工蜂群算法進(jìn)行求解；文獻(xiàn)［5］針對(duì)板坯批量調(diào)度問題，在優(yōu)化目標(biāo)中額外引入了出爐溫度跳躍懲罰，基于單親遺傳算法對(duì)問題進(jìn)行求解；文獻(xiàn)［6］將熱軋批量計(jì)劃歸結(jié)為車輛路徑問題，并在計(jì)劃數(shù)不確定的情況下求解；文獻(xiàn)［7］將無縫鋼管熱軋批量調(diào)度問題歸結(jié)為依賴順序安裝時(shí)間的流水車間調(diào)度問題，采用分支定界法和兩階段啟發(fā)式算法分別求解不同規(guī)模的調(diào)度問題；文獻(xiàn)［8］針對(duì)無縫鋼管熱軋批量調(diào)度問題，在建立模型時(shí)考慮了配送地址等因素，并設(shè)計(jì)了聚類算法和混合變鄰域算法對(duì)模型進(jìn)行求解；文獻(xiàn)［9］研究了熱軋圓鋼的批量調(diào)度問題，提出了基于規(guī)則的變鄰域搜索算法進(jìn)行求解。

上述文獻(xiàn)針對(duì)靜態(tài)環(huán)境下的熱軋批量調(diào)度問題難以適用于當(dāng)今熱軋生產(chǎn)工序，在實(shí)際的熱軋生產(chǎn)過程中存在許多動(dòng)態(tài)擾動(dòng)，緊急訂單插入、機(jī)器故障等不確定性因素導(dǎo)致初始調(diào)度方案無法繼續(xù)執(zhí)行，因此需要提高鋼鐵企業(yè)應(yīng)對(duì)突發(fā)擾動(dòng)的能力以確保生產(chǎn)過程的連續(xù)穩(wěn)定。文獻(xiàn)［10］針對(duì)鋼廠熱軋生產(chǎn)調(diào)度中出現(xiàn)板坯延遲交貨、未達(dá)到質(zhì)量標(biāo)準(zhǔn)和機(jī)器故障等擾動(dòng)因素，提出了基于約束滿足的優(yōu)化方法，設(shè)計(jì)了變量和值序啟發(fā)式算法；文獻(xiàn)［11］針對(duì)加熱爐-熱軋區(qū)間板坯的生產(chǎn)調(diào)度問題，考慮加熱爐或熱軋機(jī)故障等擾動(dòng)因素建立重調(diào)度模型，運(yùn)用非支配排序遺傳算法對(duì)該問題進(jìn)行求解；文獻(xiàn)［12］針對(duì)熱軋板坯動(dòng)態(tài)調(diào)度問題，分析了生產(chǎn)過程的擾動(dòng)因素，并提出了人機(jī)交互的熱軋動(dòng)態(tài)調(diào)度系統(tǒng)解決該問題?？梢钥闯觯壳皩?duì)熱軋重調(diào)度研究成果較少；此外，熱軋生產(chǎn)通常被抽象為單機(jī)環(huán)境，而單機(jī)重調(diào)度目前取得了一些研究成果［13-17］，但由于熱軋生產(chǎn)的特殊工藝要求，無法直接應(yīng)用于熱軋重調(diào)度問題。

實(shí)際鋼鐵企業(yè)中，經(jīng)常出現(xiàn)隨機(jī)到達(dá)的緊急訂單，對(duì)這類擾動(dòng)事件的快速高效響應(yīng)是生產(chǎn)連續(xù)和質(zhì)量穩(wěn)定的重要保障，也是提升客戶滿意度的關(guān)鍵手段。本文針對(duì)緊急訂單插入這類擾動(dòng)因素，提出基于事件驅(qū)動(dòng)的熱軋生產(chǎn)重調(diào)度策略，并以最小化訂單拖期懲罰和板坯跳躍懲罰加權(quán)和為目標(biāo)，建立熱軋重調(diào)度模型，結(jié)合問題特征，設(shè)計(jì)了基于插入位置的整數(shù)編碼方案和概率模型的分布估計(jì)算法（Evolution of Distribution Algorithm，EDA），最后運(yùn)用實(shí)際生產(chǎn)數(shù)據(jù)驗(yàn)證模型和算法的有效性。

1 問題描述與策略分析

1.1 熱軋批量調(diào)度與緊急訂單插入

在編制熱軋批量計(jì)劃時(shí)，計(jì)劃人員根據(jù)產(chǎn)品的工藝規(guī)范要求對(duì)銷售訂單進(jìn)行選擇并分解成生產(chǎn)訂單（以下簡(jiǎn)稱訂單），生產(chǎn)車間根據(jù)訂單將板坯按照交貨期和軋制寬度、硬度、厚度等工藝規(guī)程進(jìn)行組批構(gòu)成若干軋制單元，進(jìn)而排序形成熱軋批量調(diào)度如圖1 所示，開始生產(chǎn)。在熱軋生產(chǎn)過程中，每個(gè)軋制單元生產(chǎn)后需要留出安裝時(shí)間更換軋輥，因此熱軋批量調(diào)度問題可視為一類考慮安裝時(shí)間和熱軋工藝約束的單機(jī)批量調(diào)度問題。

圖1 熱軋批量調(diào)度示意圖Fig.1 Schematic diagram of hot rolling batch scheduling

相較于一般單機(jī)調(diào)度問題，熱軋生產(chǎn)工藝復(fù)雜。一個(gè)軋制單元內(nèi)的板坯是由燙輥材和主體材兩部分組成的，其中主體材部分是生產(chǎn)的主要階段且數(shù)量較多，單純依靠人工編排耗時(shí)長且很難取得較優(yōu)結(jié)果，因此本文僅考慮主體材部分的軋制工藝規(guī)程。為保證產(chǎn)品質(zhì)量、生產(chǎn)效益且減少對(duì)軋輥磨損的影響，在一個(gè)軋制單元內(nèi)的板坯需要按照軋制規(guī)程有序排列，使主體材滿足以下軋制規(guī)程：

1）軋制寬度應(yīng)盡可能遞減變化，變化要平滑；若軋制寬度反跳時(shí)，跳躍差不能超過150 mm；如遇到同寬板坯連續(xù)軋制，則要求有一定的長度限制。

2）軋制厚度最好向非減的方向變化，變化要平滑。

3）軋制硬度變化平滑且呈現(xiàn)遞增或遞減的變化，禁止反復(fù)跳躍。

4）軋制單元內(nèi)的寬度、厚度、硬度禁止同時(shí)跳躍。

5）當(dāng)軋制寬度、硬度和厚度相互沖突時(shí)，優(yōu)先級(jí)為硬度、厚度、寬度。

6）軋制單元的總軋制長度有一定限制。

在熱軋生產(chǎn)過程中，經(jīng)常出現(xiàn)緊急訂單插入等突發(fā)情況，靜態(tài)調(diào)度模型難以應(yīng)對(duì)熱軋生產(chǎn)的突發(fā)擾動(dòng)情況。緊急訂單作為一類典型的生產(chǎn)擾動(dòng)因素，其熱軋重調(diào)度是實(shí)際生產(chǎn)中亟待解決的難題，對(duì)該問題的研究在理論和實(shí)踐方面均具有重要意義。特別針對(duì)緊急訂單交貨時(shí)長短的情況，只有將訂單中的板坯插入至當(dāng)前調(diào)度方案中才能保證按期交貨的要求。訂單拖期不但會(huì)使企業(yè)產(chǎn)生拖期生產(chǎn)成本，降低車間生產(chǎn)效率，更影響了客戶滿意度，進(jìn)而影響企業(yè)效益。從客戶角度來說，訂單的拖期懲罰越大，客戶滿意度越低，因此本文將最小化拖期懲罰作為一個(gè)優(yōu)化目標(biāo)。此外，熱軋生產(chǎn)有成批生產(chǎn)和連續(xù)性強(qiáng)的特點(diǎn)，生產(chǎn)工藝要求極為嚴(yán)格，以節(jié)約產(chǎn)能，保證產(chǎn)品質(zhì)量和生產(chǎn)節(jié)奏。從生產(chǎn)工藝的角度來說，板坯的跳躍懲罰越小，產(chǎn)品質(zhì)量越穩(wěn)定，且生產(chǎn)效率越高，因此本文將最小化相鄰板坯跳躍懲罰設(shè)為另一優(yōu)化目標(biāo)。

綜上所述，考慮訂單擾動(dòng)的熱軋重調(diào)度問題可以描述為：在t=0 時(shí)刻，熱軋車間按照初始計(jì)劃組織生產(chǎn)；在t=T時(shí)刻，有若干塊緊急板坯到達(dá)，所有板坯的寬度、硬度、厚度、鋼種、重量等屬性均已知，要求在滿足軋制長度限制、軋制規(guī)程、安裝時(shí)間等熱軋生產(chǎn)約束和客戶訂單要求的前提下，確定新板坯的插入位置并生成重調(diào)度方案，使相鄰板坯總跳躍懲罰和訂單拖期懲罰的加權(quán)和最小。

1.2 訂單擾動(dòng)下的重調(diào)度策略

本文采用基于事件驅(qū)動(dòng)的重調(diào)度策略，即以新板坯的到達(dá)作為驅(qū)動(dòng)重調(diào)度的事件。在新板坯到達(dá)時(shí)，根據(jù)各軋制單元的加工狀態(tài)確定重調(diào)度對(duì)象，從而實(shí)時(shí)更新重調(diào)度的開始時(shí)間。重調(diào)度的對(duì)象為新到達(dá)板坯和初始調(diào)度中尚未加工的板坯。設(shè)新板坯在t=T時(shí)刻到達(dá)并需要插入到初始調(diào)度中，此時(shí)初始調(diào)度方案的狀態(tài)分為尚未軋制、正在軋制和軋制完成的軋制單元，假設(shè)重調(diào)度的開始時(shí)間為t1，Pm和Cm分別為軋制單元m的加工時(shí)間和完工時(shí)間，cti為板坯i的完工時(shí)間，s為軋制單元間更換軋輥的安裝時(shí)間。

1）尚未軋制的軋制單元：若軋制單元m在t=T時(shí)刻還未開始軋制，即Cm-Pm≥T，則該軋制單元進(jìn)行重調(diào)度，重調(diào)度的開始時(shí)間為t1=Cm-Pm。

2）正在加工的軋制單元：若軋制單元m在t=T時(shí)刻正在加工，即Cm≥T且Cm-Pm＜T，則尚未軋制的軋制單元進(jìn)行重調(diào)度，重調(diào)度的開始時(shí)間為t1=cti。

3）軋制完成的軋制單元：若軋制單元m在t=T時(shí)刻已經(jīng)軋制完成，即Cm＜T，則對(duì)應(yīng)軋制單元不再進(jìn)行重調(diào)度，重調(diào)度的開始時(shí)間為t1=Cm+s。

基于上述熱軋板坯的加工狀態(tài)、重調(diào)度加工對(duì)象及開始時(shí)間進(jìn)行重調(diào)度，重調(diào)度策略流程如圖2 所示。訂單擾動(dòng)發(fā)生前，根據(jù)已有熱軋批量計(jì)劃執(zhí)行初始生產(chǎn)調(diào)度方案。當(dāng)緊急訂單到達(dá)時(shí)，則需重新確定板坯的加工信息，以進(jìn)行重調(diào)度并生成最新調(diào)度方案。

圖2 熱軋重調(diào)度策略流程Fig.2 Flowchart of hot rolling rescheduling strategy

2 考慮訂單擾動(dòng)的熱軋重調(diào)度模型

2.1 符號(hào)定義

為了便于模型的描述和建立，定義符號(hào)和變量如下：

1）索引與集合。

n為初始板坯數(shù)量，n′-n為新板坯數(shù)量，I為所有軋制板坯編號(hào)的集合，包括初始板坯和新板坯，I=｛0，1，…，n，…，n′｝；

i為軋制板坯編號(hào)，其中i=0 為構(gòu)造的虛擬板坯，構(gòu)造該板坯以確保同一個(gè)軋制單元內(nèi)的板坯順序能夠形成閉環(huán)，即每個(gè)板坯有且僅有一個(gè)前驅(qū)和后繼的板坯，i∈I；

K為軋制單元的集合，K=｛1，2，…，k｝，其中k為軋制單元總數(shù)；

m為軋制單元編號(hào)，m∈K；

Nm為軋制單元m包含軋制板坯的有序集合，Nm（v）表示軋制單元m內(nèi)的第v塊軋制板坯，軋制單元集合為｛N1，N2，…，Nk｝；

δi為與板坯i同寬且連續(xù)軋制的板坯集合。

2）已知參數(shù)。

wi、gi、ri和li分別為板坯i的軋制寬度、硬度、厚度和長度；

wmax、gmax和rmax分別為相鄰板坯間軋制寬度、硬度和厚度變化的最大值；

Lmax為一個(gè)軋制單元的板坯總長度限制；

Qmax為一個(gè)軋制單元內(nèi)連續(xù)軋制同寬板坯的長度限制；

s為軋制單元間更換軋輥的安裝時(shí)間；

pti為板坯i的軋制時(shí)間；

di為板坯i的交貨期，根據(jù)該板坯所屬訂單的交貨期獲得；

α為訂單拖期的懲罰系數(shù)，α∈［0，1］；

M為足夠大的正整數(shù)。

3）決策變量。

cti為板坯i的完工時(shí)間；

qii′為板坯i到板坯i′的跳躍總懲罰值；

、和分別為板坯i到板坯i′的寬度、硬度、厚度的跳躍懲罰值；

Pm和Cm分別為軋制單元m的加工時(shí)間和完工時(shí)間。

2.2 重調(diào)度模型

本文在文獻(xiàn)［5］提出的熱軋生產(chǎn)調(diào)度模型基礎(chǔ)上，考慮緊急訂單插入的擾動(dòng)因素，建立重調(diào)度模型。將新到達(dá)的板坯和發(fā)生擾動(dòng)時(shí)尚未軋制的板坯作為重調(diào)度對(duì)象。不失一般性，提出如下合理假設(shè)：

假設(shè)1 初始調(diào)度方案中的軋制單元及其包含板坯的軋制順序已知且不變。

假設(shè)2 不考慮熱軋機(jī)組故障等其他擾動(dòng)因素。

針對(duì)訂單擾動(dòng)的熱軋重調(diào)度問題，以相鄰板坯總跳躍懲罰和訂單拖期懲罰的加權(quán)和最小為目標(biāo)，建立如下數(shù)學(xué)模型。

目標(biāo)函數(shù)式（1）包含兩層優(yōu)化目標(biāo)：第一層為最小化板坯間由軋制規(guī)格（寬度、硬度、厚度）變化導(dǎo)致的跳躍懲罰，以保證產(chǎn)品質(zhì)量；第二層為最小化總拖期懲罰，以確保按期交貨。

約束條件式（2）～（5）考慮了軋制單元的相關(guān)約束：式（2）表示軋制總長度的上限約束；式（3）表示軋制單元的先后加工順序約束，在加工時(shí)不允許中斷且需要考慮軋輥的安裝時(shí)間；式（4）表示第一個(gè)軋制單元的完工時(shí)間約束；式（5）表示軋制單元和所包含板坯的加工時(shí)長關(guān)系約束。

約束條件式（6）～（16）列出了軋制單元內(nèi)板坯排序約束：式（6）～（12）用于限定板坯間的順序關(guān)系；式（13）～（16）為軋制單元生產(chǎn)的工藝約束，參考文獻(xiàn)［5］構(gòu)建，其中：式（6）表示一塊板坯至多只能在一個(gè)軋制單元內(nèi)生產(chǎn)；式（7）表示虛擬板坯必須被放置在每個(gè)軋制單元內(nèi)，以構(gòu)成回路；式（8）～（9）表示軋制單元內(nèi)的板坯i前后有且僅有一塊板坯；式（10）表示消除子回路；式（11）表示軋制單元內(nèi)板坯的先后加工順序約束；式（12）表示每個(gè)軋制單元內(nèi)以虛擬板坯0 作為起點(diǎn)構(gòu)成回路；式（13）表示連續(xù)軋制同寬板坯的長度上限約束；式（14）～（16）表示保證寬度、硬度、厚度平滑變化且存在跳躍上限的約束。

式（17）為重調(diào)度的特殊約束，表示初始板坯所在的軋制單元保持不變，用于保證重調(diào)度前后的計(jì)劃一致性和生產(chǎn)穩(wěn)定性。

式（18）對(duì)目標(biāo)函數(shù)中的跳躍懲罰進(jìn)行了定義，設(shè)定為相鄰板坯跳躍的懲罰值總和。

約束條件式（19）～（23）為決策變量的取值約束。

3 重調(diào)度的分布估計(jì)算法

基于動(dòng)態(tài)事件的熱軋調(diào)度問題是典型NP 難問題［10］，相較于精確算法，智能優(yōu)化算法可以在較短時(shí)間內(nèi)獲得問題解，滿足實(shí)際生產(chǎn)需求。相較于傳統(tǒng)的遺傳算法，本文分布算法EDA 通過建立概率模型對(duì)初始種群進(jìn)行采樣和學(xué)習(xí)，代替了遺傳算法采用的交叉、選擇和變異操作［18］。概率模型的更新可以表征優(yōu)良解在解空間的分布，并對(duì)概率模型進(jìn)行采樣生成優(yōu)勢(shì)群體，實(shí)現(xiàn)種群進(jìn)化。EDA 具有較強(qiáng)的收斂速率和搜索能力，處理該類問題有更好的性能。本文算法EDA 的流程如圖3 所示。

圖3 本文算法流程Fig.3 Flowchart of the proposed algorithm

由圖3 可以看出：結(jié)合本文問題特征，設(shè)計(jì)算法的關(guān)鍵在于編碼方案、概率模型、適應(yīng)度函數(shù)等方面。概率模型的建立與更新機(jī)制是決定算法有效性的關(guān)鍵。針對(duì)這三個(gè)方面，本文提出了基于插入位置的整數(shù)編碼方案，結(jié)合模型特征提出了概率模型建立與更新方法，并定義了基于懲罰值的適應(yīng)度函數(shù)。

3.1 個(gè)體編碼方案

個(gè)體編碼方案沒有采用傳統(tǒng)的表達(dá)板坯順序的編碼方法，而是設(shè)計(jì)了一種表示緊急訂單中所有板坯插入原調(diào)度位置的編碼方法，這種編碼方式不僅清晰地描述了問題特征，而且縮短了編碼長度，減少了繁瑣的解碼步驟，提高了求解效率。

個(gè)體采用整數(shù)編碼形式，具體設(shè)計(jì)如下：若原調(diào)度方案中有n1塊板坯，重調(diào)度t=T時(shí)刻有n2塊板坯到達(dá)，等待插入至原調(diào)度方案中，定義種群中的個(gè)體編碼由n2個(gè)基因位組成，表示為（x1，x2，…，xn2），其中：xj為整數(shù)，且1 ≤xj ≤i，i=1，2，…，n1。

基因xj表示第j塊新板坯插入原調(diào)度中第i塊板坯后的位置。若xj=xk，則按照xj和xk在個(gè)體中的先后順序決定位置次序。根據(jù)問題模型，在每個(gè)軋制單元內(nèi)引入一塊虛擬板坯，包含在該調(diào)度的板坯數(shù)量中。若xk為虛擬板坯，則表示第k塊新板坯插入該虛擬板坯后的位置，即插入該虛擬板坯所屬軋制單元的首位。

例如，假設(shè)原調(diào)度方案中有6 個(gè)軋制單元，有40 塊原調(diào)度板坯，現(xiàn)有5 塊新板坯，個(gè)體（19，4，25，16，32）的含義為：第1 塊新板坯插入到原調(diào)度方案的第19 塊板坯后，第2 塊新板坯插入到原調(diào)度方案的第4 塊板坯后，依此類推。可以看出，雖然參與調(diào)度的板坯共計(jì)45 塊，但染色體的基因位僅需設(shè)置5 個(gè)，且通過插入方式進(jìn)行解碼，在保證了解碼效率的同時(shí)有效保障了約束（17）被滿足。

3.2 概率模型的建立

相較于遺傳算法的交叉變異操作，EDA 通過概率模型的建立和更新來描述種群進(jìn)化趨勢(shì)。概率模型是EDA 的核心，設(shè)計(jì)合適的概率模型和更新機(jī)制對(duì)EDA 的性能起著決定性的作用。本文設(shè)計(jì)了適用于熱軋重調(diào)度問題特點(diǎn)的概率模型，以提高解決實(shí)際生產(chǎn)難題的合理性和有效性。

本文算法采用n2行n1列的概率模型Pt表示解空間的分布概率，其中t表示進(jìn)化代數(shù)。根據(jù)個(gè)體編碼策略，定義了第t代概率模型矩陣Pt，如式（24）所示：

其中：j表示新板坯序列的索引；i表示原板坯序列的索引表示第t代第j塊新板坯插入到原調(diào)度方案中板坯i緊后位置的概率。

算法選取初始種群中適應(yīng)度值最大的SPsize個(gè)個(gè)體構(gòu)成優(yōu)勢(shì)種群。由于染色體采用基于訂單插入位置的編碼方式，即每個(gè)個(gè)體內(nèi)部基因是離散的，概率模型Pt為優(yōu)勢(shì)種群中每塊新板坯插入原調(diào)度的位置在染色體中每一基因的統(tǒng)計(jì)概率。為提高EDA 的全局搜索能力，應(yīng)保證所選初始種群的隨機(jī)性和均勻性。本文采用概率均勻分布的方法構(gòu)建初始概率模型矩陣P1如下：

根據(jù)初始概率模型隨機(jī)生成Psize規(guī)模的個(gè)體，計(jì)算目標(biāo)函數(shù)值選取最優(yōu)的SPsize個(gè)規(guī)模的個(gè)體，并基于優(yōu)勢(shì)群體采用如下更新機(jī)制更新概率Pt+1。

3.3 概率模型的更新機(jī)制

EDA 新種群的產(chǎn)生依靠概率模型的統(tǒng)計(jì)學(xué)習(xí)公式，使子代個(gè)體可以較大程度地保留父代個(gè)體的優(yōu)良基因，因此一個(gè)合理概率模型的更新機(jī)制對(duì)EDA 性能至關(guān)重要。為了使概率模型更準(zhǔn)確地表示群體的進(jìn)化趨勢(shì)，算法依據(jù)問題模型特征設(shè)計(jì)概率更新模型。更新概率模型Pt采用機(jī)器學(xué)習(xí)中Hebb 規(guī)則，選擇SPsize個(gè)規(guī)模最優(yōu)適應(yīng)度函數(shù)個(gè)體構(gòu)成優(yōu)勢(shì)種群，根據(jù)第t代優(yōu)勢(shì)群體在解空間中的統(tǒng)計(jì)結(jié)果，更新在下一代個(gè)體采樣過程中所依賴的概率模型，即

其中：β（0＜β＜1）表示學(xué)習(xí)因子表示第t+1 代第j塊新板坯插入原調(diào)度方案板坯i后位置的概率；SPsize表示優(yōu)勢(shì)種群規(guī)模；s表示個(gè)體表示第t代個(gè)體s的解空間統(tǒng)計(jì)函數(shù)。的賦值方式如下：

通過不斷地迭代，使概率矩陣趨于成熟。在每次迭代中，通過概率矩陣Pt對(duì)個(gè)體從第x1位至第位順序采樣，對(duì)待確定個(gè)體的位置xj通過輪盤賭的方法選擇板坯i，板坯i被選擇的概率為。采樣生成新種群后，通過適應(yīng)度函數(shù)選擇優(yōu)勢(shì)群體，基于優(yōu)勢(shì)種群采用概率模型的更新機(jī)制更新概率矩陣Pt，如此反復(fù)。在每次計(jì)算適應(yīng)度函數(shù)選擇優(yōu)勢(shì)群體時(shí)采用精英保留策略以保證算法收斂，直到達(dá)到最大迭代次數(shù)，計(jì)算得出最優(yōu)解。

3.4 適應(yīng)度函數(shù)

取目標(biāo)函數(shù)式（1）的倒數(shù)作為適應(yīng)度函數(shù)。求解算法時(shí)可能出現(xiàn)同一軋制單元內(nèi)約束（13）～（16）同寬板坯超過最大限制，板坯寬度、厚度和硬度變化不平滑等不滿足模型約束條件的調(diào)度解。為滿足約束條件，保證解的可行性，將目標(biāo)函數(shù)式（1）調(diào)整為：

其中：F′為修正后的目標(biāo)函數(shù)；F為原目標(biāo)函數(shù)；M為足夠大的正整數(shù)。違反任一約束條件，調(diào)度解經(jīng)過計(jì)算得到的目標(biāo)值均為極大值，那么適應(yīng)度值則極小，通過輪盤賭方法選擇到該個(gè)體的概率接近0，大幅降低了該個(gè)體進(jìn)入到下一代的概率，進(jìn)而達(dá)到識(shí)別并淘汰不可行解的目的。

3.5 算法步驟

在求解考慮訂單擾動(dòng)因素的熱軋重調(diào)度問題時(shí)，基于EDA 的求解步驟如下：

步驟1 輸入算法參數(shù)，包括種群規(guī)模Psize、優(yōu)勢(shì)群體規(guī)模SPsize和學(xué)習(xí)因子β等；

步驟2 初始化種群Psize及隨機(jī)概率矩陣Pt，迭代次數(shù)t=0；

步驟3 計(jì)算種群個(gè)體的適應(yīng)度函數(shù)；

步驟4 根據(jù)適應(yīng)度值從Psize中選取優(yōu)勢(shì)種群SPsize；

步驟5 根據(jù)優(yōu)勢(shì)種群SPsize更新概率模型Pt；

步驟6 采用精英保留策略保存記錄該優(yōu)勢(shì)種群的最優(yōu)解best，并對(duì)概率模型隨機(jī)采樣生成新一代優(yōu)勢(shì)種群SPsize；

步驟7 計(jì)算新一代優(yōu)勢(shì)種群SPsize個(gè)體的適應(yīng)度函數(shù)，更新迭代次數(shù)t=t+1；

步驟8 若t=Tmax，輸出最優(yōu)完整解和目標(biāo)值，否則轉(zhuǎn)至步驟5。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)

為驗(yàn)證本文模型和分布估計(jì)算法性能，設(shè)置對(duì)比算法進(jìn)行實(shí)驗(yàn)。目前未發(fā)現(xiàn)有公開發(fā)行的將緊急訂單插入熱軋生產(chǎn)調(diào)度問題和分布估計(jì)算法結(jié)合的文獻(xiàn)，沒有類似標(biāo)桿算法可以對(duì)比，因此本文與經(jīng)典遺傳算法進(jìn)行比較。本文設(shè)計(jì)的兩個(gè)對(duì)比算法如下：

1）傳統(tǒng)遺傳算法（Traditional Genetic Algorithm，TGA），在熱軋調(diào)度中廣泛應(yīng)用，解決調(diào)度問題經(jīng)典有效［1］。算法采用本文針對(duì)待插入工件位置的編碼策略，傳統(tǒng)遺傳算法的進(jìn)化策略參考文獻(xiàn)［1］。

2）單親遺傳算法（Parent Genetic Algorithm，PGA），采用本文的編碼策略，基于文獻(xiàn)［5］的單點(diǎn)基因換位方式執(zhí)行交叉操作。

本文選用某大型現(xiàn)代化鋼鐵聯(lián)合企業(yè)煉鋼廠的實(shí)際生產(chǎn)訂單數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，采集了合理的初始調(diào)度方案及新訂單數(shù)據(jù)樣本。將初始調(diào)度方案板坯的數(shù)據(jù)按照板坯編號(hào)、板坯所屬軋制單元、所屬訂單交貨期、軋制寬度、軋制硬度、軋制厚度、軋制長度、軋制時(shí)長等屬性整理；將新訂單的數(shù)據(jù)按照板坯編號(hào)、所屬訂單交貨期、軋制寬度、軋制硬度、軋制厚度、軋制長度、軋制時(shí)長等屬性整理；將初始調(diào)度方案軋制單元的數(shù)據(jù)按照軋制單元編號(hào)、軋制數(shù)量、軋制單元時(shí)長、軋制長度等屬性整理。由于新板坯到達(dá)時(shí)間的不確定性，采集了板坯的不同到達(dá)時(shí)間作為數(shù)據(jù)樣本進(jìn)行仿真實(shí)驗(yàn)。由于鋼鐵企業(yè)中板坯的軋制時(shí)長一般用分鐘（min）計(jì)算，交貨期用天（day）計(jì)算，因此為方便統(tǒng)計(jì)，統(tǒng)一單位為min?；谠摕掍搹S的實(shí)際情況并借鑒已有文獻(xiàn)確定軋制寬度、硬度、厚度的跳躍懲罰值如表1～3 所示，拖期懲罰系數(shù)可依照工廠實(shí)際對(duì)拖期和跳躍懲罰的權(quán)重確定，本文依據(jù)某大型現(xiàn)代化鋼鐵聯(lián)合企業(yè)煉鋼廠的設(shè)定數(shù)據(jù)，令α=0.5；根據(jù)某煉鋼廠的實(shí)際生產(chǎn)情況，并根據(jù)參考文獻(xiàn)［19］，確定每個(gè)軋制單元總長度限制為Qmax=40 km，同寬板坯軋制長度限制為Lmax=100 km，換輥時(shí)間為s=30 min。

表1 寬度跳躍懲罰值Tab.1 Width jump penalty value

表2 硬度跳躍懲罰值Tab.2 Hardness jump penalty value

表3 厚度跳躍懲罰值Tab.3 Thickness jump penalty value

由上述采集到的數(shù)據(jù)樣本，將問題規(guī)模設(shè)置為新板坯到達(dá)數(shù)量n2=50，100，150，200。對(duì)于板坯到達(dá)時(shí)間的設(shè)置，考慮到實(shí)驗(yàn)數(shù)據(jù)設(shè)有5 個(gè)軋制單元，在初始調(diào)度方案中的開始軋制時(shí)間依次為0 min、1 020 min、1 370 min、1 830 min、2 130 min，因此依據(jù)前3 個(gè)軋制單元的開始軋制時(shí)間設(shè)置了板坯到達(dá)時(shí)間t=200，1 020，1 370。根據(jù)問題規(guī)模進(jìn)行12 組仿真實(shí)驗(yàn)，每組隨機(jī)生成20 個(gè)算例。經(jīng)測(cè)試，運(yùn)行設(shè)置參數(shù)如下：種群規(guī)模M=200，優(yōu)勢(shì)種群數(shù)量B=70，學(xué)習(xí)速率β=0.3，最大迭代次數(shù)T=500。由于每個(gè)重調(diào)度時(shí)刻參與重調(diào)度的板坯數(shù)量不同，為方便比較分析，運(yùn)行參數(shù)與上述設(shè)置相同。

實(shí)驗(yàn)分為兩部分：第一部分為算法性能分析，對(duì)相同的問題采用不同的算法評(píng)估比較；第二部分針對(duì)本文算法，設(shè)計(jì)了新板坯數(shù)量和板坯到達(dá)時(shí)間對(duì)重調(diào)度性能的影響實(shí)驗(yàn)。本文算法使用Matlab R2020a 編寫，運(yùn)行在Intel i7-1065G7 CPU@1.30 GHz 1.50 GHz/8.00 GB 的硬件環(huán)境下。

4.2 算法性能分析

算法的性能從有效性和運(yùn)行時(shí)間兩方面對(duì)比分析。在有效性方面，以目標(biāo)值為評(píng)價(jià)指標(biāo)。針對(duì)12 組問題規(guī)模分別用上述算法求解，分別計(jì)算每種算法的均值avg和標(biāo)準(zhǔn)差Std，并采用方差分析（ANalysis Of VAriance，ANOVA）對(duì)每組實(shí)驗(yàn)進(jìn)行顯著性檢驗(yàn)（γ=0.05）。實(shí)驗(yàn)結(jié)果見表4，最后兩列為每組實(shí)驗(yàn)方差分析的F和P-value值。在運(yùn)行時(shí)間方面，上述算法求解不同問題規(guī)模的處理時(shí)間（CPU 時(shí)間）如表5所示。

表4 不同算法的均值、標(biāo)準(zhǔn)差和方差分析的對(duì)比分析結(jié)果Tab.4 Comparative analysis results of different algorithms of mean，standard deviation and variance analysis

表5 不同算法的CPU時(shí)間對(duì)比Tab.5 CPU time comparison of different algorithms

從表4 的avg指標(biāo)和std指標(biāo)來看，除了1 020×50 的規(guī)模問題外，EDA 在其他規(guī)模問題上均取得了最小平均值。說明在EDA 迭代過程中通過概率模型的更新學(xué)習(xí)保留了優(yōu)勢(shì)個(gè)體基因，使優(yōu)良基因概率不斷增大，從而引領(lǐng)新一代優(yōu)勢(shì)個(gè)體的產(chǎn)生。EDA 的avg和Std的平均值均為最低值，說明EDA 的尋優(yōu)能力強(qiáng)，求解穩(wěn)定性好。每組實(shí)驗(yàn)進(jìn)行ANOVA分析得到的P-value均小于0.05，且隨著n2或者t的增加，P-value呈顯著下降趨勢(shì)，說明三種算法對(duì)于調(diào)度目標(biāo)值存在顯著影響，而且隨著板坯數(shù)量增加或到達(dá)時(shí)間增加，差異愈加明顯，從而驗(yàn)證了本文所提EDA 的優(yōu)越性。

從表5 的CPU 指標(biāo)角度來看，針對(duì)不同的問題規(guī)模，TGA 和PGA 的求解效率均高于EDA，這是由于選擇優(yōu)勢(shì)群體以更新概率模型導(dǎo)致的。相較于TGA 和PGA 在初始種群上進(jìn)行的交叉變異操作，EDA 基于采樣生成了新優(yōu)勢(shì)群體從而進(jìn)行概率模型的學(xué)習(xí)與更新，導(dǎo)致求解時(shí)間較長，但是EDA 在尋優(yōu)能力和求解穩(wěn)定性上均優(yōu)于其他算法。而且目前多數(shù)鋼鐵企業(yè)對(duì)熱軋批量計(jì)劃采用人工編排的方式，對(duì)考慮訂單擾動(dòng)的熱軋重調(diào)度問題，人工編排的效率低、耗時(shí)長，EDA 的計(jì)算時(shí)間顯然小于人工編排的時(shí)間。即使對(duì)板坯到達(dá)時(shí)間較早（t=200 min）和大規(guī)模新板坯到達(dá)（n2=200）的情況下，EDA 也能在450 s 內(nèi)給出調(diào)度方案，因此該算法解決了鋼廠實(shí)際存在的問題，完全滿足生產(chǎn)需要。

為更直觀反映本文設(shè)計(jì)算法的收斂效率和尋優(yōu)能力，隨機(jī)挑選一個(gè)規(guī)模為100×200 的算例，圖4 給出了三種算法在迭代500 代時(shí)的收斂曲線對(duì)比。

圖4 不同算法的收斂曲線對(duì)比Fig.4 Comparison of convergence curves of different algorithms

從圖4 可以看出，在收斂效率上，EDA 在132 代取得了穩(wěn)定值，而TGA 在301 代取得了穩(wěn)定值，收斂速率不及EDA；在尋優(yōu)能力上，EDA 的目標(biāo)值為75 均低于TGA 和PGA 的目標(biāo)值152 和135。雖然PGA 和EDA 的收斂效率相差不大，但EDA 得到的解明顯優(yōu)于PGA。以上結(jié)果表明，EDA 具有良好的收斂效率和求解質(zhì)量。

三種算法的目標(biāo)值均低于目標(biāo)函數(shù)設(shè)置的懲罰值M，說明了結(jié)果的有效性，從而驗(yàn)證本文的模型和算法能夠解決熱軋重調(diào)度問題。

4.3 新板坯數(shù)量和到達(dá)時(shí)間對(duì)重調(diào)度性能的影響

新板坯數(shù)量n2和板坯到達(dá)時(shí)間t是影響重調(diào)度性能的關(guān)鍵參數(shù)，本節(jié)分別探討兩種因素對(duì)重調(diào)度性能指標(biāo)的影響。對(duì)于新板坯數(shù)量的影響，本節(jié)對(duì)4 個(gè)實(shí)驗(yàn)組n2=50，100，150，200 的目標(biāo)值進(jìn)行均值及95%置信區(qū)間的分析，如圖5 所示。對(duì)于板坯達(dá)到時(shí)間的影響，對(duì)3 個(gè)實(shí)驗(yàn)組t=200，1 020，1 370的目標(biāo)值進(jìn)行均值及其95%置信區(qū)間的分析，如圖6 所示。

1）新板坯數(shù)量對(duì)重調(diào)度目標(biāo)值的影響。

圖5 中的每條曲線表示了相同到達(dá)時(shí)間下，重調(diào)度目標(biāo)值隨新板坯數(shù)量增多所呈現(xiàn)出的變化趨勢(shì)。當(dāng)板坯到達(dá)時(shí)間t一定時(shí)，調(diào)度目標(biāo)值隨新板坯數(shù)量n2的增加呈逐漸增長的趨勢(shì)。隨著新板坯數(shù)量的增加板坯間的總跳躍懲罰和訂單拖期懲罰的總和增大。當(dāng)新板坯數(shù)量從50 增加到100 時(shí)，增長較為緩慢；當(dāng)新板坯數(shù)量從100 增加到150 時(shí)，曲線斜率變化較為明顯；當(dāng)新板坯數(shù)量從150 增加到200 時(shí)，由于板坯密集到達(dá)，跳躍懲罰增加且參與重調(diào)度的原板坯延后時(shí)間較長導(dǎo)致拖期懲罰增加，因此曲線斜率顯著增大。以上分析說明新板坯數(shù)量的增加對(duì)調(diào)度目標(biāo)值的增長幅度影響較為顯著；并且置信區(qū)間沒有重疊，表明針對(duì)板坯的不同到達(dá)時(shí)間對(duì)重調(diào)度目標(biāo)值有較為顯著的差異。

圖5 板坯的到達(dá)數(shù)量對(duì)目標(biāo)值的影響及其95%置信區(qū)間Fig.5 Influence of arrival quantity of slab on target value and its 95%confidence interval

2）板坯到達(dá)時(shí)間對(duì)重調(diào)度目標(biāo)值的影響。

圖6 中的每條曲線表示了相同新板坯數(shù)量下，重調(diào)度目標(biāo)值隨板坯到達(dá)時(shí)間增大所呈現(xiàn)出的變化趨勢(shì)。隨著板坯到達(dá)時(shí)間t的增大，尚未軋制的原板坯數(shù)量減少，新板坯可選擇的位置減少，導(dǎo)致跳躍懲罰增大，且生產(chǎn)調(diào)度臨近交貨期導(dǎo)致訂單拖期懲罰增大。

圖6 板坯的到達(dá)時(shí)間對(duì)目標(biāo)值的影響及其95%置信區(qū)間Fig.6 Influence of arrival time of slab on target value and its 95%confidence interval

由圖6 可以看出，曲線在整體上呈現(xiàn)增長的趨勢(shì)。這是由于隨著時(shí)間的推進(jìn)，新板坯到達(dá)數(shù)量在板坯總量中的占比增加，對(duì)目標(biāo)值有一定影響。200 ＜t≤1 020 時(shí)，新板坯相較于原板坯數(shù)量占比不大，因此板坯到達(dá)時(shí)間對(duì)重調(diào)度目標(biāo)值影響較小，曲線增長相對(duì)緩慢；1 020 ＜t≤1 370 時(shí)，新板坯占比變大，對(duì)目標(biāo)值的影響逐漸增強(qiáng)，曲線斜率呈現(xiàn)增大趨勢(shì)，因此曲線的增長幅度會(huì)逐漸加大；隨著板坯到達(dá)數(shù)量的逐漸增多，在板坯總量中的占比增加，因此數(shù)量較大時(shí)曲線的增長幅度要大于數(shù)量較少時(shí)的增長幅度。以上分析說明：板坯到達(dá)時(shí)間的增加對(duì)調(diào)度目標(biāo)值的增長幅度影響呈現(xiàn)逐漸增強(qiáng)的趨勢(shì)，且隨著新到達(dá)板坯數(shù)量的增加，該趨勢(shì)表現(xiàn)得更為明顯。圖中置信區(qū)間沒有重疊，表明針對(duì)板坯的不同到達(dá)數(shù)量對(duì)重調(diào)度目標(biāo)值有較為顯著的差異。

5 結(jié)語

本文針對(duì)訂單到達(dá)的情況導(dǎo)致熱軋生產(chǎn)過程中出現(xiàn)擾動(dòng)的問題，以最小化訂單拖期懲罰和板坯間總跳躍懲罰加權(quán)和為優(yōu)化目標(biāo)展開研究。首先，根據(jù)緊急訂單到達(dá)這類動(dòng)態(tài)事件在熱軋生產(chǎn)中的特點(diǎn)，以新到達(dá)的板坯和發(fā)生擾動(dòng)時(shí)尚未軋制的板坯作為重調(diào)度對(duì)象，設(shè)計(jì)了基于事件驅(qū)動(dòng)策略的重調(diào)度方法和流程，提出了考慮訂單擾動(dòng)的熱軋重調(diào)度優(yōu)化模型。進(jìn)而，針對(duì)基于訂單擾動(dòng)的熱軋重調(diào)度的問題特點(diǎn)，設(shè)計(jì)了一種分布估計(jì)算法。該算法具有以下特點(diǎn)：1）采用基于插入位置的方式進(jìn)行編碼，以縮短編碼長度并減少解碼步驟，進(jìn)而提高求解效率；2）定義了基于懲罰值的適應(yīng)度函數(shù)，通過懲罰機(jī)制實(shí)現(xiàn)對(duì)不可行解的識(shí)別與淘汰；3）根據(jù)問題特征設(shè)計(jì)了概率公式并更新了概率模型，根據(jù)進(jìn)化趨勢(shì)動(dòng)態(tài)指導(dǎo)種群的進(jìn)化方向；4）引入精英保留策略保存每一代的最優(yōu)解，以保證算法的收斂性。最后，基于國內(nèi)某大型現(xiàn)代化鋼鐵聯(lián)合企業(yè)的實(shí)際生產(chǎn)數(shù)據(jù)，設(shè)計(jì)了仿真對(duì)比實(shí)驗(yàn)，驗(yàn)證了該模型和算法的有效性，并檢驗(yàn)了動(dòng)態(tài)到達(dá)的訂單數(shù)量和到達(dá)時(shí)間對(duì)熱軋生產(chǎn)調(diào)度的影響。實(shí)驗(yàn)結(jié)果表明，板坯到達(dá)時(shí)間的增加導(dǎo)致調(diào)度目標(biāo)值的明顯增長，且隨著新到達(dá)板坯數(shù)量的增加，調(diào)度目標(biāo)值的增長幅度明顯加大，這兩種因素對(duì)于調(diào)度目標(biāo)均有顯著影響。因此，如何考慮設(shè)置合理的訂單數(shù)量閾值作為重調(diào)度的觸發(fā)機(jī)制將是我們下一步的研究方向。