考慮機(jī)器檢修的圓鋼熱軋批量調(diào)度算法

許紹云，李鐵克，王 雷，王柏琳，柏 亮，董廣靜

（1.北京科技大學(xué) 東凌經(jīng)濟(jì)管理學(xué)院，北京 100083；2.北京科技大學(xué) 鋼鐵生產(chǎn)制造執(zhí)行系統(tǒng)技術(shù)教育部工程研究中心，北京 100083；3.中國刑事警察學(xué)院 治安學(xué)系，遼寧 沈陽 110854）

0 引言

熱軋批量調(diào)度是鋼鐵企業(yè)生產(chǎn)管理的一個(gè)重要任務(wù)，是根據(jù)熱軋工序中相應(yīng)的生產(chǎn)約束和規(guī)則對生產(chǎn)訂單或原料鋼坯進(jìn)行組合形成軋制批，并對軋制批排定先后加工順序，從而確定各自的加工時(shí)間的過程。由于熱軋生產(chǎn)過程具有較高的復(fù)雜性，熱軋批量調(diào)度的好壞對企業(yè)的生產(chǎn)效率和產(chǎn)品的質(zhì)量具有關(guān)鍵性的影響，因此，有效的熱軋批量調(diào)度對提高企業(yè)生產(chǎn)效率、增強(qiáng)企業(yè)市場競爭力具有重要的意義。

現(xiàn)有的關(guān)于熱軋批量調(diào)度的研究，根據(jù)產(chǎn)品種類主要分為熱軋帶鋼批量調(diào)度、熱軋鋼管批量調(diào)度、棒線材（熱軋圓鋼）批量調(diào)度等。熱軋帶鋼作為鋼鐵企業(yè)的主要產(chǎn)品，其批量調(diào)度問題受到最廣泛的關(guān)注，文獻(xiàn)［1］將熱軋批量問題歸結(jié)為帶軟時(shí)間窗的車輛路徑問題，通過建立單目標(biāo)的約束滿足模型實(shí)現(xiàn)問題的求解；文獻(xiàn)［2］考慮熱軋批量計(jì)劃與煉鋼連鑄批量計(jì)劃的協(xié)調(diào)性，提出一體化批量計(jì)劃編制策略，并采用約束滿足算法對問題進(jìn)行求解；文獻(xiàn)［3］將熱軋批量調(diào)度問題歸結(jié)為多路徑問題，并提出一種基于精確算法和啟發(fā)式算法的混合算法對問題進(jìn)行求解；文獻(xiàn)［4］將問題分為選坯、組批、排序三個(gè)過程，建立基于獎(jiǎng)金收集車輛路徑問題（Prize Collecting Vehicle Routing Problem，PCVRP）的多目標(biāo)優(yōu)化模型，并分別采用基于分解策略和Pareto最優(yōu)的蟻群算法對問題進(jìn)行求解。熱軋鋼管作為一類重要的經(jīng)濟(jì)型鋼材，由于其熱軋工藝的復(fù)雜性，其批量調(diào)度問題的研究具有重要的意義［5-7］，問題的研究主要以訂單為基本組織單元，求解過程主要分為組批和軋批排序兩個(gè)階段，問題優(yōu)化對象主要是批次之間的轉(zhuǎn)產(chǎn)調(diào)整時(shí)間和調(diào)整費(fèi)用。對于在鋼鐵企業(yè)中普遍存在的棒線材（熱軋圓鋼）產(chǎn)品，由于在生產(chǎn)組織方式上與熱軋鋼管具有一定的相似性，其熱軋批量調(diào)度問題同樣考慮將訂單組合為軋制批，批量排序時(shí)考慮批次間的調(diào)整時(shí)間［8］，問題通常被歸結(jié)為調(diào)整時(shí)間與加工順序有關(guān)的調(diào)度問題進(jìn)行求解，在制定調(diào)度計(jì)劃時(shí)使總的調(diào)整時(shí)間和費(fèi)用最少［9］。

本文根據(jù)圓鋼熱軋生產(chǎn)的特點(diǎn)，在以往研究的基礎(chǔ)上，針對軋制批量排序階段，考慮生產(chǎn)過程中存在的機(jī)器檢修維護(hù)的情況，建立熱軋工序軋制批量調(diào)度的多目標(biāo)整數(shù)規(guī)劃模型；結(jié)合問題特征，提出改進(jìn)的帶精英策略的快速非支配排序遺傳算法（Nondominated Sorting Genetic Algorithm Ⅱ，NSGA-Ⅱ）進(jìn)行求解；最后通過數(shù)據(jù)實(shí)驗(yàn)驗(yàn)證模型和求解算法的可行性和有效性。

1 問題建模

1.1 問題描述

圓鋼熱軋生產(chǎn)過程的一個(gè)顯著特點(diǎn)在于軋制不同規(guī)格的產(chǎn)品需要不同的機(jī)架，這也意味著軋制不同規(guī)格的訂單時(shí)需要進(jìn)行機(jī)器調(diào)整，這一特征致使圓鋼在熱軋生產(chǎn)中需要采取批量成組加工方式，即將同類（同規(guī)格、同鋼種等）的訂單組合成軋制批進(jìn)行生產(chǎn)，以保證生產(chǎn)的高效連續(xù)性。此外，在機(jī)器調(diào)整過程中，拆裝機(jī)架的時(shí)間不同，導(dǎo)致不同批量的加工順序可能會(huì)具有不同的機(jī)器調(diào)整時(shí)間，因此，在制定批量調(diào)度計(jì)劃時(shí)需要考慮批量加工順序?qū)C(jī)器調(diào)整時(shí)間的影響。由此可見，圓鋼熱軋批量調(diào)度問題可以歸結(jié)為一類帶有實(shí)際生產(chǎn)約束的具有順序依賴調(diào)整時(shí)間的批調(diào)度問題（Batch Scheduling Problem with Sequence-dependent Setup Time，BSPSST）。

在制定圓鋼熱軋批量調(diào)度優(yōu)化方案時(shí)，根據(jù)其生產(chǎn)管理的特點(diǎn)和需求，主要考慮以下優(yōu)化目標(biāo)：

