李 稷，徐安軍

(北京科技大學(xué) 冶金與生態(tài)工程學(xué)院，北京 100083)

天車是煉鋼車間鋼包在各個工序間周轉(zhuǎn)的主要運輸工具.天車調(diào)度須服務(wù)于工序調(diào)度，良好的天車調(diào)度是工序調(diào)度穩(wěn)定進行的有力保證.同時，天車調(diào)度受制于工序調(diào)度且天車調(diào)度具有更高的時間精度要求，生產(chǎn)工序上分鐘級別的擾動可能造成天車調(diào)度結(jié)果的改變.目前煉鋼車間中，頻繁的動態(tài)調(diào)度是天車調(diào)度的必然選擇.

圖1給出了某鋼廠鋼水精煉跨天車調(diào)度環(huán)境的平面圖.鋼包的物流過程可由圖中步驟①～④描述：鋼包從轉(zhuǎn)爐(工序1)盛接鋼水，鋼包車將鋼包從轉(zhuǎn)爐位運輸至吊包位(步驟①)；天車將鋼包從吊包位吊起，運輸至某精煉(工序2)工位對應(yīng)的落包位，并將鋼包放置于對應(yīng)的鋼包車上(步驟②)；鋼包車將鋼包運輸至精煉位處理(步驟③)；處理結(jié)束后運輸至下一跨(步驟④).天車的運輸任務(wù)(步驟②)即是將鋼包從一個工序運輸至下一工序.另外，由于雙精煉工藝的存在(鋼水需要在兩個精煉工位處理)，鋼包還可能從某精煉工位運輸至另一精煉工位.

安裝在同一軌道(X軸)的天車相互之間不能跨越且必須保持安全距離，稱之為避碰約束，這是天車調(diào)度區(qū)別于其他機器調(diào)度的基本特征約束.同時，工位容量約束要求一個工位最多容納一個鋼包.最后，頻繁的天車重調(diào)度必然面臨不同的調(diào)度初始條件(不同的天車、任務(wù)、工位的初始狀態(tài))，從而對天車調(diào)度形成約束.

由于天車調(diào)度環(huán)境物理布局以及天車運行方式的不同，天車調(diào)度問題有不同的解決方案.目前國內(nèi)外對天車調(diào)度的研究主要集中于集裝箱港口岸橋和場堆龍門吊的調(diào)度.文獻(xiàn)[1-2]對近年來該問題的研究進行了整體分析.岸橋在執(zhí)行任務(wù)時，主體靜止在任務(wù)X軸對應(yīng)位置，沿著Y軸方向裝卸貨物.本文稱這類天車為Y軸作業(yè)天車.Y軸作業(yè)天車將任務(wù)定義為在貨物位置對貨物的操作.受其影響，許多需要沿X軸將物品從A處運輸?shù)紹處的天車調(diào)度問題，定義了同樣的任務(wù)內(nèi)涵，即將物品吊起和落下的操作分別定義為一個任務(wù).這種任務(wù)定義方式能公式化推導(dǎo)避碰約束下任務(wù)的開始、結(jié)束時刻，適用于非仿真方法.但該定義增加了額外的求解約束，如吊起任務(wù)和落下任務(wù)需要同一輛天車連續(xù)執(zhí)行.在該類任務(wù)定義下，Peterson等[3]對某制造車間多天車調(diào)度問題建模，設(shè)計了天車最優(yōu)路徑方案，并利用啟發(fā)式算法快速求得近優(yōu)解.Cheng等[4]對某倉庫兩天車調(diào)度問題建立了MIP模型，并用分支裁剪法求解.X軸作業(yè)天車任務(wù)的第二種定義將物品從A點到B點的整個運輸過程作為一個任務(wù).這種定義方式符合常規(guī)認(rèn)知且能夠利用簡單的啟發(fā)式規(guī)則快速求得近優(yōu)解，但在避碰約束下推導(dǎo)任務(wù)開始時刻較為困難，一般采用仿真手段.王旭等[5]、高小強等[6]研究了制造車間天車調(diào)度問題.兩者都設(shè)計了啟發(fā)式天車分配和沖突消解規(guī)則，并利用仿真手段和改進的遺傳算法進行求解；在時間目標(biāo)函數(shù)方面，分別或共同考慮了最小化等待被運輸時間，最小化天車對任務(wù)的響應(yīng)時間和最短完工時間.Xie等[7]對一個鋼卷熱處理工序的多天車調(diào)度問題建立了MIP模型并用一種啟發(fā)式算法求解.求解過程中，為避免起重機的干擾，規(guī)定了天車的行為規(guī)范.實驗結(jié)果表明提出的啟發(fā)式方法可以生成高質(zhì)量的解.Hirsch等[8]設(shè)計了某制造車間兩天車的運行方案，并利用蟻群算法求解了該調(diào)度問題.周炳海等[9]提出一種全新的天車軌跡映射模型，結(jié)合傳統(tǒng)差分進化方法，將庫位分配規(guī)則和天車分配算法融合到調(diào)度算法的每一次迭代過程中以指導(dǎo)算法尋優(yōu).在自動化存儲倉庫的天車調(diào)度問題中，Kung等[10]設(shè)計了一種啟發(fā)式的天車運行方案以解決天車避碰，并提出一種基于動態(tài)規(guī)劃的訂單調(diào)度方法.李維剛等[11]同樣設(shè)計了任務(wù)分配規(guī)則，并采用改進的A*算法計算天車路徑，調(diào)度方案具有可靠性和高效性.

