吳子軒，李鐵克，張文新，王柏琳，王建建

(1.北京科技大學(xué)東凌經(jīng)濟管理學(xué)院，北京 100083；2.鋼鐵生產(chǎn)制造執(zhí)行系統(tǒng)技術(shù)教育部工程研究中心，北京 100083)

1 引言

無縫鋼管作為一種重要的工業(yè)生產(chǎn)資料，廣泛用于國民經(jīng)濟的各個生產(chǎn)領(lǐng)域，企業(yè)通常按照外徑、壁厚、鋼種、長度等參數(shù)將鋼管劃分成不同的規(guī)格，將滿足一定條件的訂單按規(guī)格統(tǒng)一組織，實現(xiàn)批量化生產(chǎn)。一套完整的現(xiàn)代熱軋無縫鋼管生產(chǎn)要經(jīng)過鋼坯加熱、穿孔、連軋、張減定徑和精整、熱處理等多道工序，跨越數(shù)個作業(yè)區(qū)。其中連軋工序是無縫鋼管生產(chǎn)的重中之重。熱軋軋制訂單計劃決定了整條產(chǎn)線的生產(chǎn)節(jié)奏和前后工序的工藝調(diào)整，并直接影響到訂單交付和成品物流配送。

目前關(guān)于熱軋無縫鋼管訂單排程問題的研究并不多見，與之相關(guān)的研究有：王海鳳等[1]在假設(shè)組批完成的前提下，以生產(chǎn)跳躍懲罰最小為目標(biāo)給出熱軋無縫鋼管生產(chǎn)排序問題的約束滿足模型；Tang Lixin和Huang Lin[2]認(rèn)為熱軋無縫鋼管的生產(chǎn)具有以下四個特點：批量可調(diào)度性、生產(chǎn)多階段性、品種規(guī)格的多樣性且機器調(diào)整時間因批量規(guī)格而異；李建祥等[3]總結(jié)出7條關(guān)于鋼管組批和排序的規(guī)則，對鋼管的生產(chǎn)計劃和調(diào)度的研究具有借鑒意義；Li Lin等[4]研究了寶山無縫鋼管廠冷區(qū)生產(chǎn)調(diào)度問題，針對現(xiàn)實生產(chǎn)約束提出了混合流水車間調(diào)度問題的混合整數(shù)非線性規(guī)劃模型；Jia Shujin等[5]將熱軋批量調(diào)度問題歸結(jié)為基于獎金收集車輛路徑問題并提出多目標(biāo)優(yōu)化模型；許紹云等[6]以最大化產(chǎn)能利用率、最小化機器調(diào)整時間和訂單提前拖期為優(yōu)化目標(biāo)，建立針對圓鋼熱軋批量調(diào)度問題的多目標(biāo)整數(shù)規(guī)劃模型；Jia Shujin等[7]將熱軋批量調(diào)度問題歸結(jié)為一個帶雙時間窗的車輛路徑問題的多目標(biāo)模型。熱軋訂單排程問題屬于NP難的組合優(yōu)化問題，目前多采用智能優(yōu)化算法和聚類算法相結(jié)合的方式求解。其中，王海鳳等[1]設(shè)計了節(jié)點互換算法解決無縫鋼管生產(chǎn)計劃中的生產(chǎn)排序問題；Jia Shujin等[5]使用基于分解策略和帕累托最優(yōu)的蟻群算法對模型進(jìn)行求解；許紹云等[6]提出一種改進(jìn)的帶精英策略的快速非支配排序算法對批量調(diào)度模型進(jìn)行求解；張文學(xué)和李鐵克[8]針對面向復(fù)雜生產(chǎn)工藝的三階段一體化批量計劃模型(無優(yōu)化目標(biāo))，考慮到問題的NP難特點，提出了將約束傳播技術(shù)嵌入到聚類分析中的求解算法。

上述研究提供了良好的基礎(chǔ)，但在以下方面尚需進(jìn)一步研究：在研究對象方面，首先，已有研究大多關(guān)注訂單的生產(chǎn)因素，如產(chǎn)品規(guī)格、生產(chǎn)工藝等，對交貨因素等其他屬性則考慮甚少。而在目前的市場環(huán)境下，訂單交付能力日漸成為鋼鐵企業(yè)一項核心競爭力，相近交貨日期和地址的訂單集中生產(chǎn)能提高運輸效率，訂單交貨期的滿足能提高客戶滿意度。因此有必要在訂單排程中考慮交貨因素；其次，熱軋訂單排程是源于現(xiàn)實中的生產(chǎn)管理問題，但據(jù)作者所知已有研究多單獨研究組批或排序問題，未有建立集成模型對訂單排程問題展開研究的。在求解算法方面，熱軋訂單排程問題是NP難的，難以使用精確算法求得最優(yōu)解。我們在算法設(shè)計過程中發(fā)現(xiàn)：由于鋼鐵產(chǎn)品具有嚴(yán)苛的生產(chǎn)工藝要求，一般智能優(yōu)化方法既難以有效構(gòu)建合適的初始解，也易在計算中產(chǎn)生不可行解或陷入局部最優(yōu)，傳統(tǒng)智能優(yōu)化算法如何更好應(yīng)用于工程優(yōu)化問題尚需進(jìn)一步研究[9]。因此需要根據(jù)問題特征來設(shè)計和改進(jìn)優(yōu)化算法?；谏鲜龇治觯疚膶⒀芯靠紤]訂單交貨期、配送地址等交貨因素的熱軋無縫鋼管訂單排程問題，設(shè)計集成訂單組批和批量排序的訂單排程數(shù)學(xué)模型，進(jìn)而針對模型特征設(shè)計基于聚類和混合變鄰域搜索的兩階段求解算法。