（1）產(chǎn)能利用率最大化 產(chǎn)能利用率在這里是指除機(jī)器檢修和機(jī)器調(diào)整時(shí)間外的剩余計(jì)劃期間內(nèi)機(jī)器的使用情況，通過加工與檢修時(shí)間差來衡量，加工和檢修兩者的時(shí)間差是由機(jī)器檢修情況決定的。在實(shí)際生產(chǎn)中，機(jī)器需要定期進(jìn)行檢修維護(hù)，因此批量只允許在檢修維護(hù)時(shí)間之外的計(jì)劃期間內(nèi)排產(chǎn)。為保證批量加工的連續(xù)性，規(guī)定批量不能跨越檢修計(jì)劃進(jìn)行加工，這樣就造成了批量加工過程和檢修過程之間具有不能銜接的時(shí)間差，且不同的批量加工順序產(chǎn)生的時(shí)間差大小不同。時(shí)間差的存在會(huì)造成產(chǎn)能資源的浪費(fèi)，因此，制定調(diào)度計(jì)劃時(shí)需要將該時(shí)間差作為優(yōu)化目標(biāo)。圖1是對三個(gè)批量J1，J2和J3的調(diào)度示意圖，機(jī)器閑置時(shí)間即為加工和檢修兩者的時(shí)間差，從圖中可以看出，不同的批量加工順序產(chǎn)生的機(jī)器調(diào)整時(shí)間和機(jī)器閑置時(shí)間不同，使得最終的完工時(shí)間不同，批量順序J1，J3和J2要比J1，J2和J3具有更高的產(chǎn)能利用率。

（2）機(jī)器調(diào)整時(shí)間最小化 在圓鋼軋制過程中，若頻繁切換產(chǎn)品規(guī)格，會(huì)產(chǎn)生較多的機(jī)器調(diào)整時(shí)間，使得生產(chǎn)周期延長，造成生產(chǎn)效率降低。因此，制定調(diào)度計(jì)劃時(shí)，應(yīng)盡可能地將同規(guī)格的批量集中軋制，且對不同規(guī)格的批量確定有效的軋制順序，最大限度地減少機(jī)器調(diào)整時(shí)間，提高生產(chǎn)效率。

（3）所有被調(diào)度的訂單的交貨提前和拖期時(shí)間最小化 訂單在軋制過程中以批量的形式提交，在訂單的管理過程中，企業(yè)在接受訂單的同時(shí)向客戶承諾了產(chǎn)品交貨期，因此每個(gè)訂單需要盡量在承諾的交貨期內(nèi)進(jìn)行交貨，若訂單完成時(shí)間早于交貨期，則會(huì)在貨物等待發(fā)運(yùn)的過程中造成相應(yīng)的庫存成本，若訂單完成時(shí)間晚于交貨期，則會(huì)使企業(yè)的信譽(yù)降低。因此，批量調(diào)度中需要考慮交貨期的影響，盡可能地減少訂單提前或拖期的時(shí)間。

根據(jù)實(shí)際生產(chǎn)的特點(diǎn)，問題存在的約束條件具體有：①由于進(jìn)行調(diào)度的批量是經(jīng)過核算后確定在當(dāng)前計(jì)劃期間內(nèi)加工的，調(diào)度后最后一個(gè)批量的完工時(shí)間不能大于計(jì)劃期間的末端時(shí)刻；②同種規(guī)格的批量之間的順序必須遵循鋼種的優(yōu)先級順序；③同一批量加工過程中不允許中斷，即不能跨越機(jī)器檢修期間，不能插入其他批量進(jìn)行加工；④某一時(shí)刻，機(jī)器只能加工一個(gè)批量，不允許多個(gè)批量同時(shí)進(jìn)行加工。

1.2 問題模型

（1）符號定義

（2）變量定義

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

其中：目標(biāo)函數(shù)（1）表示最小化機(jī)器加工與檢修之間的時(shí)間差；目標(biāo)函數(shù)（2）表示最小化機(jī)器總的調(diào)整時(shí)間；目標(biāo)函數(shù)（3）表示最小化訂單的提前和拖期總時(shí)間，其中，訂單的完工時(shí)間取訂單所在批量的完工時(shí)間；約束（4）和約束（5）表示批量加工過程不能跨越檢修計(jì)劃；約束（6）定義了相鄰批量之間的機(jī)器調(diào)整時(shí)間；約束（7）定義了批量的完工時(shí)間；約束（8）表示兩個(gè)相鄰批量之間的加工順序關(guān)系，同一時(shí)刻機(jī)器只能加工一個(gè)批量，且批量加工過程連續(xù)，不可中斷插入其他批量；約束（9）表示規(guī)格相同的兩個(gè)相鄰批量之間加工先后順序要滿足鋼種的優(yōu)先級關(guān)系，即先加工的批量的鋼種優(yōu)先級不能低于后加工的批量的鋼種優(yōu)先級；約束（10）表示批量的完工時(shí)間不能晚于計(jì)劃期的末端時(shí)刻；約束（11）為變量取值約束。

2 求解算法

由問題模型可以看出，考慮機(jī)器檢修的圓鋼熱軋批量調(diào)度問題是一類具有多目標(biāo)、多約束條件的排序優(yōu)化問題，具有NP難的特性，精確算法難以在可行的時(shí)間內(nèi)求得有效解。此外，解決多目標(biāo)的優(yōu)化問題需要對相互沖突的子目標(biāo)進(jìn)行綜合考慮，協(xié)調(diào)各個(gè)目標(biāo)間的沖突值，使得問題的求解變得更加困難。NSGA-Ⅱ［10］是Deb于2000年在非支配排序遺傳算法（Non-dominated Sorting Genetic Algorithm，NSGA）的基礎(chǔ)上提出的，具有運(yùn)行速度快、解集收斂性好的優(yōu)點(diǎn)，由于它在種群規(guī)模、操作概率等模糊或明確的參數(shù)方面沒有固定的要求，被廣泛應(yīng)用于實(shí)際項(xiàng)目中的多目標(biāo)問題的求解。NSGA-Ⅱ在NSGA 的基礎(chǔ)上主要針對如下三個(gè)方面進(jìn)行了改進(jìn)：

（1）采用快速非支配排序，降低算法的計(jì)算復(fù)雜度。

（2）提出擁擠度的概念，確定個(gè)體之間的緊密程度，為快速排序后的同級比較提供依據(jù)，使準(zhǔn)Pareto域中的個(gè)體擴(kuò)展到整個(gè)Pareto域并均勻分布，保持了種群的多樣性。

