考慮丟單的改進熱軋調度問題研究

吳曈 譚園園

摘要：本文對熱軋調度問題進行研究，在熱軋調度的研究中，加入了丟單的考慮。問題為三目標優化問題，采用人工蜂群算法（ABC）進行問題的求解。在文中給出了人工蜂群算法解決問題的三個改進方案，通過丟單優化、重構優化和禁忌搜索優化來提升算法的性能，以提獲得精度更高，更加優質的優質解。在此基礎上，設計了兩組對比仿真實驗，分別為：丟單未丟單對比仿真實驗和人工蜂群算法改進前后的對比實驗。借此驗證了丟單的有效性和改進的有效性。

關鍵詞：熱軋調度;訂單丟單;改進人工蜂群算法;多目標問題;組合優化

中圖分類號：U692.4+3? 文獻標識碼：A

文章編號：1009-3044（2021）29-0174-04

Research on the Improved Hot Rolling Scheduling Problem with Lost Orders

WU Tong， TAN Yuan-yuan

（College of Artificial Intelligence， Shenyang University of Technology， Shenyang 110870， China）

Abstract： In this paper， the hot rolling scheduling problem is studied. In the hot rolling scheduling research， the consideration of losing orders is added. The problem is a three ective optimization problem， which is solved by artificial bee colony algorithm （ABC）. In this paper， three improved schemes of artificial bee colony algorithm are given to solve the problem， which can improve the performance of the algorithm through order loss optimization， reconstruction optimization and tabu search optimization， so as to obtain higher accuracy and better quality solutions. On this basis， two groups of contrast simulation experiments are designed， which are： the contrast simulation experiment before and after the improvement of artificial bee colony algorithm. The effectiveness of the lost order and the effectiveness of the improvement are verified.

Key words： hot rolling scheduling; lost orders; mproved artificial bee colony algorithm; multi-ective problem; combinatorial opti?mization

1背景

進入新時代以來，我國對于鋼鐵的需求也不斷提升，包括鋼鐵的產量和鋼鐵的質量。對我國鋼鐵企業來說，鋼鐵行業的現狀既是機遇，也是挑戰。鋼鐵行業的重要產業之一是鋼鐵煉制，煉制過程是否能夠有序順利的進行，會對鋼鐵煉制企業的盈虧產生巨大的影響[1]。鋼鐵的加工主要包括三個過程，分別為煉鋼、連鑄和熱軋[2]。熱軋是整個加工的最后過程，合理的熱軋調度能夠有效提高生產效率和資源利用率，其重要程度也可想而知。

雖然目前存在大量對熱軋調度進行的研究，但對于考慮丟單問題的熱軋調度十分匱乏[3]。文獻[4]研究了鋼鐵一體化的調度問題，研究內容中包含熱軋調度問題，設計了遺傳算法來求解熱軋調度問題，未考慮丟單問題。文獻[5]同樣采用了遺傳算法作為主算法，該文獻以寶鋼某生產線為背景，進行了熱軋調度優化嘗試，同樣未考慮訂單丟單問題。文獻[6]研究了開放車間的調度問題，目標為最大化利潤，采用了改進人工魚群算法。文獻進行建模時，加入了訂單丟單約束，對滿足特定要求的工件進行丟單處理，通過實驗驗證了加入丟單處理后，能夠獲得更大利潤。文獻[7]說明了有些丟單并不是一個明智的做法，該文獻系統地分析和闡述了有些丟單操作不僅不能提高所獲得的利潤，還會讓企業利潤下滑。因此，盲目丟單并不可取，只有合理的丟單，才能達到預期的效果。本文提出了在熱軋調度中加入了丟單的考慮，使鋼鐵企業能夠通過合理丟單獲得更高的經濟效益和時間效益。同時還設計了改進人工蜂群算法進行問題的求解，三種改進的加入也大幅度地提高了算法的性能，增加了求解的精度。

2問題描述

考慮一批包含n個工件 J ={1， 2， 3， ...， n}的訂單集合，加工機器為一臺，每個工件在加工期內僅需進行一次加工，機器同一時刻只能加工單一工件。每個工件的加工有各自的要求，分別包括寬度要求、厚度要求和硬度要求，其中的寬度、厚度以及硬度表示每個工件在加工后需要達到的外形標準。每個工件也有各自的屬性，分別為所需加工時間屬性、工件價值屬性和工件信譽度屬性，其中加工時間表示工件加工所需的時間，工件價值表示加工工件能獲得的經濟效益，工件信譽度表示工件丟單后損失的信譽值。本文包括如下假設：每個工件之間相互獨立;任一工件加工均不可中斷;工件加工無需準備時間，且均可在零時刻開始加工。

機器加工過程中軋輥會產生相應的磨損，軋輥產生磨損會對工件的質量產生影響。未更換軋輥情況下，連續加工時間越長，工件質量越差，工件價值越低，為了降低這種影響，機器需要進行更換軋輥。另外，機器加工過程中會存在惰化效應和機器壞損，這也會對機器的加工效率產生影響。未進行維護情況下，連續加工時間越長，機器惰化效應越明顯，機器加工效率越低，工件所需加工時間越長。為了降低這種影響，機器需要進行預防性維護。本文研究的問題考慮如下優化目標：經濟成本目標、時間成本目標和信譽成本目標。