2 問題建模

2.1 問題描述

在企業(yè)與客戶簽訂供貨合同后，生產(chǎn)部門將銷售合同分解為生產(chǎn)訂單并進(jìn)行訂單排程，而后將訂單排程計劃下發(fā)給生產(chǎn)車間和原料廠，原料廠根據(jù)排程計劃供應(yīng)鋼坯。生產(chǎn)訂單是企業(yè)對銷售合同的分解和再處理，便于合同排產(chǎn)，因此同一生產(chǎn)訂單內(nèi)的產(chǎn)品具有相同的工藝屬性要求。熱軋訂單排程是在銷售合同分解為生產(chǎn)訂單(以下統(tǒng)稱為“訂單”)后，將一段時間內(nèi)一定數(shù)量的訂單按照軋制規(guī)格(外徑、鋼種、壁厚、長度等)工藝屬性和交貨時間、交貨地址等交貨屬性進(jìn)行訂單組批，形成熱軋批次(以下簡稱為“軋批”)，再將軋批排定生產(chǎn)次序的過程。訂單排程的最終結(jié)果是一系列有序的軋批，每個軋批具有相同的工藝屬性和相似的交貨屬性。一個軋批可以包含單個或多個訂單，每個訂單只能屬于一個軋批。排程過程中要充分考慮生產(chǎn)和交貨中的成本因素，避免因為切換規(guī)格導(dǎo)致頻繁的機器設(shè)備調(diào)整，避免過多的中間庫存和成品庫存堆積。此外，不同于以往研究，本文重點考慮了合同的交貨期和交貨地址，使具有相似交貨屬性的訂單盡量集中生產(chǎn)并交付。

2.2 模型假設(shè)

對于考慮合同交貨的熱軋無縫鋼管訂單排程優(yōu)化問題，根據(jù)生產(chǎn)實際提出如下合理假設(shè)：

(1)僅考慮由軋制規(guī)格變化所引發(fā)的機器設(shè)備調(diào)整，且不同規(guī)格切換引發(fā)的調(diào)整時間相同，不考慮設(shè)備突發(fā)故障和現(xiàn)場突發(fā)事故等動態(tài)情況；

(2)在生產(chǎn)過程中，機器設(shè)備的調(diào)整成本與相鄰批次外徑差和鋼種差的絕對值成正比，其中，外徑差和鋼種差是按照工廠對外徑、鋼種差異的界定轉(zhuǎn)化為數(shù)字表示；

(3)忽略不同訂單的備存成本差異，庫存成本由訂單的提前生產(chǎn)產(chǎn)生；

(4)本文問題考慮的是生產(chǎn)訂單，即合同訂單按產(chǎn)品和產(chǎn)量分解后用于指導(dǎo)生產(chǎn)的訂單，同一訂單內(nèi)的產(chǎn)品具有相同屬性。

2.3 符號定義

為了便于模型的描述和建立，給出符號和變量如下：

(1)索引與集合

I為所有計劃軋制批編號的集合，I={1,2,…,n}；i為軋制批次編號，i∈I；

J為訂單的集合J={1,2,…,m}，其中m為訂單總數(shù)；j為訂單編號，j∈J；

Li為軋制批次i所包含的訂單有序集合，Li(v)表示軋批i內(nèi)的第v個訂單；軋制計劃集合為{L1,L2…Ln}。

(2)符號定義

Pd為相鄰批次外徑變化造成機器調(diào)整的懲罰參數(shù)，Pd∈[0,1]；

Psg為相鄰批次鋼種變化造成機器調(diào)整的懲罰參數(shù)，Psg∈[0,1]；

Pte,Ptl分別為訂單提前和訂單拖期的單位時間懲罰參數(shù)，Pte,Ptl∈[0,1]；

dj,wj,sgj,lj分別為訂單j的軋制外徑、壁厚、鋼種和長度；

[dsj,dej]為訂單j的交貨期窗口；

(aj,bj)為訂單j的配送地坐標(biāo)；

ptj為為訂單j的計劃軋制時長；

qtyj為為完成訂單j所需要軋制的管坯數(shù)量；