（3）引入精英策略，擴(kuò)大采樣空間，將父代種群與子代種群組合，共同競爭產(chǎn)生下一代種群，保證了種群個(gè)體的優(yōu)良性。

對本文所考慮的問題，采用NSGA-Ⅱ算法求解時(shí)主要解決的問題包括：編碼規(guī)則的設(shè)計(jì)、適應(yīng)度函數(shù)的定義及計(jì)算、初始解的生成、選擇策略及精英策略的確定、遺傳操作方式的選擇等；此外，由于本文問題具有復(fù)雜的約束條件，基本的NSGA-Ⅱ算法在產(chǎn)生初始種群和迭代過程中并不能保證所有個(gè)體的可行性，從而可能得不到最終有效的求解結(jié)果。為此，本章提出改進(jìn)的NSGA-Ⅱ算法（Modified Nondominated Sorting Genetic Algorithm Ⅱ，MNSGA-Ⅱ）以實(shí)現(xiàn)問題的有效求解。

2.1 編碼規(guī)則

軋制批量調(diào)度主要是確定軋制批的加工先后順序和加工時(shí)間，其解的構(gòu)成即是一系列軋制批量構(gòu)成的序列。算法采用十進(jìn)制的自然順序排列的批量順序來表示染色體。

例如，對于由10 個(gè)批量構(gòu)成的批量集合Z=｛1，2，3，4，5，6，7，8，9，10｝，若批量的加工順序?yàn)?→3→4→2→8→5→7→6→10→9，則其編碼為x=［1，3，4，2，8，5，7，6，10，9］。

2.2 種群初始化

基本的NSGA-Ⅱ初始解都是隨機(jī)產(chǎn)生的，而隨機(jī)生成的初始種群會(huì)存在違反約束條件的不可行解，且即使在可行的情況下也無法保障解的質(zhì)量。本算法在初始階段，利用改進(jìn)的NEH 算法（Modified NEH，MNEH）產(chǎn)生局部滿意的初始解，為了保證初始種群的多樣性，MNEH 在基本的NEH 算法的基礎(chǔ)上，通過不同的初始排序規(guī)則形成不同的染色體。由于本文問題具有多目標(biāo)的特性，與經(jīng)典的NEH 算法依據(jù)單適應(yīng)度函數(shù)值逐步優(yōu)化的方式不同，這里采用了文獻(xiàn)［11］中提出的變權(quán)重組合法，采用隨機(jī)權(quán)重的方式將問題的多個(gè)目標(biāo)構(gòu)造成單目標(biāo)的適應(yīng)度函數(shù)，如下：

式中w1，w2，w3≥0。

采用MNEH 算法產(chǎn)生popSize個(gè)初始解的具體步驟如下：

算法1 MNEH 算法。

步驟1 正向NEH 產(chǎn)生第一條染色體。

步驟1.1 按照批量在所有工序上的總加工時(shí)長由大到小的順序，對k個(gè)批量進(jìn)行初始排序。

步驟1.2 隨機(jī)生成三個(gè)權(quán)重系數(shù)w1，w2和w3，取前兩個(gè)批量調(diào)度，根據(jù)式（12）計(jì)算適應(yīng)度值并選擇適應(yīng)度值最小的批量順序。

步驟1.3 令z從3～k變化，z每增加一個(gè)值，就隨機(jī)生成三個(gè)權(quán)重系數(shù)w1，w2和w3，在不改變序列中z-1個(gè)批量先后順序的條件下，將第z個(gè)批量插入當(dāng)前序列中z個(gè)可能的位置，計(jì)算z插入每個(gè)位置后形成的批量序列對應(yīng)的適應(yīng)度函數(shù)值，最后選擇具有最小適應(yīng)度函數(shù)值的序列；重復(fù)此過程，獲得使k個(gè)批量具有最小適應(yīng)值的序列。

步驟1.4 將得到的具有最小適應(yīng)度函數(shù)值的序列經(jīng)過編碼形成染色體。

步驟2 反向NEH 產(chǎn)生第二條染色體。

與步驟1相似，只是在初始排序時(shí)按照批量總加工時(shí)長由小到大的順序進(jìn)行排序。

步驟3 改進(jìn)的正向NEH 產(chǎn)生剩余的popSize-2條染色體。

每生成一個(gè)染色體，改進(jìn)正向NEH 的初始排序規(guī)則，即任選兩個(gè)批量作為初始序列的前兩個(gè)批量，剩余的k-2個(gè)批量按照加工時(shí)長由大到小的順序排序，其他步驟同步驟1.2～步驟1.4。

2.3 適應(yīng)度函數(shù)設(shè)計(jì)與種群修復(fù)

NSGA-Ⅱ在搜索進(jìn)化過程中根據(jù)適應(yīng)度函數(shù)值來評價(jià)個(gè)體的優(yōu)劣，是非支配排序的度量依據(jù)，對算法進(jìn)化的方向起指導(dǎo)作用。由于模型具有多目標(biāo)、多約束條件的特征，為保證種群進(jìn)化過程中子代個(gè)體的可行性，對適應(yīng)度函數(shù)進(jìn)行相應(yīng)的設(shè)計(jì)，采用懲罰函數(shù)的思想，將部分關(guān)鍵的約束條件以懲罰值的形式加入目標(biāo)函數(shù)中，構(gòu)造適應(yīng)度函數(shù)：

規(guī)則1 對重復(fù)個(gè)體x1=x2=…=xk′，保留一個(gè)個(gè)體x1不變，其他個(gè)體經(jīng)過變異形成新個(gè)體，為保證個(gè)體與原解的相近性，變異采用交換個(gè)體中任意兩個(gè)基因位置的方式，所有的重復(fù)個(gè)體更新為x1←x1，x2←Mut（x2），…，xk′←Mut（xk′），Mut（xi）為任意交換xi中兩個(gè)基因的位置。

規(guī)則2 對不可行個(gè)體，或直接進(jìn)行修復(fù)轉(zhuǎn)化為可行解，或淘汰并由種群中其他個(gè)體的變異代替。對不可行個(gè)體x=（x1，x2，…，xn）的修復(fù)操作如下：

（1）若f2（x）＜0，則說明該個(gè)體違背約束（10），淘汰x，選擇種群中其他某個(gè)個(gè)體x′≠x，令x←Mut（x′）；