以上針對車間或倉庫的天車調(diào)度研究，多以靜態(tài)調(diào)度為主.其調(diào)度初始條件人為假設(shè)，無法解決動態(tài)條件下面臨的任務(wù)、天車、工位各種初始狀態(tài)對調(diào)度的影響；而動態(tài)調(diào)度的研究多采用實時調(diào)度策略，即每當(dāng)一個任務(wù)到達(dá)時，根據(jù)任務(wù)分配規(guī)則將任務(wù)分配給某臺天車.該策略具有較為嚴(yán)重的調(diào)度短視性.同時，以上車間天車調(diào)度研究忽略了工位容量，有可能產(chǎn)生不可行解.針對以上情況，本文利用滾動調(diào)度策略對煉鋼車間天車調(diào)度問題進行了仿真研究.滾動調(diào)度實時對未來一小段時間內(nèi)的任務(wù)進行預(yù)測，采用優(yōu)化算法進行調(diào)度求解.又可以隨著新任務(wù)的到來，不斷進行重調(diào)度，進行快速響應(yīng).

本文首先針對任一重調(diào)度過程進行了建模.模型目標(biāo)函數(shù)考慮了天車調(diào)度在時間節(jié)奏上需服從工序調(diào)度，同時考慮最小化天車工作量及其差異.約束條件在遵守天車避碰約束的同時，還考慮了工位容量約束和重調(diào)度初始條件對天車調(diào)度的約束.隨后，提出了一種基于仿真的啟發(fā)式方法對模型進行了求解，對圖1所示雙天車調(diào)度進行了實例分析.

1 問題建模

1.1 問題描述

本文研究的多天車動態(tài)調(diào)度問題(簡稱DMCSP)中，天車的運輸任務(wù)定義為將一個鋼包從起點工位運輸至終點工位.其包括3個過程：在起點工位吊起鋼包；將鋼包運輸至終點工位；將鋼包放置于終點工位.由于每次重調(diào)度中任務(wù)數(shù)量不多且天車數(shù)量有限，故重調(diào)度方式采用完全重調(diào)度，即對所有未完成任務(wù)和新到的任務(wù)重新分配天車.

圖1 天車調(diào)度跨布局

假設(shè)某次重調(diào)度過程中任務(wù)數(shù)量為N.工位數(shù)量為M，工位首先以工序號排序，工序內(nèi)工位從左向右排序.故圖1中工位1～4為轉(zhuǎn)爐工位，5～11為精煉工位；工位在X軸上的位置已在圖1中標(biāo)識.天車數(shù)量為K，天車從左向右排序.DMCSP中僅考慮天車沿X軸的移動(沿Y軸的移動忽略，沿高度方向的移動以固定的起吊時間和落包時間代替)，且移動速度固定.天車避讓時的優(yōu)先級與其當(dāng)前任務(wù)在任務(wù)排序序列中的序列號一致；任務(wù)序列號越小，天車優(yōu)先級越高.

DMCSP的每次重調(diào)度可描述為：對于N個任務(wù)，K臺天車，在遵從天車移動行為約束、工位容量約束、初始條件約束的前提下，確定一個任務(wù)排序序列以及對應(yīng)的天車分配序列作為問題解，以最小化完成N個任務(wù)時的時間懲罰值以及對天車工作量增加和差異的懲罰值.

DMCSP模型涉及的數(shù)學(xué)符號如下.

t，仿真系統(tǒng)時間,t=0，1，2，…;

t0，當(dāng)前重調(diào)度時刻;

N，任務(wù)數(shù)量;

K，天車數(shù)量;

M，工位數(shù)量;

δ，天車安全距離，天車中線之間的距離，δ=26 m;