deti為軋批i的最晚交貨期，根據(jù)該軋批所包含訂單集合的最晚交貨期求得；

zmax為單個批次所允許的最大軋制數(shù)量；

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

(3)決策變量

sti,eti分別為軋批i的開工時間和完工時間；

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

針對熱軋無縫鋼管訂單排程問題，建立以機器設(shè)備調(diào)整、提前/拖期和配送地域差異度最小為目標(biāo)的數(shù)學(xué)模型，具體如下：

minF1=

(1)

(2)

(3)

s.t.

|dj-dj′|·xij·xij′=0,j,j′∈J,i∈I

(4)

|wj-wj′|·xij·xij'=0,j,j′∈J,i∈I

(5)

|sgj-sgj′|·xij·xij′=0,j,j′∈J,i∈I

(6)

|lj-lj′|·xij·xij′=0,j,j′∈J,i∈I

(7)

(8)

(9)

xij·xi′j=0,j∈J,i≠i′,i,i′∈I

(10)

(11)

(12)

(13)

(sti′-eti)·yii′≥0,i,i′∈I

(14)

sti,eti≥0,i∈I

(15)

xij,yii′∈{0,1},i∈I,j∈J

(16)

目標(biāo)函數(shù)(1)表示在組批過程中最小化每個批次內(nèi)所包含訂單配送中心地理位置的差異。目標(biāo)函數(shù)(2)表示最小化軋批間軋制規(guī)格(外徑、鋼種)切換所導(dǎo)致的機器設(shè)備調(diào)整的頻率；目標(biāo)函數(shù)(3)表示最小化提前和拖期生產(chǎn)懲罰使訂單能夠適期生產(chǎn)，針對提前生產(chǎn)或拖期的懲罰值各不相同。

約束(4)～(12)與組批相關(guān)，其中，約束(4)表示同一批次內(nèi)的訂單外徑相同；約束(5)表示同一批次內(nèi)的訂單壁厚相同；約束(6)表示同一批次內(nèi)的訂單鋼種相同；約束(7)表示同一批次內(nèi)的訂單長度相同；約束(8)表示受鋼坯生產(chǎn)供應(yīng)、生產(chǎn)管理因素和軋機、軋輥、定徑機可用的最大生產(chǎn)能力的影響，一個批次內(nèi)的軋制數(shù)不超過預(yù)先設(shè)定的最大值，這也間接約束了可排入同批生產(chǎn)的訂單；約束(9)表示一個批次至少包含一個訂單；約束(10)表示一個訂單只能匹配給一個批次；約束(11)表示軋批的最晚交貨期，根據(jù)該軋批所包含訂單集合的最晚交貨期求得；約束(12)表示所有訂單都參與組批。

約束(13)～(15)與排序相關(guān)，其中，約束(13)表示軋批在軋制時不允許中斷；約束(14)表示前一個軋批軋制完成后下一個軋批才能開始軋制；約束(15)表示開始和結(jié)束時間非負(fù)。

約束(16)為整數(shù)變量的取值約束。

3 求解算法

本文的熱軋無縫鋼管訂單排程模型是一類多目標(biāo)、多約束的混合整數(shù)規(guī)劃模型，且在實際生產(chǎn)中，由于生產(chǎn)連續(xù)性的要求，同期生產(chǎn)的訂單規(guī)模往往較大，難以采用精確算法在有限時間內(nèi)取得問題的解。為了提高求解效率及解的有效性，本文結(jié)合無縫鋼管成批量的生產(chǎn)特征，設(shè)計了一種兩階段混合優(yōu)化算法。第一階段基于帶凝聚策略的層次聚類思想設(shè)計了一種訂單聚類算法，進(jìn)行訂單組批并形成初始軋制計劃，第二階段使用嵌入模擬退火思想的變鄰域搜索算法對初始批次進(jìn)行排程優(yōu)化。

3.1 初始排程

本階段首先對訂單進(jìn)行組合，并形成初始軋制批次，在此過程中遵循以下兩類原則：①工藝屬性相同性原則；②交貨屬性相似性原則。工藝屬性相同性是指同一批次內(nèi)的訂單必須具有相同的規(guī)格以滿足熱軋鋼管軋制工藝規(guī)范要求，這也符合成組技術(shù)[10]的思想，實現(xiàn)集中生產(chǎn)以降低成本。交貨屬性相似性是指同一軋批內(nèi)不同訂單交貨時間和配送地址允許具有一定相近性，而不要求完全相同。層次聚類是聚類分析的一個分支，它是一種用于形成群體或集群的系統(tǒng)性方法，具有高計算性的特點，通過按照某種策略對數(shù)據(jù)集進(jìn)行層次分解，直至條件得到滿足[11]。目前層次聚類方法已經(jīng)廣泛應(yīng)用于解決與生產(chǎn)制造和供應(yīng)鏈物流配送相關(guān)的問題[12]。本文改進(jìn)了層次聚類算法，通過在訂單預(yù)處理階段考慮工藝約束，并在聚類中心和相對距離的計算中融入了訂單的交貨時間和交貨地址，設(shè)計了一種訂單聚類算法(Order clustering algorithm, OCA)來滿足交貨屬性相似性要求。

