煉鋼車間多天車動態調度仿真方案

李 稷，徐安軍

(北京科技大學 冶金與生態工程學院，北京 100083)

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

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

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

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

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

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

1 問題建模

1.1 問題描述

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

圖1 天車調度跨布局

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

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

DMCSP模型涉及的數學符號如下.

t，仿真系統時間,t=0，1，2，…;

t0，當前重調度時刻;

N，任務數量;

K，天車數量;

M，工位數量;

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

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

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

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

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

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

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

si，ei，任務i的開始、結束時刻，i=1，2，…，N；如果任務i重調度時未開始，si，ei=0;

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

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

Ri，任務i在任務序列中的排序序號 (相當于任務i的優先級序號)，i=1，2，…，N;

Rk,i，在所有分配給天車k的任務中，任務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，多目標函數.

1.2 數學模型

(1)

根據多次仿真實驗，參數a賦值1.002.

第一個目標函數表述為

(2)

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

(3)

其中：Wk,t0是重調度開始時天車k的工作量；Dk,1，Dk,2是當N個任務完成時，天車k空載、負載移動距離；λ1(設λ1=0.4)為權重系數.

目標函數Z2表述為

(4)

其中λ2(設λ2=0.3)為權重系數.

最終，多目標函數表述為

Z=Z1+Z2.

(5)

綜上，本文的DMCSP數學模型可表述為

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)由重調度時的不同初始條件產生.初始約束(7)和約束(8)要求若重調度時某任務正在被某天車執行，那么該任務仍分配給該天車，且必須作為該天車的第一個任務，否則不符合現實.約束(9)是工位容量約束，即若任務i的起點是任務j的終點，且任務i起點被占據，那么，任務i必須先執行，任務j才能執行.

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

2 實驗方法

2.1 仿真過程總體方案

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

圖2 天車調度仿真平臺運行模式

2.2 天車運行方案

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

2.2.1 主動運行方案

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

圖3 天車的5個狀態

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

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

(14)

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

(15)

圖4 天車狀態變更邏輯流程

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

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

(16)

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

2.2.2 避讓運行方案

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

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

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

2.3 啟發式方法

每一個重調度的解包括一個任務排序序列和對應的天車分配序列.

記I[i]表示任務序列中第i個任務的索引號.構建任務序列的方法如下：

對于每個任務序列，其所有天車分配序列構建如下：

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

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

對于以上構造的天車分配序列，不符合下列規則的序列將被排除：

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

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

3 實驗結果及分析

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

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

模型目標函數使得本文天車調度方案具有維護生產調度穩定性和平衡天車工作量的作用.例如，人為調換任務2和任務3的計劃釋放時刻以模擬任務3因某種原因導致落后于工序調度計劃，此時任務3優先級將提升而高于任務2，執行結果如圖6b所示.又如，設置天車2在t=0時的初始工作量為50 min，則在后續調度中，任務將趨向于分配給天車2以平衡兩車的工作量，如圖6c所示.

表1 仿真實驗任務集合

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

圖6 天車運行軌跡

表2 性能對比實驗結果

4 結 論

1) 本文提出的煉鋼車間天車動態仿真調度方案能夠促進工序調度的穩定，減少和均衡天車工作量.提出的啟發式算法的實時性保證了本方案的可行性，天車利用率滿足現場要求.

2) 滾動調度策略下，提出的啟發式方法所得解的優化性能最高能達到最優解的96.3%.

3)提出的滾動調度策略下的啟發式方法相比于現場采用的實時規則調度方法，調度優化性能提高26.4%.