（2）若f3（x）＜0，則說明個(gè)體x違背約束條件（9），直接對x進(jìn)行修復(fù)，確定個(gè)體x中滿足條件o（gxi）＜o(jì)（gxi+1）∧sxixi+1=0 的相鄰分量xi，xi+1，交換xi，xi+1的先后順序，重復(fù)尋找滿足條件o（gxi）＜o(jì)（gxi+1）∧sxixi+1=0 的相鄰分量并交換先后順序，直到不存在任意兩個(gè)相鄰分量違背鋼種優(yōu)先級關(guān)系。

2.4 加工時(shí)間計(jì)算

式中Q是一個(gè)足夠大的正數(shù)。

通過適應(yīng)度函數(shù)的定義可以看出，對于種群中的任何一個(gè)個(gè)體，只要個(gè)體內(nèi)的批量順序違背約束條件就會(huì)受到較大的懲罰，因?yàn)槟Ｐ椭械哪繕?biāo)函數(shù)值都是正數(shù)，且約束中的正偏移量也均為正數(shù)，所以滿足約束條件的個(gè)體對應(yīng)的適應(yīng)度函數(shù)值必定是正數(shù)，而不可行的個(gè)體對應(yīng)的適應(yīng)度函數(shù)值則為負(fù)數(shù)。

種群進(jìn)化過程中不可避免地會(huì)出現(xiàn)彼此相同的重復(fù)個(gè)體或不可行個(gè)體，由于重復(fù)個(gè)體占據(jù)過多的種群空間，造成種群空間資源的浪費(fèi)，不可行個(gè)體使得種群存在不合理性，易產(chǎn)生進(jìn)化方向的傾斜，兩者的存在不利于種群的優(yōu)化，為此，需要不斷地對種群進(jìn)行修復(fù)，修復(fù)規(guī)則如下：

由于本文的問題考慮到機(jī)器的檢修計(jì)劃，在排定的批量順序中確定批量的加工時(shí)間時(shí)需要避開機(jī)器檢修的時(shí)間。在確定每個(gè)批量加工時(shí)間時(shí)，不僅需要考慮工件的加工時(shí)長和調(diào)整時(shí)間，還要考慮檢修計(jì)劃的時(shí)間。下面根據(jù)模型中的約束（4）和約束（5），具體分析批量的加工開始時(shí)間和結(jié)束時(shí)間的確定。

對于最終得到的批量加工順序Z=｛z1，…，zk｝，計(jì)算其中每個(gè)批量的加工開始時(shí)間和結(jié)束時(shí)間的方法如下：

（1）對于加工順序中處于第一位的批量z1，由于機(jī)器處于準(zhǔn)備加工的狀態(tài)，不考慮調(diào)整時(shí)間，其原則上的加工開始時(shí)間為計(jì)劃開始時(shí)間，即bz1=0，進(jìn)而判斷該批量加工過程中是否有檢修計(jì)劃，即是否滿足可直接加工條件bz1+pbz1≤min｛Sm｜bz1≤Sm，m∈M｝：

1）若滿足可直接加工條件，即加工過程中無檢修計(jì)劃，則可直接得到批量z1的加工完成時(shí)間Cbz1=pbz1。

2）若不滿足條件，則找出所有跨越的檢修計(jì)劃集合Mz1=｛m｜bz1≤Sm，bz1+pbz1≥Em，m∈M｝，考慮到加工過程不能跨越檢修計(jì)劃，更新批量z1的實(shí)際開始加工時(shí)間為bz1←max｛Em｜m∈Mz1｝，進(jìn)而得到完工時(shí)間Cbz1=bz1+pbz1。

（2）對于加工順序中其他位置的批量zi（i=2，…，k），由于機(jī)器已經(jīng)經(jīng)過一定的加工過程，處于上一個(gè)批量zi-1加工完成狀態(tài)，需要根據(jù)批量與上一個(gè)加工完成的批量之間的屬性相關(guān)性關(guān)系，判斷是否需要進(jìn)行機(jī)器調(diào)整，即通過約束（6）計(jì)算調(diào)整時(shí)間szi-1zi。原則上批量zi的開始時(shí)間為bzi←Cbzi-1+szi-1zi，進(jìn)一步判斷是否跨越檢修計(jì)劃，該過程與批量z1的相同。

通過上述兩個(gè)過程，得到批量加工順序Z=｛z1，…，zk｝中每個(gè)批量zi的加工開始時(shí)間和完成時(shí)間，則目標(biāo)函數(shù)（1）～（3）可以直接通過計(jì)算得到。

2.5 非支配排序和擁擠度的計(jì)算

非支配排序和擁擠度計(jì)算是對種群中的個(gè)體進(jìn)行評估的過程，是NSGA-Ⅱ算法確定個(gè)體優(yōu)劣的基本步驟。為了更好地實(shí)現(xiàn)評估過程，首先，針對本文問題的特點(diǎn)，確定解的支配及相關(guān)概念［12］：

定義1 支配。原則上若解x=（x1，x2，…，xn）支配解x′=（x′1，x′2，…，x′n），則當(dāng)且僅當(dāng)對任意的目標(biāo)函數(shù)fi∈F（F為目標(biāo)函數(shù)集合），滿足fi（x）≤fi（x′）且?fi∈F，使得fi（x）＜fi（x′）。

定義2 非支配解。若解x=（x1，x2，…，xn）為非支配解，則當(dāng)且僅當(dāng)在當(dāng)前所有參與對比的解X=｛x0，x1，…，xk｝中，不存在一個(gè)xj，使得對任意的fi∈F都滿足fi（xj）＜fi（x）。

（1）非支配排序

非支配排序主要根據(jù)支配概念對種群中的個(gè)體進(jìn)行優(yōu)劣排序，并確定個(gè)體的非支配等級［10］。對于規(guī)模為popSize的種群P中的每個(gè)個(gè)體xi，首先設(shè)置種群中支配個(gè)體xi的個(gè)體數(shù)量ni和種群中被個(gè)體xi支配的個(gè)體集合Subi兩個(gè)參數(shù)。具體的排序過程為：

1）令前沿非支配級別rank=1，針對整個(gè)種群，尋找所有的非支配解，即ni=0的個(gè)體xi，令其非支配等級rank（xi）=1，并存入第一級前沿非支配集合F1中，同時(shí)，Subi也得以確定。