Δk,l，任意兩天車之間的最小的安全距離，k，l=1，2，…，K，k≠l;Δk,l=|k-l|δ;

v，天車移動速率，v=2/3 m/s;

Om，t0時刻工位m中的鋼包數(shù)量，m=1，2，…，M；Om=0，1;

Lm，工位m在X軸的位置，m=1，2，…，M;

ai，bi，任務(wù)i的起點、終點工位索引號，i=1，2，…，N，ai，bi=1，2，…，M;

ri，任務(wù)i的釋放時刻(到達(dá)吊包位的時刻)，i=1，2…N;

si，ei，任務(wù)i的開始、結(jié)束時刻，i=1，2，…，N；如果任務(wù)i重調(diào)度時未開始，si，ei=0;

αi，βi，任務(wù)i中鋼包起吊、落下所需時間，αi=180 s，βi=240 s;

Ci，任務(wù)i所分配天車的索引號，i=1，2，…，N，Ci=1，2，…，K;

Ri，任務(wù)i在任務(wù)序列中的排序序號 (相當(dāng)于任務(wù)i的優(yōu)先級序號)，i=1，2，…，N;

Rk,i，在所有分配給天車k的任務(wù)中，任務(wù)i的排序序號，i=1，2，…，N；k=1，2，…，K;

Pk,t，天車k在t時刻的位置，k=1，2,…,K；t=1，2,…; 天車初始位置Pk,0=(k-1)δ;

Z，多目標(biāo)函數(shù).

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

(1)

根據(jù)多次仿真實驗，參數(shù)a賦值1.002.

第一個目標(biāo)函數(shù)表述為

(2)

另外，目標(biāo)函數(shù)還考慮了天車的工作量增量和不同天車歷史總工作量之間的差異.天車歷史總工作量，記為Wk，主要體現(xiàn)在其吊包、落包次數(shù)和負(fù)載、空載移動距離.本文將Wk量化為時間值：

(3)

其中：Wk,t0是重調(diào)度開始時天車k的工作量；Dk,1，Dk,2是當(dāng)N個任務(wù)完成時，天車k空載、負(fù)載移動距離；λ1(設(shè)λ1=0.4)為權(quán)重系數(shù).

目標(biāo)函數(shù)Z2表述為

(4)

其中λ2(設(shè)λ2=0.3)為權(quán)重系數(shù).

最終，多目標(biāo)函數(shù)表述為

Z=Z1+Z2.

(5)

綜上，本文的DMCSP數(shù)學(xué)模型可表述為

minZ.

(6)

服從于約束(7)～(13)：

(7)

(8)

Ri

(9)

Pk,t-v≤Pk,t+1≤Pk, t+v,
?k=1,2,…,K; ?t=1,2,…

(10)

Pk-1,t≤Pk,t-δ?k=2, 3,…,K;
?t=1,2,…

(11)

si+αi+|Lai-Lbi|/v+βi+Δ1=ei,
?i=1,2,…,N.

(12)

(13)

約束(7)～(9)由重調(diào)度時的不同初始條件產(chǎn)生.初始約束(7)和約束(8)要求若重調(diào)度時某任務(wù)正在被某天車執(zhí)行，那么該任務(wù)仍分配給該天車，且必須作為該天車的第一個任務(wù)，否則不符合現(xiàn)實.約束(9)是工位容量約束，即若任務(wù)i的起點是任務(wù)j的終點，且任務(wù)i起點被占據(jù)，那么，任務(wù)i必須先執(zhí)行，任務(wù)j才能執(zhí)行.

約束(10)～(13)為天車移動行為約束.約束(10)要求天車的運行軌跡必須是連續(xù)的；約束(11)是避碰約束，要求相鄰兩臺天車必須保持安全距離且不能相互跨越.約束(12)表明天車實際完成一個任務(wù)的時間，由于天車避讓等原因，必然不小于該任務(wù)的理論完成時間.約束(13)規(guī)定一臺天車在完成當(dāng)前任務(wù)后，必須到達(dá)下一任務(wù)的起點且下一任務(wù)已經(jīng)釋放后，下一任務(wù)才能開始執(zhí)行.約束(12)和約束(13)中Δ1和Δ2通過仿真獲得.

2 實驗方法

2.1 仿真過程總體方案