3數學模型

引入以下符號：n表示總工件訂單數量;F為經濟指標;tj和cj分別為工件j加工的起始時間和結束時間;Xi為工件信譽度; gj1，j2表示工件j1是否在工件j2前加工;tw表示單次更換軋輥所需時間; cv表示單次機器維護所需時間;m 為軋制單元個數;o 為

維護區間個數; w表示工件j加工后是否進行第k 次更換軋輥;vqj表示工件j加工后是否進行第q次維護;pj表示工件j加工時間;dhj表示工件訂單j加工前最近的機器維護結束時間;Sf為丟單工件訂單集合;So表示未丟單工件集合;Xj表示工件信譽度;dmj為丟單決策變量，為0表示工件不丟單，為1表示工件丟單;pd表示丟單比率最大值;tzk為更換軋輥起始時間;dzk為更換軋輥結束時間;tcp為機器維護起始時間;dcp為機器維護結束時間。

針對本問題，建立如下數學模型：

式（1）為最小化經濟成本;式（2）為最小化最大完工時間;式（3）為最小化信譽成本;式（4）為最大丟單數限制;式（5）為工件j 的加工起始時間;式（6）為工件j 的加工結束時間;式（7）為更換軋輥起始時間;式（8）為更換軋輥結束時間;式（9）為機器維護起始時間;式（10）為機器維護結束時間。

4算法及改進

算法流程主要包括以下九個部分，分別為編碼方式、解碼方式、丟單設計、初始解生成、重構設計、機器惰化效應設計、求解目標及優勢蜜源選擇、深度搜索設計以及最優解保留策略，主要進行編碼方式和機器惰化效應設計的介紹。改進方式分別為：丟單優化、重構優化以及禁忌搜索優化。

4.1編碼方式

本文的編碼包含兩類，分別為：丟單工件編碼和加工信息編碼。丟單信息編碼采用實數編碼，丟單信息編碼采用實數編碼結合0-1編碼方式。

其中加工信息編碼如下：

加工信息編碼為三位一組，三位按照順序分別為：加工順序位、更換軋輥位和機器維護位。圖1 中的編碼則表示加工順序為1-5，且在工件5后進行更換軋輥，工件1后機器維護。

4.2機器惰化效應設計

本文中的機器會隨著連續加工時長而產生惰化問題，即機器連續加工時長越長，機器加工效率越低，如圖2所示。

4.3丟單優化

在標準算法中，設定丟單選擇是無向隨機的，即任一工件訂單被選中丟單的概率都是相同的。然而在實際生產中，每個訂單都有自身獨特的屬性，這種屬性的不同使得每個訂單所帶來的凈效益也不相同。在丟單的選擇上，可以通過計算為每個訂單設計一個丟單值，再據此來設計每個訂單被選中丟單的概率。

設定工件丟單值符號表示為DDZ，DDZ值越高工件越容易被丟單，為了計算DDZ值，可以將其拆分為三類指標分別進行計算，這三類指標分別為時間指標、經濟指標和信譽指標，符號表示分別為SD、XD和JD。

時間指標 SD 以及信譽指標XD 可以分別用式（11）和式（12）進行計算，式中的SJi和XYi分別表示工件i的加工時間和信譽值，So表示進行加工的工件集合。

經濟指標JD 內包含三個子指標，分別為工件價值指標、工件硬度指標和工件寬度厚度聯合指標，符號表示分別為JZD、 YDD 和KHD。其中工件價值越大，工件丟單值應越低，所以首先需要對工件價值做反向處理，如式（13）所示，式中的JZj表示工件j 的價值：

其中FJZ表示反向價值，JZ表示工件價值，為防止出現0的情況，在尾端進行加一處理。在此基礎上，工件價值指標可以由式（14）計算得出：

工件硬度指標在計算中，首先將工件硬度根據表3.2進行量化處理，工件硬度指標反映測算工件在全部工件中硬度的差別度，需要計算測算工件到其他所有工件的距離之和同所有工件到其他工件距離之和占比，隨后由式（15）來進行計算，式中的YDi表示工件i的硬度量化值：

工件寬度厚度聯合指標可以由式（16）進行計算，式中的KDi和HDi分別表示工件i的寬度值和厚度值：

最后將這些指標按照式（17）融合并進行歸一化處理，得到了丟單值：

4.4重構優化

重構指的是，在同一軋制單元內，對工件進行重新排產，以使得不可行解變為可行解。在實驗中選擇了其中最優的重構方式作為優化后的重構方式來完成算法的求解。

對于信譽成本來講，重構方式并不會影響結果;對于時間成本來講，由于重構調整均于同一軋制單元內，時間成本也不會受到影響。所以，只有經濟成本會受到重構方式的影響。經濟成本中，能夠受重構方式改變影響的僅有寬度、厚度和硬度跳變所帶來的電力成本大小。進一步分析，重構方式對厚度和硬度跳變所帶來的電力成本大小的影響是隨機的，所以這部分影響同樣不考慮。最終，重構方式在理論上僅會對寬度跳變成本產生非概率性影響。

