吳曈 譚園園

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

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

中圖分類號(hào)：U692.4+3? 文獻(xiàn)標(biāo)識(shí)碼：A

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

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

2問(wèn)題描述

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

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

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

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

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

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

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

4算法及改進(jìn)

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

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

4.3丟單優(yōu)化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6結(jié)論

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

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

2）通過(guò)仿真實(shí)驗(yàn)驗(yàn)證可知，在進(jìn)行了丟單優(yōu)化、重構(gòu)優(yōu)化以及禁忌搜索優(yōu)化后，實(shí)驗(yàn)結(jié)果無(wú)論在經(jīng)濟(jì)指標(biāo)、時(shí)間指標(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é)報(bào)，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)計(jì)劃優(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]劉峰源.從一則案例說(shuō)說(shuō)那些"本不該丟掉"的訂單[J].印刷技術(shù)，2019，742（10）：52-54.

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