2）令rank←rank+1，對每個(gè)個(gè)體xi∈Frank-1對應(yīng)的集合Subi，檢驗(yàn)其中的每個(gè)個(gè)體xj∈Subi的nj，令nj=nj-1，若滿足條件nj=0，則令個(gè)體xj的非支配級數(shù)為rank（xj）=rank，并由所有級數(shù)為rank的個(gè)體構(gòu)成第rank級前沿非支配集合Frank。

3）重復(fù)步驟2），將種群的個(gè)體依次進(jìn)行分級，直到所有的個(gè)體都?xì)w入相應(yīng)的等級集合中。

（2）計(jì)算擁擠度

擁擠度描述的是處于同一非支配級的所有個(gè)體與其周圍其他個(gè)體之間的密集程度，NSGA-Ⅱ算法根據(jù)個(gè)體的擁擠度，淘汰擁擠度較小的個(gè)體，保留擁擠度較大的個(gè)體，從而保證解的多樣性。擁擠度的計(jì)算主要是對每個(gè)適應(yīng)度函數(shù)，對所有的同級個(gè)體按照在該適應(yīng)度函數(shù)下的函數(shù)值進(jìn)行排序，并計(jì)算個(gè)體與前后個(gè)體的擁擠距離，處于序列兩端的個(gè)體，由于其前（后）沒有個(gè)體存在，將其擁擠距離設(shè)為正無窮大，最后將個(gè)體在所有適應(yīng)度函數(shù)條件下得到的擁擠距離相加，得到個(gè)體的擁擠度［13］。具體表示如下：

個(gè)體xi∈Frank在某個(gè)適應(yīng)度函數(shù)fv∈F下的擁擠距離為

式中：k為Frank中個(gè)體的總數(shù)量；V為適應(yīng)度函數(shù)的個(gè)數(shù)；Iv（i-1）和Iv（i+1）分別為按第v個(gè)適應(yīng)度函數(shù)對解排序后，位于xi前后的解和分別為所有當(dāng)前解對應(yīng)的適應(yīng)度函數(shù)fv的最大值和最小值。

2.6 選擇策略

選擇策略的目標(biāo)是使種群進(jìn)化朝著非劣解和均勻分布的方向進(jìn)行，選擇的主要依據(jù)為個(gè)體的非支配等級以及擁擠度。

借鑒二元聯(lián)賽選擇機(jī)制的思想，首先設(shè)置選擇容量popSize′并初始化集合P′t=?，選擇規(guī)則為：在父代種群Pt中，隨機(jī)選擇兩個(gè)不同的個(gè)體xi，xj：

（1）若rank（xi）＞rank（xj），則Pt′←Pt′∪｛xj｝；

（2）若rank（xi）＜rank（xj），則Pt′←Pt′∪｛xi｝；

（3）若rank（xi）=rank（xj），則比較兩個(gè)個(gè)體的擁擠度，更 新Pt′←Pt′∪｛x′｝，其中，x′=xi，Distance（xi）＞Distance（xj）或x′=xj，Distance（xj）＞Distance（xi）。

如此反復(fù)地從父代種群Pt中選擇成對的個(gè)體并作出選擇，直到集合Pt′內(nèi)的個(gè)體數(shù)量達(dá)到pop-Size′，即｜Pt′｜=popSize＇。最終得到的集合Pt′即是下一步進(jìn)行遺傳操作的集合。

2.7 遺傳算子

遺傳操作是NSGA-Ⅱ?qū)崿F(xiàn)種群進(jìn)化的關(guān)鍵步驟，其效果的好壞依賴于交叉和變異兩種算子的設(shè)計(jì)和選擇。為了取得較好的問題求解效果，本節(jié)將結(jié)合問題的求解特征對交叉算子和變異算子進(jìn)行詳細(xì)設(shè)計(jì)。

（1）交叉算子

交叉算子作為個(gè)體進(jìn)化的一種方式，對個(gè)體的進(jìn)化起著主要作用，決定遺傳操作的全局搜索能力，是決定算法收斂性能的關(guān)鍵。考慮到算法的編碼方式是自然順序排列的批量號，采用基本的交叉方法可能會(huì)導(dǎo)致基因重復(fù)或丟失，并且交叉中的基因相對位置的改變對新個(gè)體的可行性具有一定的影響。為了達(dá)到較好的交叉效果，本文借鑒文獻(xiàn)［14］中的線性序號交叉法（Linear Order Crossover，LOX）和C1兩種交叉方法。采用概率選擇的方式交互使用兩種方法，即通過預(yù)先設(shè)置交叉選擇概率pc∈（0，1），比較隨機(jī)生成的數(shù)值rc∈（0，1）與pc的大小，通過比較結(jié)果選擇兩種方法中的一種進(jìn)行交叉操作。

（2）變異算子

變異算子是種群進(jìn)化的另一種操作方式，主要用來保持種群多樣性。對待變異的個(gè)體，本文采用常用的交換方式：隨機(jī)選擇兩個(gè)位置的基因進(jìn)行位置互換，形成的新的基因序列構(gòu)成新的個(gè)體。預(yù)先設(shè)置變異概率pm∈（0，1）和循環(huán)整數(shù)參數(shù)T，對種群中的每個(gè)個(gè)體，根據(jù)隨機(jī)生成的數(shù)值rm∈（0，1）與pm的大小對比結(jié)果決定是否變異，對于決定進(jìn)行變異操作的個(gè)體，隨機(jī)選擇基因序列中的兩個(gè)基因交換位置，并循環(huán)T次，得到新個(gè)體。

2.8 基于有限搜索范圍的鄰域搜索

鄰域搜索是為了從當(dāng)前解的鄰域中找出更好的解，避免算法陷入局部最優(yōu)。對于調(diào)度問題，通常用于鄰域搜索的方法有插入和交換兩種，并且插入是比交換更為有效的方法。在算法進(jìn)行鄰域搜索前，首先設(shè)置一個(gè)搜索決策概率ps∈（0，1），對于種群中的每個(gè)個(gè)體，通過比較隨機(jī)數(shù)值rs∈（0，1）與ps的大小決定是否進(jìn)行鄰域搜索，若rs＜ps，則進(jìn)行鄰域搜索，否則，進(jìn)入下一步計(jì)算。由于個(gè)體中某個(gè)被選擇的基因可選擇插入的位置較多，尤其對于基因序列較長的個(gè)體，若鄰域搜索考慮的是全部的可插入位置，則會(huì)產(chǎn)生較長的搜索時(shí)間，不利于提高算法的搜索效率。

