考慮交貨因素的熱軋無縫鋼管訂單排程模型與算法

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

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

1 引言

無縫鋼管作為一種重要的工業(yè)生產(chǎn)資料，廣泛用于國(guó)民經(jīng)濟(jì)的各個(gè)生產(chǎn)領(lǐng)域，企業(yè)通常按照外徑、壁厚、鋼種、長(zhǎng)度等參數(shù)將鋼管劃分成不同的規(guī)格，將滿足一定條件的訂單按規(guī)格統(tǒng)一組織，實(shí)現(xiàn)批量化生產(chǎn)。一套完整的現(xiàn)代熱軋無縫鋼管生產(chǎn)要經(jīng)過鋼坯加熱、穿孔、連軋、張減定徑和精整、熱處理等多道工序，跨越數(shù)個(gè)作業(yè)區(qū)。其中連軋工序是無縫鋼管生產(chǎn)的重中之重。熱軋軋制訂單計(jì)劃決定了整條產(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)具有以下四個(gè)特點(diǎn)：批量可調(diào)度性、生產(chǎn)多階段性、品種規(guī)格的多樣性且機(jī)器調(diào)整時(shí)間因批量規(guī)格而異；李建祥等[3]總結(jié)出7條關(guān)于鋼管組批和排序的規(guī)則，對(duì)鋼管的生產(chǎn)計(jì)劃和調(diào)度的研究具有借鑒意義；Li Lin等[4]研究了寶山無縫鋼管廠冷區(qū)生產(chǎn)調(diào)度問題，針對(duì)現(xiàn)實(shí)生產(chǎn)約束提出了混合流水車間調(diào)度問題的混合整數(shù)非線性規(guī)劃模型；Jia Shujin等[5]將熱軋批量調(diào)度問題歸結(jié)為基于獎(jiǎng)金收集車輛路徑問題并提出多目標(biāo)優(yōu)化模型；許紹云等[6]以最大化產(chǎn)能利用率、最小化機(jī)器調(diào)整時(shí)間和訂單提前拖期為優(yōu)化目標(biāo)，建立針對(duì)圓鋼熱軋批量調(diào)度問題的多目標(biāo)整數(shù)規(guī)劃模型；Jia Shujin等[7]將熱軋批量調(diào)度問題歸結(jié)為一個(gè)帶雙時(shí)間窗的車輛路徑問題的多目標(biāo)模型。熱軋訂單排程問題屬于NP難的組合優(yōu)化問題，目前多采用智能優(yōu)化算法和聚類算法相結(jié)合的方式求解。其中，王海鳳等[1]設(shè)計(jì)了節(jié)點(diǎn)互換算法解決無縫鋼管生產(chǎn)計(jì)劃中的生產(chǎn)排序問題；Jia Shujin等[5]使用基于分解策略和帕累托最優(yōu)的蟻群算法對(duì)模型進(jìn)行求解；許紹云等[6]提出一種改進(jìn)的帶精英策略的快速非支配排序算法對(duì)批量調(diào)度模型進(jìn)行求解；張文學(xué)和李鐵克[8]針對(duì)面向復(fù)雜生產(chǎn)工藝的三階段一體化批量計(jì)劃模型(無優(yōu)化目標(biāo))，考慮到問題的NP難特點(diǎn)，提出了將約束傳播技術(shù)嵌入到聚類分析中的求解算法。

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

2 問題建模

2.1 問題描述

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

2.2 模型假設(shè)

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

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

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

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

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

2.3 符號(hào)定義

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

(1)索引與集合

I為所有計(jì)劃軋制批編號(hào)的集合，I={1,2,…,n}；i為軋制批次編號(hào)，i∈I；

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

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

(2)符號(hào)定義

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

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

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

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

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

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

ptj為為訂單j的計(jì)劃軋制時(shí)長(zhǎng)；

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

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

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

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

(3)決策變量

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

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

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

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

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

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

3 求解算法

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

3.1 初始排程

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

3.1.1 訂單預(yù)處理

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

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

此外，若在訂單組批階段就考慮交貨期相似性，能夠?yàn)榕判騼?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ì)訂單間距離公式的重要依據(jù)。

(17)

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

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

(18)

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

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

3.2.1 算法初始化

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

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

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

3.2.3 局部搜索

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

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

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

針對(duì)多目標(biāo)問題中局部最優(yōu)解的更新問題，本文采用在多目標(biāo)串行優(yōu)化中嵌入模擬退火算法解的接受準(zhǔn)則的決策方式。針對(duì)當(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ū)間的隨機(jī)數(shù)。

(20)

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

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

3.2.5 終止條件

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

3.2.6 算法步驟

步驟1算法初始化

步驟1.1從數(shù)據(jù)庫(kù)獲取初始軋制批次集合{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，對(duì)應(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，隨機(jī)從NBK中生成解SEQNBK，令當(dāng)前局部最優(yōu)解SEQ←SEQNBK，計(jì)算目標(biāo)函數(shù)值F2(SEQ)和F3(SEQ)；

步驟3局部搜索

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

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

步驟3.3若F2(SEQt)

步驟3.4生成隨機(jī)數(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ù)實(shí)驗(yàn)與分析

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

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

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

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

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

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

表4-1 訂單初始排程實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

5 結(jié)語

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

參考文獻(xiàn)：

[1] 王海鳳,薛美美,李鐵克.基于約束滿足的熱軋無縫鋼管生產(chǎn)排序模型與算法[J].冶金自動(dòng)化,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] 李建祥,唐立新,吳會(huì)江,等.基于規(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] 許紹云,李鐵克,王雷,等.考慮機(jī)器檢修的圓鋼熱軋批量調(diào)度算法[J].計(jì)算機(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)工藝的冶鑄軋一體化批量計(jì)劃優(yōu)化[J].計(jì)算機(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].長(zhǎng)沙：中南大學(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é)報(bào),2015,37(1):111-117.

[19] 王雷,許紹云,趙揚(yáng),等.有限緩沖區(qū)的多節(jié)點(diǎn)訂單接受模型與算法[J].中國(guó)管理科學(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.