3.1.1 訂單預(yù)處理

3.1.2 基于聚類的初始軋批生成

通過預(yù)處理得到的粗批次滿足了約束(4)～(7)，需要進(jìn)一步優(yōu)化以實現(xiàn)訂單初始排程，最小化批次內(nèi)訂單的差異性，實現(xiàn)交貨屬性相似性的要求。根據(jù)分類原理的不同，層次聚類可以分為凝聚和分裂兩種策略[13]。本文需要將每個粗批次內(nèi)分散的訂單進(jìn)行聚類形成初始軋批，因此根據(jù)問題特征選用凝聚策略。

此外，若在訂單組批階段就考慮交貨期相似性，能夠為排序優(yōu)化階段提供良好的初始解，提高目標(biāo)函數(shù)(3)的優(yōu)化效率和效果。為此，在這里提出最小化批次內(nèi)訂單交貨期的差異值的優(yōu)化目標(biāo)，作為目標(biāo)函數(shù)(3)的輔助目標(biāo)，見式(17)。式(1)和(17)是衡量訂單間的相似程度進(jìn)而設(shè)計訂單間距離公式的重要依據(jù)。

(17)

在帶凝聚策略的層次聚類算法中，初始聚類中心的選擇會對聚類結(jié)果產(chǎn)生重要影響。本文通過在每個粗批次內(nèi)計算訂單間相對距離以表示訂單相似度的方法，取最小相對距離為初始聚類中心(新類)，并不斷將與初始聚類中心相對距離最小的訂單加入該類中直至達(dá)到單批產(chǎn)能限制為止，計算新聚類中心。

為計算訂單間的相對距離并得到聚類中心，可以將訂單數(shù)值化描述為：j(otj,odj)，其中otj為訂單j的交貨期窗口[dsj,dej]；odj(aj,bj)為訂單j交貨地址的坐標(biāo)，即成品配送的地理位置。對于Li′內(nèi)的兩個不同訂單j,j′，我們設(shè)計了公式(18)來計算兩訂單間的相對距離，其中(dsj+dej)/2-(dsj′+dej′)/2反映了訂單間交貨期的相對差異，(aj-aj′)2+(bj-bj′)2反映了訂單間配送位置的相對差異。

(18)

對于聚類中心，算法采用一個類中所有訂單間相對距離的算術(shù)平均值來表示，該值在聚類過程中是不斷變化的，計算公式見式(19)，其中r為當(dāng)前聚類中心所包含訂單的總數(shù)。

avg(ot,od)=([∑ds/r,∑de/r], (∑a/r,∑b/r))

(19)

3.1.3 初始排程的算法步驟

形成初始批次{L1,L2…Ln}的算法步驟如下：

步驟6 終止條件判斷

該新類作為初始批次Li，輸出初始批次集合{L1,L2…Ln}；若L'c≠φ，則令i←i+1，執(zhí)行步驟2；若c

3.2 排程優(yōu)化

基于OCA得到的訂單排程是問題的一個可行解，但在最小化機器調(diào)整時間和適期交貨方面還需要進(jìn)一步優(yōu)化。若將每個初始軋批視為工件，將熱軋過程視為處理機，本階段問題可抽象為一類考慮交貨期和機器調(diào)整的單機調(diào)度問題。Arroyo等[14]證明了在最小化提前/拖期和序列相關(guān)機器設(shè)置時間的單機調(diào)度問題中應(yīng)用變鄰域搜索算法是可行的。變鄰域搜索(Variable Neighborhood Search, VNS)屬于單點元啟發(fā)式算法[15]，VNS的創(chuàng)新之處主要包括動態(tài)變化的鄰域結(jié)構(gòu)和局部搜索，通過在搜索過程中系統(tǒng)地改變鄰域結(jié)構(gòu)集以拓展搜索范圍，達(dá)到局部最優(yōu)解不斷地向全局最優(yōu)解收斂的目的[15]，該算法所具有的靈活性決定其可根據(jù)實際問題設(shè)計各種變形，并結(jié)合其他算法使用，以提高搜索性能[17-18]。Xiao Yiyong等[17]將變鄰域搜索算法與模擬退火算法結(jié)合，模擬退火算法(Simulated Annealing, SA)是解NP難組合優(yōu)化問題的有效近似算法，該算法能夠克服傳統(tǒng)優(yōu)化算法易陷入局部極值的缺點[20-21]。嵌入模擬退火思想的變鄰域搜索算法既秉承了變鄰域搜索算法進(jìn)行大范圍變鄰域搜索的優(yōu)點，又利用模擬退火思想避免算法陷入局部最優(yōu)，兩者的結(jié)合可以有效提高算法的搜索效率和解的質(zhì)量[17-19]。

