考慮丟單的改進(jìn)熱軋調(diào)度問題研究

吳曈 譚園園

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

關(guān)鍵詞：熱軋調(diào)度;訂單丟單;改進(jìn)人工蜂群算法;多目標(biāo)問題;組合優(yōu)化

中圖分類號：U692.4+3? 文獻(xiàn)標(biāo)識碼：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背景

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

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

2問題描述

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

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

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

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

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

針對本問題，建立如下數(shù)學(xué)模型：

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

4算法及改進(jìn)

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

4.1編碼方式

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

其中加工信息編碼如下：

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

4.2機(jī)器惰化效應(yīng)設(shè)計

本文中的機(jī)器會隨著連續(xù)加工時長而產(chǎn)生惰化問題，即機(jī)器連續(xù)加工時長越長，機(jī)器加工效率越低，如圖2所示。

4.3丟單優(yōu)化

在標(biāo)準(zhǔn)算法中，設(shè)定丟單選擇是無向隨機(jī)的，即任一工件訂單被選中丟單的概率都是相同的。然而在實(shí)際生產(chǎn)中，每個訂單都有自身獨(dú)特的屬性，這種屬性的不同使得每個訂單所帶來的凈效益也不相同。在丟單的選擇上，可以通過計算為每個訂單設(shè)計一個丟單值，再據(jù)此來設(shè)計每個訂單被選中丟單的概率。

設(shè)定工件丟單值符號表示為DDZ，DDZ值越高工件越容易被丟單，為了計算DDZ值，可以將其拆分為三類指標(biāo)分別進(jìn)行計算，這三類指標(biāo)分別為時間指標(biāo)、經(jīng)濟(jì)指標(biāo)和信譽(yù)指標(biāo)，符號表示分別為SD、XD和JD。

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

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

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

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

工件寬度厚度聯(lián)合指標(biāo)可以由式（16）進(jìn)行計算，式中的KDi和HDi分別表示工件i的寬度值和厚度值：

最后將這些指標(biāo)按照式（17）融合并進(jìn)行歸一化處理，得到了丟單值：

4.4重構(gòu)優(yōu)化

重構(gòu)指的是，在同一軋制單元內(nèi)，對工件進(jìn)行重新排產(chǎn)，以使得不可行解變?yōu)榭尚薪?。在?shí)驗(yàn)中選擇了其中最優(yōu)的重構(gòu)方式作為優(yōu)化后的重構(gòu)方式來完成算法的求解。

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

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

4.5禁忌搜索優(yōu)化

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

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

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

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

5實(shí)驗(yàn)及仿真結(jié)果

本文通過國內(nèi)某鋼廠的真實(shí)算例，來完成實(shí)驗(yàn)仿真。圖4為考慮丟單和未考慮丟單實(shí)驗(yàn)結(jié)果仿真圖。由于未丟單不存在信譽(yù)成本，因此對比實(shí)驗(yàn)為雙目標(biāo)。

圖中三角形為無丟單狀態(tài)下的優(yōu)質(zhì)解，十字符為有丟單狀態(tài)下的優(yōu)質(zhì)解，有丟單狀態(tài)下的優(yōu)質(zhì)解在經(jīng)濟(jì)成本和時間成本上均優(yōu)于無丟單狀態(tài)下的優(yōu)質(zhì)解，因此說明丟單存在效果，驗(yàn)證了丟單的有效性。

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

6結(jié)論

熱軋是整個加工的最后過程，合理的熱軋調(diào)度能夠有效提高生產(chǎn)效率和資源利用率，本文對熱軋調(diào)度進(jìn)行研究并進(jìn)行實(shí)驗(yàn)仿真，得到了如下結(jié)論：

1）通過仿真實(shí)驗(yàn)驗(yàn)證可知，在考慮丟單問題后，實(shí)驗(yàn)結(jié)果無論在經(jīng)濟(jì)成本還是在時間成本上，均優(yōu)于未考慮丟單問題的情況。因此丟單能夠更好地提高解的質(zhì)量。

2）通過仿真實(shí)驗(yàn)驗(yàn)證可知，在進(jìn)行了丟單優(yōu)化、重構(gòu)優(yōu)化以及禁忌搜索優(yōu)化后，實(shí)驗(yàn)結(jié)果無論在經(jīng)濟(jì)指標(biāo)、時間指標(biāo)還是信譽(yù)指標(biāo)的均值和方差上，均優(yōu)于標(biāo)準(zhǔn)人工蜂群算法。因此可以認(rèn)為改進(jìn)存在效果，能夠有效提升算法精度和穩(wěn)定性。參考文獻(xiàn)：

[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]黃輝，羅小川，鄭秉霖，等.煉鐵-煉鋼區(qū)間鐵水重調(diào)度方法及其應(yīng)用[J].系統(tǒng)工程學(xué)報，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]王冰.熱軋生產(chǎn)計劃優(yōu)化方法的研究與應(yīng)用[D].大連：大連理工大學(xué)，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].印刷技術(shù)，2019，742（10）：52-54.

【通聯(lián)編輯：梁書】