本文通過改進(jìn)基本的插入方法，有限制地選擇插入位置，即對某個(gè)基因，通過設(shè)定搜索長度參數(shù)α，選擇部分位置做插入操作，以減少搜索時(shí)間。同時(shí)，為了節(jié)約計(jì)算時(shí)間，在進(jìn)行鄰域搜索時(shí)，若找到一個(gè)比原解更優(yōu)秀（非支配）的新解，則停止搜索，用新解代替原解。

對待進(jìn)行鄰域搜索的個(gè)體x=｛x1，x2，…，xk｝，算法及具體操作如下：

算法2 鄰域搜索算法。

步驟1 設(shè)置搜索長度參數(shù)α。

步驟2 令i從1～k變化，選擇位置為i的基因xi，將其移出基因序列，確定xi可插入的位置集合S=｛i-1，i-2，…，max（i-α，1），i+1，i+2，…，min（i+α，k）｝。

步驟3 令j從1到min（α，i-1）+max（α，ki）變化，選擇插入位置S（j），將xi插入到位置S（j），形成臨時(shí)解xj。

步驟4 根據(jù)式（13）～式（15）計(jì)算xj的適應(yīng)度函數(shù)值，并確定與x的支配關(guān)系，若x受xj支配，則選擇xj替代原解x，x←xj，并停止搜索，執(zhí)行步驟6，否則，令j←j+1，執(zhí)行步驟3，若j=min（α，i-1）+max（α，k-i）仍不能更新x，則執(zhí)行步驟5。

步驟5 令i←i+1，執(zhí)行步驟2，直到i=k，執(zhí)行步驟6。

步驟6 輸出x，算法結(jié)束。

2.9 精英策略

精英策略是在父代種群和子代種群中選擇優(yōu)秀的個(gè)體，是算法收斂的條件，其具體方法為：

步驟1 將父代種群Pt與經(jīng)過選擇操作、遺傳操作以及鄰域搜索后形成的子代種群Qt進(jìn)行合并，得到混合種群Rt，即Rt=Pt∪Qt，且Size+popSize′。

步驟2 對所有的x∈Rt進(jìn)行非支配排序確定非支配等級Rank（x）并計(jì)算擁擠度Distance（x），根據(jù)非支配等級和擁擠度大小排定個(gè)體間的優(yōu)劣順序。采用的排序規(guī)則具體如下：對?xi，xj∈Rt，其優(yōu)先級o（xi），o（xj）的大小關(guān)系為：

（1）若Rank（xi）＜Rank（xj）或Rank（xi）=Rank（xj）∧Distance（xi）＞Distance（xj），則o（xi）＞o（xj）；

（2）若Rank（xi）＞Rank（xj）或Rank（xi）=Rank（xj）∧Distance（xi）＜Distance（xj），則o（xi）＜o(jì)（xj）。

步驟3 選擇序列的前popSize個(gè)個(gè)體構(gòu)成精英集，將精英集作為下一次算法迭代的父代種群Pt+1。

2.10 MNSGA-Ⅱ算法的計(jì)算步驟

步驟1 種群初始化。

步驟1.1 令種群進(jìn)化代數(shù)為t=0，種群規(guī)模為popSize，最大迭代次數(shù)為Iter，子群規(guī)模為pop-Size′，交叉選擇概率為pc，變異選擇概率為pm，變異整數(shù)參數(shù)為T，鄰域搜索決策概率為ps，搜索長度參數(shù)為α；

步驟1.2 采用MNEH 算法（算法1）產(chǎn)生初始父代種群Pt=｛x1，x2，…，xpopSize｝。

步驟2 種群修復(fù)。

步驟2.1 選擇種群Pt中重復(fù)的個(gè)體，根據(jù)重復(fù)個(gè)體的修復(fù)規(guī)則（規(guī)則1）進(jìn)行修復(fù)。

步驟2.2 采用目標(biāo)函數(shù)計(jì)算方法，根據(jù)式（13）～式（15）計(jì)算種群Pt中每個(gè)個(gè)體的適應(yīng)度函數(shù)值，并對不可行個(gè)體進(jìn)行修復(fù)（規(guī)則2）。

步驟3 非支配排序并計(jì)算擁擠度。

步驟3.1 非支配排序，對種群Pt的所有個(gè)體進(jìn)行非支配分級，為每個(gè)個(gè)體賦予非支配等級，等級為i的所有個(gè)體構(gòu)成前沿非支配集合Fi，所有的Fi形成總非支配集F′=｛F1，F(xiàn)2，…，F(xiàn)r｝；

步驟3.2 對每個(gè)Fi∈F′，根據(jù)式（16）和式（17）計(jì)算每個(gè)x′∈Fi的擁擠度Distance（x′）。

步驟4 遺傳操作。

步驟4.1 根據(jù)選擇策略選擇popSize′個(gè)個(gè)體構(gòu)成待進(jìn)化的臨時(shí)種群Pt′。

步驟4.2 對Pt′中的個(gè)體進(jìn)行交叉操作，對待交叉的個(gè)體x，x′∈Pt′，將隨機(jī)數(shù)值rc∈（0，1）與pc對比，若rc≤pc，則選擇交叉方式LOX，否則選擇交叉方式C1。

步驟4.3 對Pt′中的個(gè)體進(jìn)行變異操作，對個(gè)體x∈Pt′，將隨機(jī)數(shù)值rm∈（0，1）與pm對比，若rm≤pm，則對x進(jìn)行變異操作，否則，不進(jìn)行變異操作。

步驟4.4 種群Pt′經(jīng)過交叉和變異兩種遺傳操作，進(jìn)化形成新的子代種群Qt。

步驟5 選擇精英集。

步驟5.1 對每個(gè)x∈Qt，通過隨機(jī)產(chǎn)生的數(shù)值rs∈（0，1）與ps的對比結(jié)果決策是否進(jìn)行鄰域搜索，對需要進(jìn)行鄰域搜索的個(gè)體x，采用基于有限搜索范圍的鄰域搜索算法（算法2）進(jìn)行鄰域搜索，更新子代種群Qt。