基于上述分析，本階段借鑒Hansen和Mladenovic[16]中基本變鄰域搜索算法(basic Variable Neighborhood Search, bVNS)的算法框架和Xiao Yiyong等[17]將模擬退火思想嵌入變鄰域搜索算法的設(shè)計思路，提出了混合變鄰域搜索算法(Hybrid variable neighborhood search, HVNS)，對得到的初始批次排程做進(jìn)一步優(yōu)化。在HVNS中，我們根據(jù)本文問題特征和應(yīng)用背景設(shè)計了一種解的接受準(zhǔn)則，并確定了搜索算子。算法的詳細(xì)設(shè)計及步驟如下。

3.2.1 算法初始化

算法初始化是對以下3類信息進(jìn)行明確的過程：①根據(jù)問題特征和模擬退火思想設(shè)置算法運行所需的參數(shù)；②確定初始軋制批次集合{L1,L2…Ln}及其對應(yīng)的初始解SEQ0；③將模型中的F2和F3設(shè)定為軋批排序的優(yōu)化目標(biāo)，并計算初始解的目標(biāo)函數(shù)值。

3.2.2 鄰域結(jié)構(gòu)

構(gòu)造鄰域結(jié)構(gòu)是變鄰域搜索算法的核心內(nèi)容，通過變換鄰域結(jié)構(gòu)以對更廣闊的空間進(jìn)行搜索。考慮到本文的解為一個置換序列，算法采用交換(Swap)算子和插入(Insertion)算子構(gòu)造鄰域結(jié)構(gòu)集合，Swap算子是從當(dāng)前解中隨機選取兩個相異節(jié)點，交換兩點位置形成新的鄰域結(jié)構(gòu)，將所有可能鄰域結(jié)構(gòu)組成的集合稱為當(dāng)前鄰域的交換式鄰域。Insertion算子是從當(dāng)前解中隨機選擇一個節(jié)點，并將其插入其他位置形成新的解，把所有可能形成的新解構(gòu)成當(dāng)前解關(guān)于該節(jié)點的插入式鄰域。已有研究已證明了上述兩種算子對于生成置換序列鄰域的有效性[14, 18]。

3.2.3 局部搜索

局部搜索是對每次生成的鄰域結(jié)構(gòu)進(jìn)行局部搜索，得到該鄰域結(jié)構(gòu)中的局部最優(yōu)解，通過解的接受準(zhǔn)則決定是否使用當(dāng)前解更新局部最優(yōu)解。局部搜索既是鄰域搜索的重要組成部分，也是最消耗計算資源的部分，必須針對問題特點制定搜索策略。本文采用or-opt算子進(jìn)行局部搜索，將當(dāng)前解中順序相連的部分節(jié)點移動到解路徑上的另一個位置上，得到新的局部解。

3.2.4 解的接受準(zhǔn)則

解的接受準(zhǔn)則主要包括局部最優(yōu)解更新和全局最優(yōu)解更新這兩個方面。

針對多目標(biāo)問題中局部最優(yōu)解的更新問題，本文采用在多目標(biāo)串行優(yōu)化中嵌入模擬退火算法解的接受準(zhǔn)則的決策方式。針對當(dāng)前鋼鐵企業(yè)的普遍情況，本文為生產(chǎn)因素賦以比交貨因素更高的影響因子，遵循以下規(guī)則進(jìn)行更新：

規(guī)則1：若目標(biāo)函數(shù)F2的值得到優(yōu)化，或F3相同且F2的值得到優(yōu)化，即可更新局部最優(yōu)解。

規(guī)則2：若F2得到優(yōu)化但F3值變差，則執(zhí)行模擬退火算法中解的接受準(zhǔn)則決定是否更新，接受準(zhǔn)則見式(20)，其中r0為位于0-1區(qū)間的隨機數(shù)。

(20)

規(guī)則3：其他情況均保留原解。

關(guān)于全局最優(yōu)解的接受與更新，考慮到生產(chǎn)因素的重要性，當(dāng)局部最優(yōu)解的F3不小于當(dāng)前值且局部最優(yōu)解的F2小于當(dāng)前值時，可以更新全局最優(yōu)解。

3.2.5 終止條件

基于模擬退火的思想，在當(dāng)前溫度小于終止溫度時，終止搜索并輸出計算結(jié)果。

3.2.6 算法步驟

步驟1算法初始化

步驟1.1從數(shù)據(jù)庫獲取初始軋制批次集合{L1,L2…Ln}，其軋制序列既是初始解SEQ0；

步驟1.2設(shè)定局部最大搜索次數(shù)MaxSearch、當(dāng)前搜索次數(shù)k=0，模擬退火中的初始溫度T0、終止溫度Tf、降溫系數(shù)α、降溫迭代次數(shù)nT、降溫函數(shù)Tk+1=αTk；