仿真平臺分為兩部分，如圖2所示.一部分為現(xiàn)實仿真模塊，其模擬真實天車運行環(huán)境，同時管理任務(wù)，記錄天車、任務(wù)、工位狀態(tài).另一部分為算法，當(dāng)需要調(diào)度決策時，其首先從仿真模塊獲取當(dāng)前仿真時刻天車、任務(wù)、工位的初始狀態(tài)作為初始條件.然后算法模塊生成有效解(調(diào)度方案)集合，并將每一個有效解以當(dāng)前初始條件進行仿真運行.最終選取擁有最小目標(biāo)函數(shù)值的解為最優(yōu)解.該最優(yōu)解將反饋給現(xiàn)實仿真模塊，天車根據(jù)該解繼續(xù)執(zhí)行任務(wù).如此，形成了一種滾動調(diào)度的動態(tài)調(diào)度模式.

圖2 天車調(diào)度仿真平臺運行模式

2.2 天車運行方案

天車運行方案控制仿真過程中天車的運行行為.提出的天車運行方案適用于任意數(shù)量的天車，具有較好的拓展性.其包含一個主動運行方案和一個避讓運行方案.

2.2.1 主動運行方案

天車在無干擾的情況下，完成一個任務(wù)需要經(jīng)歷5個步驟，本文稱為天車的5個狀態(tài)，如圖3所示.其中，細(xì)線表示天車處于空載狀態(tài)(Sk,t=0，1)，粗線表示天車處于負(fù)載狀態(tài)(Sk,t=2，3，4).其中，Sk,t=0表示任務(wù)i的di時刻未到達(dá)，或天車沒有任務(wù)；Sk,t=1表示天車從當(dāng)前位置移向任務(wù)i起點工位；Sk,t=2表示天車起包過程；Sk,t=3表示天車吊運鋼包至任務(wù)i終點工位；Sk,t=4表示天車落包過程.

圖3 天車的5個狀態(tài)

天車k在執(zhí)行任務(wù)i時，其狀態(tài)變更邏輯流程如圖4所示，圖中Tc為天車當(dāng)前狀態(tài)的變更時刻.圖4給出了天車狀態(tài)變更的判斷邏輯，也給出了天車位置變更的函數(shù).當(dāng)天車k處于Sk,t=1或者3時，須向當(dāng)前狀態(tài)下的目標(biāo)點(任務(wù)起點或終點)移動：

Pk,t=f(Pk,t-1，Ldest)=Pk,t-1+
sign(Ldest-Pk,t-1)v.

(14)

其中：Ldest是目標(biāo)點所在位置；sign(x)是符號函數(shù):

(15)

圖4 天車狀態(tài)變更邏輯流程

重調(diào)度時某低優(yōu)先級天車l可能處于Sl,t=2或4，當(dāng)前過程無法中斷.若此時高優(yōu)先級天車k向天車l移動，且|Pk,t-Pl,t| <Δk,l時，天車位置更新為

Pk,t=h(k，Pl,t)=Pl,t+sign(k-l)Δk,l.

(16)

另外，當(dāng)擁有高優(yōu)先級任務(wù)的天車k處于Sk,t=0時，規(guī)定其須避讓其他天車，表述為Pk,t=h(k，Pl,t).

2.2.2 避讓運行方案

低優(yōu)先級天車在執(zhí)行任務(wù)的過程中，為避讓高優(yōu)先級天車，可能需要經(jīng)過多個中間過渡點，記為Pmid.以某兩天車(低優(yōu)先級天車l和高優(yōu)先級天車k)為例，天車l在完成任務(wù)過程中最多需要經(jīng)過1個Pmid,可能的情況如圖5所示.圖5a中兩天車任務(wù)區(qū)域不重疊，天車各自按其主動運行方案移動；圖5b中天車l須在Sl,t=1階段移動到Pmid以避讓天車k; 而圖5c中天車l須在Sl,t=3階段移動到Pmid以避讓天車k.故天車l的避讓運行方案可描述為：天車l按主動運行方案移動→如果需要，在特定Sl,t下移動到Pmid→等待繼續(xù)執(zhí)行任務(wù)的條件判斷→繼續(xù)按主動運行方案完成任務(wù)剩余部分.當(dāng)有n臺天車優(yōu)先性高于天車l時，天車l最多需要經(jīng)過n個Pmid，該邏輯流程可由以上描述拓展得到.

由于Pmid的限制，低優(yōu)先級天車會提前避讓潛在沖突從而避免在現(xiàn)實中較為常見的無效折返跑.并且Pmid的限制也使得高優(yōu)先級天車在Sk,t=0時即使避讓低優(yōu)先級天車，也不會導(dǎo)致其無效折返跑而增加額外工作量，更加符合現(xiàn)實天車運行行為.

圖5 天車避讓運行方案示例

2.3 啟發(fā)式方法

每一個重調(diào)度的解包括一個任務(wù)排序序列和對應(yīng)的天車分配序列.

記I[i]表示任務(wù)序列中第i個任務(wù)的索引號.構(gòu)建任務(wù)序列的方法如下：