步驟5.2 根據(jù)精英策略構(gòu)造新的父代種群Pt+1，并更新Pt←Pt+1。

步驟6 判斷終止條件。

步驟6.1 令t=t+1，若t＞Iter，則執(zhí)行步驟6.2，否則返回執(zhí)行步驟2。

步驟6.2 輸出種群Pt中的非支配解，算法結(jié)束。

3 數(shù)據(jù)實(shí)驗(yàn)

本文采用Microsoft Visual C＃實(shí)現(xiàn)算法，實(shí)驗(yàn)環(huán)境為Pentium4.1／2.90GHz／2.00GB／Windows 7。根據(jù)已有數(shù)據(jù)的多次試驗(yàn)，發(fā)現(xiàn)MNSGA-Ⅱ算法參數(shù)如下設(shè)置在多數(shù)情況下具有更好的求解效果：種群大小popSize=200；選擇進(jìn)行遺傳操作的子種群大小popSize′=20；交叉選擇概率pc=0.6；變異概率pm=0.06；變異整數(shù)參數(shù)T=10；鄰域搜索決策概率ps=0.5，搜索長度參數(shù)根據(jù)批量數(shù)計(jì)算得到，記為α=1／5k（k為批量數(shù)量）；最大迭代次數(shù)100，每輪迭代均獨(dú)立運(yùn)行10 次，仿真結(jié)果取所有迭代的平均值。

本文實(shí)驗(yàn)分為兩部分：①通過對實(shí)際的生產(chǎn)數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，驗(yàn)證算法解決實(shí)際問題的能力；②根據(jù)實(shí)際生產(chǎn)的數(shù)據(jù)范圍，采用人工方式產(chǎn)生不同規(guī)模數(shù)據(jù)，檢驗(yàn)算法的求解質(zhì)量，為了驗(yàn)證算法的有效性，將其與MNEH 和基本的NSGA-Ⅱ算法進(jìn)行比較，其中NSGA-Ⅱ算法的初始解通過隨機(jī)方式產(chǎn)生，其他步驟與MNSGA-Ⅱ相同。

3.1 第一組實(shí)驗(yàn)

以國內(nèi)某特鋼企業(yè)在某計(jì)劃期間內(nèi)的237個(gè)訂單經(jīng)過組批后形成的108個(gè)軋制批為基本數(shù)據(jù)源，并將批量信息及生產(chǎn)數(shù)據(jù)整理成模型參數(shù)，包括產(chǎn)品規(guī)格、鋼種和每個(gè)規(guī)格對應(yīng)的機(jī)架類型和數(shù)量、鋼種的優(yōu)先級，機(jī)器檢修維護(hù)時(shí)間以及機(jī)器調(diào)整的單位時(shí)間（其中tu=10min，td=5min，tr=20min）。分別采用MNSGA-Ⅱ算法、NSGA-Ⅱ算法和MNEH 對實(shí)例模型進(jìn)行測試。實(shí)驗(yàn)結(jié)果如表1和圖2所示，其中：表1中的結(jié)果數(shù)據(jù)取每個(gè)算法的所有非支配解的平均值，圖2給出了兩算法迭代100次后得到的20個(gè)染色體（非支配解）對應(yīng)的三種目標(biāo)函數(shù)值對比曲線。

由以上實(shí)驗(yàn)結(jié)果可以得到以下結(jié)論：

（1）由表1可以看出，在對實(shí)際問題的求解中，MNSGA-Ⅱ算法在求解質(zhì)量上優(yōu)于MNEH 算法，這是由于MNSGA-Ⅱ算法以MNEH 得到的解作為初始值再進(jìn)一步優(yōu)化，從而對各個(gè)目標(biāo)函數(shù)值均有不同程度的改善；另外，雖然MNSGA-Ⅱ算法在計(jì)算時(shí)間上略多于MNEH 算法，但計(jì)算時(shí)間在允許范圍內(nèi)，符合實(shí)際需求。

表1 第一組實(shí)驗(yàn)——MNEH 與MNSGA-Ⅱ?qū)Ρ冉Y(jié)果

（2）圖2 是MNSGA-Ⅱ與NSGA-Ⅱ求得的非支配解對應(yīng)的目標(biāo)函數(shù)值，從圖中可以看出，MNS-GA-Ⅱ算法得到的非支配解質(zhì)量明顯優(yōu)于NSGA-Ⅱ算法，MNSGA-Ⅱ和NSGA-Ⅱ僅在初始解的構(gòu)造策略上不同，因此，通過對比可以看出，基于MNEH算法的初始解構(gòu)造機(jī)制對問題的求解能夠起到較好的作用。

3.2 第二組實(shí)驗(yàn)

該組實(shí)驗(yàn)中，根據(jù)鋼鐵企業(yè)實(shí)際生產(chǎn)的相關(guān)數(shù)據(jù)，通過隨機(jī)的方式生成批量及訂單的各項(xiàng)屬性值，包括訂貨量、交貨期、規(guī)格和鋼種等，其中規(guī)格和鋼種在企業(yè)所能生產(chǎn)的所有種類中隨機(jī)選擇。實(shí)驗(yàn)根據(jù)不同的批量數(shù)量分為5組，每組生成10個(gè)算例，對每個(gè)算例，其結(jié)果數(shù)據(jù)取每個(gè)算法所有非支配解的平均值，最終的計(jì)算結(jié)果取10個(gè)算例的平均值。

實(shí)驗(yàn)結(jié)果如表2 所示，其中time表示MNSGA-Ⅱ算法的計(jì)算時(shí)間。

由以上實(shí)驗(yàn)結(jié)果可以得到以下結(jié)論：

（1）針對不同規(guī)模的訂單量，MNSGA-Ⅱ算法得到的解的質(zhì)量都優(yōu)于MNEH 和NSGA-Ⅱ。一方面，MNSGA-Ⅱ是以MNEH 得到的解作為初始解進(jìn)行優(yōu)化，并且MNEH 采用隨機(jī)權(quán)重法將多目標(biāo)化解為單目標(biāo)進(jìn)行求解，權(quán)重取值的隨機(jī)性使得MNEH 的解不穩(wěn)定，MNSGA-Ⅱ能夠在此基礎(chǔ)上對解進(jìn)行優(yōu)化改善，得到更好的解；另一方面，MNEH 產(chǎn)生的初始解要比隨機(jī)生成的初始解具有更好的目標(biāo)適應(yīng)性，因此，MNSGA-Ⅱ能夠比NSGA-Ⅱ得到更優(yōu)秀的解。