步驟1.3令全局最優(yōu)解為SEQb←SEQ0，對應(yīng)的全局最優(yōu)目標(biāo)函數(shù)值為FB2(SEQb)和FB3(SEQb)；

步驟2鄰域構(gòu)造

步驟2.1采用插入算子(Insertion)或交換算子(Swap)構(gòu)造關(guān)于當(dāng)前軋制批次集合的鄰域結(jié)構(gòu)集合NBK(K=1,2)，kmax=2，K=1；

步驟2.2令k←k+1、nT=0、當(dāng)前溫度為Tk=αTk-1，隨機從NBK中生成解SEQNBK，令當(dāng)前局部最優(yōu)解SEQ←SEQNBK，計算目標(biāo)函數(shù)值F2(SEQ)和F3(SEQ)；

步驟3局部搜索

步驟3.1令nT←nT+1，針對SEQNBK執(zhí)行or-opt的局部搜索操作，得到當(dāng)前局部解SEQt；

步驟3.2計算當(dāng)前局部解SEQt的目標(biāo)函數(shù)值F2(SEQt)和F3(SEQt)；

步驟3.3若F2(SEQt)

步驟3.4生成隨機數(shù)r0∈[0,1]，若滿足模擬退火接受準(zhǔn)則(式(20))則令SEQ←SEQt更新局部最優(yōu)解，轉(zhuǎn)到步驟3.5；

步驟3.5若nT=MaxSearch終止局部搜索，否則重新執(zhí)行步驟3.1；

步驟4更新歷史解

若F2(SEQ)

步驟5判斷終止條件

步驟5.1若Tk

步驟5.2排程尋優(yōu)停止，全局最優(yōu)解SEQb作為最終解，并輸出以全局最優(yōu)解排列的最終訂單排程結(jié)果{L1,L2…Ln}。

4 數(shù)據(jù)實驗與分析

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

為檢驗?zāi)Ｐ秃退惴ㄔ诂F(xiàn)實生產(chǎn)中的可行性和有效性，本文采用某典型國有大型鋼廠的實際訂單數(shù)據(jù)進(jìn)行實驗設(shè)計，共采集8組由300個訂單的整數(shù)倍組成的樣本。此樣本數(shù)據(jù)的工藝和交貨相關(guān)參數(shù)均采用行業(yè)通用標(biāo)準(zhǔn)，訂單規(guī)模覆蓋了大中小型熱軋無縫鋼廠可能的產(chǎn)能范圍，適用于國內(nèi)各鋼鐵企業(yè)。訂單按模型參數(shù)要求進(jìn)行整理后輸入模型中。

訂單樣本包含的屬性有：訂單編號、軋制外徑、軋制鋼種、軋制壁厚、軋制長度、計劃軋制支數(shù)、計劃軋制時長、交貨期窗口時間和配送地址坐標(biāo)。根據(jù)該鋼廠現(xiàn)實生產(chǎn)狀況，將模型中目標(biāo)函數(shù)懲罰值Pd、Psg、Pte、Ptl分別設(shè)置為0.6、0.4、0.2、0.8，zmax=2000，et=15min。關(guān)于對比算法的設(shè)計，考慮到本文研究問題的獨特性和復(fù)雜性，以及無縫鋼管生產(chǎn)工藝約束限制，已有算法不能直接應(yīng)用到本文問題。因此，本文將實驗分為兩階段，并分別設(shè)置如下對比算法：在第一階段實驗中，將訂單分組算法(Order grouping algorithm, OGA)和本文提出的OCA進(jìn)行對比，生成初始排程，通過目標(biāo)函數(shù)F1和F4衡量二者所生產(chǎn)初始排程的優(yōu)劣。OGA是一種不考慮交貨因素的分組算法，參考了文獻(xiàn)[1～3]中針對工藝屬性相同性進(jìn)行組批的傳統(tǒng)方法，并針對本文訂單排程模型的約束進(jìn)行了分組設(shè)定。第二階段實驗在由OGA和OCA分別生成的初始排程基礎(chǔ)上，對比bVNS和本文設(shè)計的HVNS的排程尋優(yōu)性能，其中bVNS不使用模擬退火思想控制計算的總迭代和解的接受準(zhǔn)則?？紤]到初始排程方法和排程優(yōu)化方法的優(yōu)化重點不同，第一階段實驗的衡量指標(biāo)為F1-F4這4個目標(biāo)函數(shù)；第二階段實驗則重點考察目標(biāo)函數(shù)F2和F3；另外，兩組實驗都將給出計算時間，以衡量算法的效率。

上述算法均使用Visual C#編寫，編譯于Microsoft .Net Framework 3.5軟件環(huán)境下，并運行在Intel i7-3840QM 3.8GHZ CPU/16.00GB的硬件環(huán)境下。

4.2 實驗結(jié)果與分析