對于每個任務(wù)序列，其所有天車分配序列構(gòu)建如下：

1) 根據(jù)約束(7)，正在被執(zhí)行的任務(wù)將繼續(xù)分配給執(zhí)行該任務(wù)的天車；

2) 其他任務(wù)按照窮舉法分配天車.

對于以上構(gòu)造的天車分配序列，不符合下列規(guī)則的序列將被排除：

1) 連續(xù)3個任務(wù)不能分配給同一天車；

2) 如果任務(wù)區(qū)域不重疊，則天車不可交叉分配，如圖5a所示.這符合已被證明存在最優(yōu)解的單向調(diào)度策略[13]，即若max{aI[i]，bI[i]}+Δk,lCI[i+1].

3 實驗結(jié)果及分析

仿真平臺利用C#語言在Microsoft Visual Studio 2013軟件上編寫.計算機安裝Win 10系統(tǒng)，8 GB內(nèi)存，CPU型號為Intel(R) Core(TM) i3-6100 @ 3.7 GHz.

仿真實驗中天車數(shù)量根據(jù)現(xiàn)場實際設(shè)定為2臺，任務(wù)見表1.動態(tài)調(diào)度的結(jié)果展示于圖6a，其為天車在各個工位間執(zhí)行任務(wù)的軌跡.軌跡圖可以得到任務(wù)分配方案和任務(wù)開始、結(jié)束時刻.下部軌跡屬于天車1，而上部軌跡屬于天車2.兩條軌跡中，粗線部分天車處于負(fù)載狀態(tài)(Sk,t>1)而細(xì)線部分處于空載狀態(tài)(Sk,t≤1).圖中兩天車軌跡不相交，滿足避碰約束.天車到達(dá)任務(wù)起點時，大多數(shù)任務(wù)并未釋放，不會造成額外的任務(wù)延遲.表1中30個任務(wù)的調(diào)度過程計算耗時為0.22 s，每個重調(diào)度過程則更少，完全滿足實際調(diào)度的實時性要求.煉鋼車間天車任務(wù)是隨著主工序的生產(chǎn)節(jié)奏而產(chǎn)生，故不會導(dǎo)致批量任務(wù)同時釋放.在滾動調(diào)度策略下，每次重調(diào)度的任務(wù)規(guī)模不超過5個.總的任務(wù)規(guī)模增大，僅會導(dǎo)致重調(diào)度的次數(shù)和整個仿真過程耗時增加，而對每次重調(diào)度的實時性影響較小.

模型目標(biāo)函數(shù)使得本文天車調(diào)度方案具有維護生產(chǎn)調(diào)度穩(wěn)定性和平衡天車工作量的作用.例如，人為調(diào)換任務(wù)2和任務(wù)3的計劃釋放時刻以模擬任務(wù)3因某種原因?qū)е侣浜笥诠ば蛘{(diào)度計劃，此時任務(wù)3優(yōu)先級將提升而高于任務(wù)2，執(zhí)行結(jié)果如圖6b所示.又如，設(shè)置天車2在t=0時的初始工作量為50 min，則在后續(xù)調(diào)度中，任務(wù)將趨向于分配給天車2以平衡兩車的工作量，如圖6c所示.

表1 仿真實驗任務(wù)集合

表2對比了滾動調(diào)度策略與實時調(diào)度策略下的天車調(diào)度結(jié)果，滾動調(diào)度策略下分別采用了提出的啟發(fā)式方法和枚舉法進行了對比.枚舉法因能遍歷所有解，其取得的解是局部最優(yōu)解.同時，在實時調(diào)度策略下對比了提出的啟發(fā)式方法(此時相當(dāng)于一種貪婪算法)和規(guī)則調(diào)度(向左任務(wù)由左邊天車執(zhí)行，向右任務(wù)由右邊天車執(zhí)行).

圖6 天車運行軌跡

表2 性能對比實驗結(jié)果

4 結(jié) 論

1) 本文提出的煉鋼車間天車動態(tài)仿真調(diào)度方案能夠促進工序調(diào)度的穩(wěn)定，減少和均衡天車工作量.提出的啟發(fā)式算法的實時性保證了本方案的可行性，天車?yán)寐蕽M足現(xiàn)場要求.

2) 滾動調(diào)度策略下，提出的啟發(fā)式方法所得解的優(yōu)化性能最高能達(dá)到最優(yōu)解的96.3%.

3)提出的滾動調(diào)度策略下的啟發(fā)式方法相比于現(xiàn)場采用的實時規(guī)則調(diào)度方法，調(diào)度優(yōu)化性能提高26.4%.