表2 第二組實(shí)驗(yàn)計(jì)算結(jié)果

（2）隨著問題規(guī)模的不斷增大，種群個(gè)體的基因序列逐漸增長，MNSGA-Ⅱ算法所用的計(jì)算時(shí)間也逐漸增加，但對于訂單規(guī)模為250的問題，算法也能在6min內(nèi)得到較滿意的解，能夠滿足批量調(diào)度的實(shí)際應(yīng)用需求。

4 結(jié)束語

熱軋批量調(diào)度是鋼鐵企業(yè)生產(chǎn)管理中的關(guān)鍵問題，在理論和實(shí)踐中具有重要的研究意義，本文針對圓鋼的熱軋批量調(diào)度問題，考慮機(jī)器檢修計(jì)劃的約束，將問題歸結(jié)為帶有多種約束條件的具有順序依賴調(diào)整時(shí)間的flowshop調(diào)度問題，并在此基礎(chǔ)上建立了多目標(biāo)的整數(shù)規(guī)劃模型。通過分析問題的求解特點(diǎn)，提出了MNSGA-Ⅱ算法。首先，采用MNEH算法生成初始解，利用罰函數(shù)的思想設(shè)計(jì)適應(yīng)度函數(shù)并對重復(fù)個(gè)體和不可行個(gè)體進(jìn)行淘汰或修復(fù)；其次，在基本的NSGA-Ⅱ的基礎(chǔ)上，結(jié)合問題的特點(diǎn)，設(shè)計(jì)了遺傳操作方式以及基于有限搜索范圍的鄰域搜索算法，使得算法朝著最優(yōu)的方向進(jìn)化的同時(shí)避免陷入局部最優(yōu)。仿真實(shí)驗(yàn)表明，MNSGA-Ⅱ算法對圓鋼熱軋批量調(diào)度問題具有較好的求解效果，且計(jì)算效率滿足實(shí)際應(yīng)用的需求。

［1］LI Tieke，GUO Dongfen.Model and algorithm for hot-rolling batch plan on constraint satisfaction［J］.Control and Decision，2007，22（4）：389-393（in Chinese）.［李鐵克，郭冬芬.基于約束滿足的熱軋批量計(jì)劃模型與算法［J］.控制與決策，2007，22（4）：389-393.］

［2］ZHANG Wenxue，LI Tieke.Batch plan optimization of steel integrated production with multiple process［J］.Computer Integrated Manufacturing Systems，2013，19（6）：1296-1303（in Chinese）.［張文學(xué)，李鐵克.面向多種生產(chǎn)工藝的冶鑄軋一體化批量計(jì)劃優(yōu)化［J］.計(jì)算機(jī)集成制造系統(tǒng)，2013，19（6）：1296-1303.］

［3］PAN C C，YANG G K.A method of solving a large scale rolling batch scheduling problem in steel production using a variant of column generation［J］.Computers &Industrial Engineering，2009，56（1）：165-178.

［4］JIA S J，YI J，YANG G K，et al.A multi-objective optimization algorithm for the hot rolling batch scheduling problem［J］.International Journal of Production Research，2013，51（3）：667-681.

［5］TANG L X，HUANG L.Optimal and near-optimal algorithmsto rolling batch scheduling for seamless steel tube production［J］.International Journal of Production Economics，2007，105（2）：357-371.

［6］LI Lin，HOU Jiazhen.Multi-objective flexible job-shop scheduling problem in steel tubes production［J］.Systems Engineering—Theory &Practice，2009，29（8）：117-126（in Chinese）.［李 琳，霍佳震.鋼管生產(chǎn)計(jì)劃中的多目標(biāo)柔性Job-shop調(diào)度問題［J］.系統(tǒng)工程理論與實(shí)踐，2009，29（8）：117-126.］

［7］SHI C T，YANG G J，LI T K.An evolutionary neighborhood search algorithm for flexible job-shop scheduling problem in steel tube production［J］.Advanced Materials Research，2012，566：620-627.

［8］ASAD R，DEMIRLI K.Production scheduling in steel rolling mills with demand substitution：Rolling horizon implementation and approximations［J］.International Journal of Production Economics，2010，126（2）：361-369.

［9］WANG Xin，YANG Chunhua，QIN Bin.Multi-objective hybrid optimization of lot scheduling for bar mill process［J］.Control and Decision，2006，21（9）：996-1000（in Chinese）.［王 欣，楊春華，秦 斌.棒線材軋制批量調(diào)度多目標(biāo)混合優(yōu)化［J］.控制與決策，2006，21（9）：996-1000.］

［10］DEB K，PRATAP A，AGARWAL S，et al.A fast and elitist multiobjective genetic algorithm：NSGA-Ⅱ［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：180-197.

［11］ISHIBUCHI H，MURATA T.A multi-objective genetic local search algorithm and its application to flowshopscheduling［J］.IEEE Transactions on System，Man，Cybernetics，1998，28（3）：392-403.

［12］LI Qian，GONG Jun，TANG Jiafu.Multi-objective optimal cross-training plan models using non-dominated sorting genetic algorithm-Ⅱ［J］.Journal of Northeastern University：Natural Science，2011，32（12）：1696-1699（in Chinese）.［李倩，宮 俊，唐加福.基于改進(jìn)NSGA-Ⅱ的交叉培訓(xùn)規(guī)劃多目標(biāo)優(yōu)化［J］.東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2011，32（12）：1696-1699.］

［13］WEI Tian，F(xiàn)AN Wenhui.Modified NSGAⅡalgorithm for vehicle routing problem in logistics［J］.Computer Integrated Manufacturing Systems，2008，14（4）：778-784（in Chinese）.［衛(wèi) 田，范文慧.基于NSGAⅡ的物流配送中車輛路徑問題研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2008，14（4）：778-784.］

［14］WANG L，ZHANG L，ZHENG D Z.An effective hybrid genetic algorithm for flow shop scheduling with limited buffers［J］.Computers &Operations Research，2006，33（10）：2960-2971.