表4-1和表4-2給出了兩階段實驗的結(jié)果。其中，F(xiàn)1、F2、F3、F4分別表示模型的四個目標(biāo)函數(shù)值，CPU Time表示算法的計算時間。

表4-1 訂單初始排程實驗結(jié)果

由表4-1可以看出，對于初始排程生成算法，在每種訂單規(guī)模下，OCA得到的初始排程結(jié)果(F1、F4)都優(yōu)于OGA，且相對優(yōu)勢為4%～13%。面對實驗中八組不同規(guī)模的訂單樣本，兩種算法的耗時均在1.25s以內(nèi)。這說明兩種算法都能將訂單有效組織成軋批，而OCA通過訂單間的相對距離計算體現(xiàn)訂單分布的聚類中心，再根據(jù)聚類中心進(jìn)行訂單聚集，這種思想能夠有效將交貨地址和交貨時間相近的訂單聚合成軋批集中生產(chǎn)，因此其F1和F4的目標(biāo)值明顯優(yōu)于OGA。在實現(xiàn)兩種算法時應(yīng)用了.Net成熟的分組函數(shù)，這使得計算耗時較少，而OCA比OGA消耗更多時間，主要是因為OCA需要根據(jù)式(18)和(19)不斷計算訂單間差異并生成聚類中心，這是項耗時的工作。

表4-2 訂單優(yōu)化排程實驗結(jié)果

由表4-2可以得到，對于排程優(yōu)化算法，在每種訂單規(guī)模下，經(jīng)過排程優(yōu)化后得到的F2和F3都要比初始排程后的結(jié)果有所改善。這是因為初始排程階段重點解決訂單組批問題，其形成的訂單排程結(jié)果能夠滿足工藝屬性相同性和交貨屬性相似性要求，但軋批間的排序需要進(jìn)一步優(yōu)化。由HVNS得到的排程結(jié)果優(yōu)于bVNS，這是因為HVNS在局部搜索中引入了模擬退火算法的思想，通過容忍一定概率的劣解防止搜索陷入局部最優(yōu)，搜索域相對更寬闊。而bVNS僅通過隨機的鄰域變化尋找最優(yōu)解(F2、F3)，容易陷入局部最優(yōu)，影響全局優(yōu)化效果。

此外，基于OCA的初始排程尋優(yōu)得到的最終結(jié)果要優(yōu)于OGA，主要原因如下：首先，在基于OGA的初始排程中，同批次的訂單在交貨屬性(特別是交貨期)上具有較大差距，而OCA則通過聚類保證了同批次訂單交貨期和交貨地址的相似性。其次，生產(chǎn)訂單是由銷售合同分解的，部分面向大工程的合同對某些規(guī)格有集中需求，且部分地域的客戶在規(guī)格需求上也往往具有一定相似性，這使得相似訂單在初始階段被聚類在同個或相鄰批次中，這為后續(xù)排程優(yōu)化也打下良好基礎(chǔ)。同時進(jìn)一步驗證了OCA算法的有效性。

從表4-2給出的計算時間來看，HVNS的計算時間比bVNS要長。這主要是由于HVNS算法引入模擬退火思想，HVNS的運算規(guī)模大于bVNS，當(dāng)訂單規(guī)模增加，其搜索范圍和計算量將相應(yīng)增加。但本實驗的最大訂單規(guī)模達(dá)到2400，相當(dāng)于一般大型鋼廠的中長期訂單排程需求，在此規(guī)模上HVNS于6min內(nèi)獲得了排程結(jié)果，完全能夠滿足實際的計劃需求。而由此能夠取得F2相較于bVNS的30%到45%的優(yōu)化，同時F3也能得到1%到6%的優(yōu)化，降低了由機器調(diào)整和提前/拖期生產(chǎn)造成的成本。因此，對于HVNS而言，其在計算時間與優(yōu)化效果上的平衡是值得的。

綜上所述，實驗通過八組不同訂單規(guī)模的樣本，測試了模型及OCA和HVNS在訂單排程中的可行性和有效性，該組合算法在合理的時間范圍內(nèi)可以得到相對更優(yōu)的排程結(jié)果。

5 結(jié)語

熱軋訂單排程是無縫鋼管生產(chǎn)管理中的重要問題，目前大多數(shù)研究主要基于產(chǎn)品規(guī)格，很少涉及訂單交貨和配送等因素。本文在充分考慮了無縫鋼管的生產(chǎn)工藝要求和產(chǎn)品特點的基礎(chǔ)上，綜合考慮訂單交貨期和交貨地址，以訂單適期交貨、集中生產(chǎn)和配送、機器設(shè)備調(diào)整頻率最小為目標(biāo)設(shè)計了問題的混合整數(shù)規(guī)劃模型。在模型的求解方面，本文基于過往研究并結(jié)合冶金行業(yè)的生產(chǎn)特征和本文研究問題的特點，首先基于帶凝聚策略的層次聚類算法思想，按工藝屬性相同和交貨屬性相似的要求，定義了訂單間的距離公式，設(shè)計了一種訂單聚類算法進(jìn)行訂單組批并形成初始軋制計劃。然后通過構(gòu)造符合本文問題特征的解的接受準(zhǔn)則和搜索算子，設(shè)計了混合變鄰域搜索算法對初始批次進(jìn)行排程優(yōu)化?；趯嶋H訂單數(shù)據(jù)的仿真實驗驗證了模型和算法的可行性和有效性。實驗結(jié)果表明，該模型在滿足熱軋無縫鋼管生產(chǎn)特點的同時，優(yōu)化了合同對于交貨與配送的需求，且本文提出的算法能夠在各訂單規(guī)模上得到相對優(yōu)化的訂單排程結(jié)果，能夠?qū)彳垷o縫鋼管的生產(chǎn)管理起到指導(dǎo)作用。