寬度跳變成本中，上升重構和下降重構單個軋制單元中寬度跳變累加值為當前軋制單元中寬度最大值同寬度最小值的差，而極大值重構的寬度跳變累加值永遠大于等于上升重構和下降重構的該值。另外，為了提高解的多樣性，最終選擇上升下降重構為改進后的重構方式。

4.5禁忌搜索優化

禁忌搜索可以使解的搜索避免產生回路，為了提升算法效率，本文設計了禁忌搜索同人工蜂群相結合的方法來提升算法性能。

為了解決禁忌表消耗內存過大問題，設計了簡化禁忌表。在簡化禁忌解的記錄中，只保存蜜源中的變化部分，未變化部分則不予記錄。

對于記錄部分來說，有兩類信息，一個是在蜜源中的位置信息，也稱為信息位;另一個是其內部的數據信息，也稱為數據位。如圖3所示：

在該簡化禁忌解中，為了區分位置和數據兩類信息，將位置信息均取其相反數，由于存在-1作為是否更換軋輥以及是否進行機器維護的判別數，位置信息會反向增加一個數量為1 的偏差數，如-4代表位置偏移量為3。除此之外，-2表示前后兩數據位置相鄰，為了簡化數據長度，將-2省略。上圖的簡化禁忌解中，第一位為3，為數據位，蜜源第一位存在變動，變動后的數據信息為3;簡化禁忌解第二位為-4，小于-1，為位置位，表示3位的偏移;第三位為8，為數據位，結合上一位-4的3位偏移量，蜜源第四位存在變動，變動后的數據信息為8;禁忌解第四位為0，為數據位，數據位相連，說明省略位置位-2，所以蜜源第五位存在變動，變動后的數據為0。以此類推，結合初始蜜源，可得出該簡化禁忌解所表示蜜源的完整信息。

5實驗及仿真結果

本文通過國內某鋼廠的真實算例，來完成實驗仿真。圖4為考慮丟單和未考慮丟單實驗結果仿真圖。由于未丟單不存在信譽成本，因此對比實驗為雙目標。

圖中三角形為無丟單狀態下的優質解，十字符為有丟單狀態下的優質解，有丟單狀態下的優質解在經濟成本和時間成本上均優于無丟單狀態下的優質解，因此說明丟單存在效果，驗證了丟單的有效性。

表2和表3分別為考慮丟單情況下，標準人工蜂群算法和改進人工蜂群算法在規模為150、200和250情況下進行10組同算例的平均值結果對比表和方差結果對比表。表2中可以看出，標準人工蜂群算法在三個指標的平均值上均大于改進人工蜂群算法，這也說明了改進后的人工蜂群算法在性能上優于標準人工蜂群算法;表3中可以看出，標準人工蜂群算法在三個指標的方差上均大于改進人工蜂群算法，這也說明了改進后的人工蜂群算法在穩定性上優于標準人工蜂群算法。表中還表明，無論規模大小，改進人工蜂群算法均優于標準人工蜂群算法，說明改進存在效果，驗證了改進的有效性。

6結論

熱軋是整個加工的最后過程，合理的熱軋調度能夠有效提高生產效率和資源利用率，本文對熱軋調度進行研究并進行實驗仿真，得到了如下結論：

1）通過仿真實驗驗證可知，在考慮丟單問題后，實驗結果無論在經濟成本還是在時間成本上，均優于未考慮丟單問題的情況。因此丟單能夠更好地提高解的質量。

2）通過仿真實驗驗證可知，在進行了丟單優化、重構優化以及禁忌搜索優化后，實驗結果無論在經濟指標、時間指標還是信譽指標的均值和方差上，均優于標準人工蜂群算法。因此可以認為改進存在效果，能夠有效提升算法精度和穩定性。參考文獻：

[1] He Y， Liao N， Rao J， et al. Energy conservation path of China iron and steel industry driven by relative policies[J].Energy Ef? ficiency，2021， 14（1）：14-16.

[2]黃輝，羅小川，鄭秉霖，等.煉鐵-煉鋼區間鐵水重調度方法及其應用[J].系統工程學報，2013，28（2）：234-247.

[3] Viana M S， Junior O M， Contreras R C. A modified genetic al?gorithm with local search strategies and multi-crossover opera? tor for job shop scheduling problem[J]. Sensors， 2020， 20（18）：32-35.

[4] Tang L， Liu J， Rong A， et al. A review of planning and sched?uling systems and methods for integrated steel production[J]. European Journal of Operational Research， 2001，133（1）：1-20.

[5]王冰.熱軋生產計劃優化方法的研究與應用[D].大連：大連理工大學，2005.

[6] Sheikhalishahi M， Eskandari N， Mashayekhi A， et al. Multiective open shop scheduling by considering human error and preventive maintenance[J]. Applied Mathematical Model? ling， 2019， 67（4）：573-587.

[7]劉峰源.從一則案例說說那些"本不該丟掉"的訂單[J].印刷技術，2019，742（10）：52-54.

【通聯編輯：梁書】