參考文獻(xiàn)：

[1] 王海鳳,薛美美,李鐵克.基于約束滿足的熱軋無縫鋼管生產(chǎn)排序模型與算法[J].冶金自動化,2013,37(3):39-42.

[2] Tang Lixin, Huang Lin. Optimal and near-optimal algorithms to rolling batch scheduling for seamless steel tube production[J]. International Journal of Production Economics,2007,105(2):357-371.

[3] 李建祥,唐立新,吳會江,等.基于規(guī)則的熱軋鋼管調(diào)度[J].鋼鐵,2004,39(9):39-42.

[4] Li Lin, Huo Jiazhen, Tang Ou. A hybrid flowshop scheduling problem for a cold treating process in seamless steel tube production[J].International Journal of Production Research, 2011, 49(15):4679-4700.

[5] Jia Shujin,Yi Jian,Yang Genke,et al. A multi-objective optimisation algorithm for the hot rolling batch scheduling problem[J].International Journal of Production Research,2013,51(3):667-681.

[6] 許紹云,李鐵克,王雷,等.考慮機器檢修的圓鋼熱軋批量調(diào)度算法[J].計算機集成制造系統(tǒng), 2014, 20(10): 2502-2511.

[7] Jia Shujin, Zhu Jun, Yang Genke,et al. A decomposition-based hierarchical optimization algorithm for hot rolling batch scheduling problem [J]. The International Journal of Advanced Manufacturing Technology, 2012, 61(5): 487-501.

[8] 張文學(xué),李鐵克.面向多種生產(chǎn)工藝的冶鑄軋一體化批量計劃優(yōu)化[J].計算機集成制造系統(tǒng),2013,19(6):1296-1303.

[9] 薛羽.仿生智能優(yōu)化算法及其應(yīng)用研究[D].南京： 南京航空航天大學(xué),2013.

[10] Pan Changchun, Yang Genke. A method of solving a large-scale rolling batch scheduling problem in steel production using a variant of column generation[J]. Computers & Industrial Engineering, 2009, 56(1):165-178..

[11] Everitt B, Landau S, Leese M, et al. Cluster analysis, Wiley series in probabilityand statistics[M]. Chichester, UK: Wiley; 2011.

[12] Daie P, Li S. Hierarchical clustering for structuring supply chain network in case of product variety[J]. Journal of Manufacturing Systems, 2016, 38:77-86.

[13] 段明秀.層次聚類算法的研究及應(yīng)用[D].長沙：中南大學(xué),2009.

[14] Arroyo J E C, Rafael D S O, Alcione D P O. Multi-objective variable neighborhood search algorithms for a single machine scheduling problem with distinct due windows[J]. Electronic Notes in Theoretical Computer Science, 2011, 281(1):5-19.

[15] Mladenovic N, Hansen P. Variable neighborhood search[J]. Computers & Operations Research, 1997, 24(11):1097-1100.

[16] Hansen P, Mladenovic N. Variable neighborhood search:Principles and applications[J]. European Journal of Operational Research, 2001, 130(3):449-467.

[17] Xiao Yiyong, Zhao Qiuhong, Kaku I, et al.Variable neighbourhood simulated annealing algorithm for capacitated vehicle routing problems[J].Engineering Optimization, 2014, 46(4):562-579.

[18] 柏亮,李鐵克,王柏琳,等.基于變鄰域搜索的熱軋圓鋼批量調(diào)度多目標(biāo)優(yōu)化方法[J].工程科學(xué)學(xué)報,2015,37(1):111-117.

[19] 王雷,許紹云,趙揚,等.有限緩沖區(qū)的多節(jié)點訂單接受模型與算法[J].中國管理科學(xué),2015,23(12):135-141.

[20] Yu V F, Lin S Y. A simulated annealing heuristic for the open location-routing problem[J]. Computers and Operations Research, 2015,62:184-196.

[21] Bandyopadhyay S, Saha S, Maulik U, et al. A Simulated annealing-based multiobjective optimization algorithm:AMOSA[J]. IEEE transactions on evolutionary computation, 2008, 12(3):269-283.