基于仿真優(yōu)化的加熱爐—熱軋區(qū)間重調(diào)度

潘瑞林，胡邦國，曹建華，劉德樓

（1．安徽工業(yè)大學 管理科學與工程學院，安徽 馬鞍山 243032；2．山東鋼鐵集團有限公司，山東 濟南 250132）

0 引言

加熱爐—熱軋過程是鋼鐵企業(yè)一體化生產(chǎn)中的重要組成部分，也是實現(xiàn)連續(xù)生產(chǎn)不可缺少的關鍵環(huán)節(jié)。鋼鐵企業(yè)生產(chǎn)過程具有復雜性和不確定性，其調(diào)度結(jié)果會直接影響合同交貨期、成本和生產(chǎn)的連續(xù)性等［1－3］。因此，加熱爐和熱軋機的調(diào)度優(yōu)化一直受到眾多專家和學者的關注。目前的研究主要集中在加熱爐和熱軋調(diào)度優(yōu)化兩個方面。在加熱爐調(diào)度方面主要有：寧樹實等認為加熱爐調(diào)度問題屬于NP－h(huán)ard問題，對此建立了加熱爐調(diào)度問題的數(shù)學模型［4］；孫學剛等提出了基于免疫文化算法的加熱爐優(yōu)化調(diào)度方法，利用免疫克隆算法的全局收斂性對最優(yōu)調(diào)度方案進行搜索，利用文化算法形成的公共認知信念指導和加速搜索［5］；梁合蘭等建立了連鑄—熱軋混裝一體化模式下的加熱爐生產(chǎn)調(diào)度優(yōu)化模型，并提出了基于貪婪算法和模擬退火算法的兩階段求解方法［6］；在熱軋調(diào)度優(yōu)化方面主要有：陳愛玲根據(jù)熱軋生產(chǎn)模式和軋制計劃的結(jié)構(gòu)特點，采用車輛路徑問題（Vehicle Routing Problem，VRP）模型建立了軋制調(diào)度模型，提出一種混合調(diào)度方法，即模擬退火和修正粒子群優(yōu)化算法（Simulated Annealing and Modified Particle Swarm Optimization，SAMPSO）［7］；高慧敏等在分析熱軋帶鋼生產(chǎn)調(diào)度特征的基礎上給出了數(shù)學規(guī)劃模型，并提出一種基于并行策略的混合啟發(fā)式算法［8］；唐立新等在分析軋批排序問題特征的基礎上，建立了軋批最優(yōu)排序的旅行商模型，為軋鋼生產(chǎn)計劃問題提供了一個科學的方法［9］。Shigui提出用多旅行商問題模型（Multiple Traveling Salesman Problem，MTSP）來解決軋制計劃的編制問題，但沒有考慮軋制計劃的能力約束［10］；楊業(yè)建等根據(jù)加熱爐區(qū)的生產(chǎn)特點分別建立了以生產(chǎn)能耗最小化和加熱質(zhì)量最優(yōu)化為主次目標的鋼坯加熱爐區(qū)調(diào)度數(shù)學模型［11］。以上研究只是單方面考慮加熱爐調(diào)度和熱軋調(diào)度，沒有整體考慮加熱爐和熱軋區(qū)間的生產(chǎn)過程，所建立的模型缺乏系統(tǒng)性和連續(xù)性。

加熱爐—熱軋生產(chǎn)過程是一種多設備、多工序和多約束的復雜系統(tǒng)，對應的是一個多維、非線性、動態(tài)開放的復雜問題，因此伴隨著大量的不確定因素和撓動問題。利用傳統(tǒng)的優(yōu)化算法求解時，需要以大量的假設為前提，另外對應的數(shù)學模型難以建立或轉(zhuǎn)化，因此得出的作業(yè)計劃很難用于實踐。本文基于上述文獻，以加熱爐和熱軋區(qū)間為研究對象，改變了傳統(tǒng)的只從單方面考慮加熱爐調(diào)度和熱軋調(diào)度的建模方式。以實現(xiàn)鋼鐵企業(yè)生產(chǎn)過程的連續(xù)性、生產(chǎn)成本最小化等為優(yōu)化目標，并且考慮加熱爐的容量、熱軋機的軋制能力和生產(chǎn)過程的工藝等多種約束，建立了加熱爐—熱軋區(qū)間生產(chǎn)調(diào)度模型。針對實際生產(chǎn)過程中出現(xiàn)的隨機事件干擾或由于設備沖突等情況，對三種重排策略進行比較，建立了基于局部重調(diào)度的加熱爐—熱軋區(qū)間數(shù)學模型。采用非支配排序遺傳算法（Nondominated Sorting Genetic AlgorithmⅡ，NSGA－Ⅱ）對建立的兩種模型進行求解，利用加熱爐開始加熱時間和熱軋機開始軋制時間的分布概率進行變異操作。最后運用實際生產(chǎn)數(shù)據(jù)進行了仿真驗證。

1 加熱爐—熱軋區(qū)間生產(chǎn)調(diào)度問題描述

加熱爐—熱軋區(qū)間生產(chǎn)調(diào)度是在保證連續(xù)軋制的前提下，根據(jù)訂單的鋼種、規(guī)格和交貨期等條件將坯料進行組批，以軋次為最小計劃單位，在追求某一評價函數(shù)（如合同提前/拖期費用、最小完工時間或最小等待時間）情況下的一類多坯料、多工序、多機器的混合Flow Shop調(diào)度問題。當生產(chǎn)過程受到隨機事件干擾或因設備沖突而不能按原計劃執(zhí)行時，及時調(diào)整設備和生產(chǎn)時間，保證生產(chǎn)的連續(xù)性，從而實現(xiàn)資源和時間的平衡。其最終結(jié)果是確定在何時、何種設備上以何種順序安排坯料從加熱爐到熱軋機的生產(chǎn)過程。

1．1 加熱爐—熱軋區(qū)間生產(chǎn)工藝簡介

加熱爐—熱軋區(qū)間生產(chǎn)過程位于鋼鐵企業(yè)一體化生產(chǎn)過程的后段，其生產(chǎn)工藝過程如圖1中的虛線矩形框所示，坯料按照軋制順序依次向各個加熱爐分配坯料，以保證加熱爐持續(xù)向熱軋機提供坯料。

為了突出主題，本文只考慮兩類主體生產(chǎn)設備即加熱爐和熱軋機，但安排作業(yè)時間表時要考慮坯料的轉(zhuǎn)換時間。軋次在熱軋機上的作業(yè)順序和坯料在加熱爐中的額定加熱時間已知，需要為坯料組批并在加熱工序上為其選擇加熱爐爐號，并確定坯料在各設備上處理的開始時間和結(jié)束時間。熱軋機對所要加工的坯料一般要求溫度達到1 200℃以上，坯料不能在加熱爐停留過長，也不宜在加熱爐外停留過長?，F(xiàn)代鋼鐵企業(yè)的加熱爐設備一般采用連續(xù)步進式加熱爐，其能耗約占噸鋼能耗的一半，因此在追求合同交貨懲罰費用最小、坯料住爐時間最短和工序間等待時間最小的目標下，考慮到坯料經(jīng)過的工序不變、機器無沖突和連續(xù)軋制等約束，實現(xiàn)企業(yè)的連續(xù)生產(chǎn)和成本優(yōu)化。

1．2 符號定義

以坯料為最小單位，設i表示坯料序號；η表示全部坯料集合，η＝｛i＝1，2，…，I｝；j表示加熱爐序號；γ表示全部加熱爐集合，γ＝｛j＝1，2，…，J｝；k表示熱軋機序號；δ表示全部熱軋機集合，δ＝｛k＝1，2，…，K｝。設xij表示坯料i在加熱爐j上的開始加工時間；xi′j表示坯料i的緊后坯料i′在加熱爐j上的開始加工時間；xik表示坯料i在熱軋機k上的開始加工時間；xi′k表示坯料i的緊后坯料i′在熱軋機k上的開始加工時間。因為坯料在加熱爐和熱軋機上的加工時間具有不確定性，所以采用ti表示坯料i在加工設備上的預期加工時間；pij表示坯料i是否在加熱爐j中加熱；qik表示坯料i是否在熱軋機k上軋制；di表示合同的交貨期；cijk表示坯料i是否要從加工設備j轉(zhuǎn)換到加工設備k；αi表示提前單位懲罰費用；βi表示拖期單位懲罰費用，一般βi＞αi；tstep表示坯料i在加熱爐j中的步進時間；Tijk表示工序間的轉(zhuǎn)換時間；Hi表示坯料i的重量；Vj表示加熱爐j的最大容量；Mtk表示熱軋機k在t段時間內(nèi)的軋制坯料總重量。

1．3 加熱爐—熱軋區(qū)間生產(chǎn)調(diào)度數(shù)學模型

為便于問題描述，給出如下基本假設：

假設1 軋次計劃（包括各個坯料在熱軋機上的軋制順序）已知且不可變。

假設2 各工位的最早可用時間已知。

隨著準時制思想的發(fā)展，企業(yè)管理者越來越關注如何制定在交貨期窗口下的提前/拖期生產(chǎn)計劃［12］。Cheng認為，只要任務完工時間不在交貨期窗口內(nèi)，就必然引起提前/拖期懲罰［13］。為了得到較好的加熱爐—熱軋區(qū)間生產(chǎn)調(diào)度方案，目標函數(shù)還應包括以下幾點：

（1）加熱爐內(nèi)冷熱坯料混裝次數(shù)最小化，降低加熱爐能耗，提高坯料加熱質(zhì)量。

（2）坯料在加熱爐中加熱時，盡量不要超過坯料的額定加熱時間。

（3）坯料在加熱爐中嚴格按照先進先出規(guī)則，減少軋機等待時間，提高軋機利用率。

基于文獻［4，14－15］，為了降低合同提前和拖期懲罰費用、減少坯料在加熱爐中的停留時間和工序間的等待時間，綜合考慮加熱爐的額定加熱時間和容量、坯料的工藝約束、熱軋機產(chǎn)能等約束條件，建立如下加熱爐—熱軋區(qū)間生產(chǎn)調(diào)度數(shù)學模型：

其中：式（1）表示最小化板坯在熱軋機上軋制結(jié)束時的提前和拖期懲罰費用；式（2）表示所有待加熱坯料達到軋制溫度后在加熱爐（熱軋機）中的停留時間最??；式（3）表示保證坯料在設備上的停留時間最小，即保證生產(chǎn)的連續(xù)性；式（4）表示同一爐兩相鄰坯料的進爐時間滿足加熱爐的步進時間間隔；式（5）表示前一塊坯料加工完后再加工后一塊坯料；式（6）表示前一工序完成后才能進入下一工序；式（7）表示保證坯料的實際加工時間不得少于坯料的額定加工時間；式（8）表示熱軋總量不能超過熱軋機的軋制能力；式（9）表示加熱爐容量約束；式（10）表示開始加工時間必須大于等于零；式（11）表示保證每塊坯料都被分配且只能被分配到一個加熱爐中進行加熱；式（12）表示保證每塊坯料都被分配且只能被分配到一個熱軋機上進行加工；式（13）～式（15）表示0－1變量。

1．4 加熱爐—熱軋區(qū)間的重調(diào)度

加熱爐—熱軋區(qū)間生產(chǎn)調(diào)度有時會在某些設備上出現(xiàn)資源占用，導致相鄰工序之間的工作時間沖突。重調(diào)度是指當生產(chǎn)過程受到隨機事件干擾或因設備沖突而不能按原計劃執(zhí)行時，及時調(diào)整設備和生產(chǎn)時間。

在鋼鐵企業(yè)生產(chǎn)中經(jīng)常出現(xiàn)加熱爐出坯延遲情況，延遲的時間不同，對后續(xù)生產(chǎn)的影響也不同。加熱爐—熱軋過程是一個連續(xù)化的過程，如果不能及時有效地解決坯料出爐延遲問題，將有可能造成熱軋機等待時間過長、設備沖突等問題，從而降低軋機利用率，增加加熱爐的能耗。

設加熱爐群三個軋次分別是A、B和C，圖2所示為正常情況下的靜態(tài)甘特圖。

設熱軋機通過降低軋制速度延長的軋制時間為tbuffter，軋次B的出爐延遲時間為ttar。

（1）當ttar≤tbuffter時，軋次A 的加熱時間延長ttar，軋次B、C的開始處理時間和開始加熱時間延遲ttar，圖3所示為ttar≤tbuffter時重調(diào)度后的甘特圖。

（2）當ttar≥tbuffter時，若通過降低軋機的軋制速度不能緩沖坯料出爐延遲時間，則熱軋機不能實現(xiàn)連軋。此時需要對軋次B的后續(xù)軋次時間表進行重排，重排策略有以下三種［16－18］：①右移法，即推遲軋次B后續(xù)軋次的開始處理時間。該方法簡易，便于計算機實現(xiàn)，但是不能保證設備無沖突，調(diào)整后的結(jié)果不是最優(yōu)。②全局重調(diào)度法，利用數(shù)學模型對已經(jīng)軋制和未軋制軋次進行重調(diào)度，再根據(jù)已軋制軋次的時間確定未軋制的軋次開始處理時間。該方法追求的是全局最優(yōu)化，能夠保證設備無沖突，但處理時間長、不切實際。③局部重調(diào)度法，利用數(shù)學模型對軋次B的后續(xù)軋次進行局部重調(diào)度。該方法的處理速度快，而且能夠保證設備無沖突，貼近實際生產(chǎn)需要。通過對這三種重排策略對應的魯棒性進行驗證，對于解決設備無沖突問題和局部重調(diào)度策略具有更好的魯棒性。因此，本文借鑒文獻［15，19］，建立了局部重調(diào)度的數(shù)學模型。

優(yōu)化目標：

工藝約束：

式中：C1表示加熱爐k的故障單位懲罰費用，C2表示熱軋機k的故障單位懲罰費用；C3表示坯料在加工設備k上等待時間的單位懲罰費用。式（16）表示加熱爐故障時的懲罰費用、熱軋機故障時的懲罰費用和加工設備間等待時間懲罰費用總和最小；式（17）表示坯料進入加熱爐時的步進時間間隔約束；式（18）表示同一加工設備上相鄰的兩坯料要等前一坯料處理完成后才能處理下一坯料；式（19）表示同一坯料要等加熱爐加熱完成后才能進入熱軋機的軋制處理。

2 基于仿真的優(yōu)化算法

基于仿真的優(yōu)化算法（Simulation Based Optimization，SBO）的基本思想是：上層采用優(yōu)化器對問題進行求解，下層采用仿真器對優(yōu)化解進行評價，并將評價結(jié)果反饋給優(yōu)化器指導優(yōu)化，其邏輯結(jié)構(gòu)如圖4所示［19－20］。

本文采用基于仿真的NSGA－Ⅱ的最大特點在于解的評價方法。一般的遺傳算法可以通過遺傳編碼表示解析函數(shù)或者通過一段代碼得到目標函數(shù)值，然而基于仿真的NSGA－Ⅱ需要根據(jù)統(tǒng)計信息對染色體進行評價，而且在評價過程中涉及到許多不確定因素，從而增加了仿真次數(shù)。另外，一般的遺傳算法在求解生產(chǎn)調(diào)度問題時，需要將各工序上各工位加工的開始時間和結(jié)束時間等全部信息都包含在染色體上，因此編寫染色體時比較復雜。然而，本文基于仿真的NSGA－Ⅱ染色體上包含了加工時間的全部信息，這樣不但便于算法的遺傳操作，而且有利于處理仿真過程中的不確定性因素，從而使仿真結(jié)果更貼近生產(chǎn)實踐。

本文中的仿真器與其他仿真器有所不同，它不僅包括計算機系統(tǒng)的運行，還包括現(xiàn)場調(diào)度人員的活動，例如坯料額定加工時間的確定等，這種方法更適合復雜系統(tǒng)的運行。

2．1 優(yōu)化器設計

遺傳算法是常見的基于仿真的優(yōu)化算法之一，在生產(chǎn)調(diào)度問題中應用非常廣泛，驗證了其在生產(chǎn)調(diào)度問題中的有效性。本文采用NSGA－Ⅱ解決多目標優(yōu)化中每個目標的重要性不同、單位不同等問題。NSGA－Ⅱ采用Pareto排序策略［21］，基本思路是：當前群體是非支配個體時，全部非支配個體組成的集合為第一級非支配個體，其Pareto排序值為1；去除第一級非支配個體集中的全部個體，新產(chǎn)生的非支配個體Pareto排序值為2，組成的集合為第二級非支配個體集。依次類推，直到所有個體的Pareto排序值確定為止。算法的每一步迭代過程都會產(chǎn)生與初始種群規(guī)模大小相同的新種群，種群都會經(jīng)過選擇、交叉、變異、產(chǎn)生新種群、父子種群合并、計算序值和擁擠距離、非支配排序、計算擁擠距離和修剪種群等操作。NSGA－Ⅱ算法的基本流程如圖5所示。

2．2 Pareto最優(yōu)解

多目標優(yōu)化問題的最優(yōu)解是一個集合，而不是一個全局最優(yōu)解［21］。多目標優(yōu)化就是在目標函數(shù)可接受的范圍內(nèi)找到滿足各個約束條件限制的解。當沒有其他解比現(xiàn)有解更好時，則現(xiàn)有解即達到了Pareto最優(yōu)。下面介紹Pareto最優(yōu)解的相關概念。

（1）Pareto優(yōu)勢

當且僅當絕大部分向量a＞b，則向量a＝（a1，…，an）被向量b＝（b1，…，bk）所支配，?i∈｛1，…，k｝，ai≤bi∧?i∈｛1，…，k｝：ai≤bi。

（2）Pareto最優(yōu)集合

假如F（x）是一個多目標函數(shù)，則（P＊）就是Pareto最優(yōu)集合，即p＊＝｛x∈Ω｜?x′∈Ω，F(xiàn)（x′）≤F（x）｝。

（3）Pareto最優(yōu)

假如一個解屬于某個解集空間，即x∈Ω，則稱x是關于這個解集空間的最優(yōu)解。當且僅當向量b支配向量a，即當b＝F（x′）＝（f1（x′），…，fk（x′））支配a＝F（x）＝（f1（x），…，fk（x））時，則沒有解對應這個解集空間，即x′?Ω。

2．2．4 Pareto優(yōu)化前沿

假如F（x）是一個多目標函數(shù)，則P＊就是Pareto最優(yōu)解集合，則稱（PF＊）為Pareto優(yōu)化前沿，即PF＊＝｛a＝F（x）＝（f1（x），…，fk（x））｜x∈P＊｝。

2．3 非支配排序遺傳算法

NSGA－Ⅱ運算過程中的每一個體都通過非支配排序方法產(chǎn)生Pareto序列，并且利用擁擠距離分配方法完成密度評價。在兩個體進行適應值分配時，NSGA－Ⅱ提供了較低序列值的點，或當兩個點都屬于同一優(yōu)化前沿時，該點就會落在較少點的范圍內(nèi)。因此，在一些生產(chǎn)調(diào)度問題上NSGA－Ⅱ不同于原始的NSGA，它可以通過非支配快速排序方法產(chǎn)生一種更好的值分布算法［21］。2．3．1 個體編碼與初始解

染色體采用兩段、多層實數(shù)編碼形式［22－23］，由坯料的開始加熱時間和開始軋制時間組成，其數(shù)據(jù)結(jié)構(gòu)可表示如下：

Chromosome（FurnaceNo（1×N）

As Integer，MillNo（1×N）As Integer）

Furnace（1×N）As Real，Mill（1×N）As Real））。其中：N為坯料個數(shù)；FurnaceNo（1×N）表示通過隨機數(shù)為每個坯料指派的加熱爐爐號；MillNo（1×N）表示通過隨機數(shù)為每個坯料指派的熱軋機機器號；Furnace（1×N）表示坯料的開始加熱時間；Mill（1×N）表示坯料的開始軋制時間。

本文采用實數(shù)編碼方案，優(yōu)化問題則轉(zhuǎn)化為對編碼的實數(shù)取值問題，編碼采用決策變量的真實值，初始解表示坯料在加熱爐、熱軋機中的分配、開始加工時間和開始軋制時間，并對應初始條件（坯料的工藝路線和可用的機器）隨機生成初始解。如個體［3，1，2，4；1，1，1，1；0．1，0．3，0．2，0．4；190，194，195，193］，該個體表達了四組坯料被分配在四臺加熱爐中加熱并且在一臺熱軋機上軋制。其中：前四位1～4表示坯料的加熱爐爐號；5～8表示熱軋機機器號；9～12表示坯料的開始加熱時間；13～16表示坯料的開始軋制時間。2．3．2 適應值計算

因為適應度函數(shù)在算法中要進行比較排序，所以要求適應值取正值。因此，必須將目標函數(shù)轉(zhuǎn)化成非負形式，轉(zhuǎn)換方法為：

式中：f（x）為最小化目標函數(shù)，Cmax是一個足夠大的正數(shù)。

適應值的標定如下：

式中：f′為標定后的適應值；fmax為當代染色體中目標函數(shù)的最大值，f為仿真器返回的目標函數(shù)值，θ為預先給定的小常數(shù)。

2．3．3 選擇、交叉與變異算子

（1）選擇操作。選擇策略采用精英保留與正比選擇的混合策略，每一代種群中除最好的個體進入下一代外，最差的個體也進入下一代，其余個體按輪盤賭方式正比進行選擇［19］。比例選擇的概率

選擇過程充分遵循集中和擴散兩個策略。集中策略主要體現(xiàn)在局部搜索，即從某一個體出發(fā)，在其鄰域內(nèi)搜索以獲得更好的解，從而達到局部最優(yōu)解；擴散策略的目的是跳出局部最優(yōu)解。通過保留種群中的較差個體達到一些沒有搜索的點，從而實現(xiàn)更大區(qū)域的搜索。

（2）交叉操作。采用多點復合交叉操作。首先根據(jù)選擇概率pc選擇種群中的個體，然后選擇決策變量作為交叉點并對其進行實數(shù)交叉運算，最后對運算后的決策變量實行交換操作。復合交叉過程采用算術(shù)交叉的方法，如表1所示。算術(shù)交叉產(chǎn)生新個體c1，c2的方法為［24］：

式中：f1i表示父代個體1基因，f2i表示父代個體2基因，n1i表示子體個體1基因，n2i表示子代個體2基因。

表1 復合交叉過程

（3）變異操作。首先根據(jù)變異概率pm，從染色體的第一層代碼中隨機選取變異個體，然后選擇變異位置pos1和pos2，最后對換個體pos1和pos2位上對應的加熱爐號和軋機號。根據(jù)變異概率pm，從染色體的第二層代碼中隨機選取變異個體，最后根據(jù)染色體i中對應的加熱爐和熱軋機的最大開始時間λi的概率Pi，對變異位置pos3和pos4的變異元素qi進行變異操作，產(chǎn)生變異個體q′i。相應的過程為：

式中Pi～U（0，λi）表示坯料的開始加工時間服從區(qū)間（0，λi）上的均勻分布，其概率密度函數(shù)為：

變異操作能保證決策變量的可行性，如下所示，變異位置為2，4，9和14。

個體：［3，1，2，4；1，1，1，1；0．1，0．3，0．2，0．4；190，194，195，193］；

變異后新個體：［3，4，2，1；1，1，1，1；0．4，0．3，0．2，0．4；190，195，195，193］。

種群通過交叉、變異操作將獲得新的個體，從而推動整個種群的進化，體現(xiàn)了進化算法的核心思想。設計兩個算子時應滿足兩個基本條件：①產(chǎn)生的新個體（即新解）在定義域內(nèi)；②產(chǎn)生的新個體分布在整個定義域上。因此，經(jīng)過交叉、變異操作后產(chǎn)生的新個體，應該進行以上兩方面的校驗。

2．3．4 停止準則

采用給定種群的最大迭代次數(shù)（即種群的最大進化代數(shù)）為停止準則，可根據(jù)實際問題進行調(diào)整。

2．4 仿真器設計

為減少仿真過程中隨機因素的影響，可對染色體進行多次獨立仿真，取其平均值返回給優(yōu)化器。仿真器邏輯圖如圖6所示，具體步驟如下：

步驟1 根據(jù)各坯料在各加工設備上的額定加工時間和相鄰工位之間的轉(zhuǎn)換時間等信息，隨機給各個坯料指派加熱爐爐號，并生成各坯料的開始加熱時間和開始軋制時間。

步驟2 根據(jù)熱軋機的最早可用時間，選擇開始軋制時間最早的坯料進行軋制。

步驟3 對于已選定的軋次，沿工藝路線，逐一確定各坯料的加熱爐號和入爐時間，直至對應坯料的軋制結(jié)束時間為止。若某一工序有多個工位時，優(yōu)先選擇可用時間早的加工設備。

步驟4 更新各工序各加工設備的最早可用時間和已安排的軋次。

步驟5 若還有未安排的軋次，則轉(zhuǎn)步驟2；否則，轉(zhuǎn)步驟6。

步驟6 從熱軋機的最后一個軋次開始，沿逆工序順序調(diào)整各工序各加工設備的開始加工時間。對于給定的軋次，若某坯料開始軋制之前，其緊前坯料已經(jīng)軋制完畢，則推遲緊前坯料的開始軋制時間，避免斷軋。

步驟7 考慮時間的約束，調(diào)整各加工設備的開始加工時間，盡可能消除各工序各加工設備間的等待時間。

2．5 算法性能分析

實驗測評基于Lawrence提出的各種Benchmark問題［25］。P1～P3是10個工件和5臺機器問題；P4～P6是15個工件和5臺機器問題；P7～P9是20個工件和5臺機器問題；P10～P12是10個工件和10臺機器問題；P13～P15是15個工件和10臺機器問題；P16～P18是20個工件和10臺機器問題。

實驗參數(shù)如下：種群數(shù)為30；最大迭代次數(shù)為300；選擇概率為0．9交叉概率為0．8；變異概率為0．4；實驗環(huán)境為 MATLAB 7．11，NSGA－Ⅱ算法與基本遺傳算法（Simple Genetic Algorithms，SGA），性能比較結(jié)果如表2所示。

表2 兩種遺傳算法的尋優(yōu)結(jié)果比較

由表2可以看出NSGA－Ⅱ比SGA的尋優(yōu)能力更強，而且在 P4，P5，P7，P8，P12，P13，P15，P16的測試中完全找到了最優(yōu)解。

續(xù)表2

3 應用實例

3．1 實驗環(huán)境和數(shù)據(jù)

本文采用 MATLAB 7．11語言在PC Pentium4/CPU 2．5GHz/RAM2．0G 計算機上編程實現(xiàn)調(diào)度算法。假設種群大小為100，最大迭代次數(shù)為200，交叉概率為0．7，變異概率為0．05，適應值中預設小常數(shù)θ＝1，每個解的仿真次數(shù)為60。本文根據(jù)鋼鐵企業(yè)的生產(chǎn)實際，依托專家經(jīng)驗并借鑒已有文獻確定了加熱爐—熱軋區(qū)間生產(chǎn)調(diào)度數(shù)學模型中的懲罰參數(shù)，其中拖期懲罰費用αi＝0．7，提前懲罰費用βi＝0．3。在沖突解消模型中，加熱爐故障單位懲罰費用C1＝0．3，熱軋機單位故障懲罰費用C2＝0．2，坯料在工位上等待單位懲罰費用C3＝0．5。實驗數(shù)據(jù)根據(jù)國內(nèi)某大型鋼鐵企業(yè)的實際生產(chǎn)數(shù)據(jù)整理而來，如表3所示。該企業(yè)的加熱爐—熱軋生產(chǎn)系統(tǒng)中包括4臺加熱爐和1臺熱軋機，當日計劃中有20個批次。

表3 相關的生產(chǎn)實際數(shù)據(jù)

續(xù)表3

在NSGA－Ⅱ的運行過程中，自動繪制了第一前端中個體的分布情況，且分布隨著算法進化一代而更新一次，如圖7所示。算法終止時，Workspace中返回了Pareto解集x，如圖8所示。

同時，Workspace中返回了Pareto解集x對應的目標函數(shù)值，如圖9所示。圖中，函數(shù)值4×104，5×104和1×104分別表示目標函數(shù)1，2和3的滿意解。

根據(jù)Pareto解集x的值，得到如圖10所示的加熱爐—熱軋區(qū)間生產(chǎn)計劃安排情況。

圖10中，圖例A表示坯料在1號加熱爐中的開始加熱時間和加熱結(jié)束時間，對應矩形條中的文字表示坯料的鋼號和批次，如T10A，1表示坯料的鋼號為“T10A”，批次為第一批；中間的豎線表示同批次坯料中每支坯料的開始加熱時間，第一條豎線的位置表示坯料“T10A”的第一支坯料開始加熱時間為2．23min，加熱結(jié)束時間為220min，第二條豎線的位置表示坯料“T10A”的第二支坯料開始加熱時間為8．43min，加熱結(jié)束時間為220min。依次類推，圖例B，C和D分別表示坯料在2、3和4號加熱爐中的加熱開始和結(jié)束時間。圖中最后一行表示軋制坯料在熱軋機上的開始和結(jié)束時間，由圖例A，B，C和D四種灰度的小矩形條組成，每種灰度對應不同加熱爐中輸出的坯料。

t＝710時刻，3號加熱爐出現(xiàn)故障，這時需要將未發(fā)生沖突的坯料按照原計劃進行軋制，發(fā)生沖突的坯料利用沖突消解模型進行重排。另外，需要補充的是，發(fā)生故障時3號加熱爐中的坯料“40CrMNiMoA，7”由于已經(jīng)加熱一段時間，重排后被分配到1號加熱爐中進行加熱時要比預期的時間短。重排后得到如圖11所示的甘特圖，其中虛線的左邊是沖突消解前的調(diào)度方案，右邊是沖突消解后的調(diào)度方案。

3．2 實驗結(jié)果分析

對于加熱爐—熱軋區(qū)間的生產(chǎn)調(diào)度問題，將生產(chǎn)調(diào)度數(shù)學模型與實際生產(chǎn)業(yè)務相結(jié)合，并采用計算機仿真技術(shù)實現(xiàn)鋼鐵企業(yè)管理信息化，已成為鋼鐵企業(yè)研究的重要課題。計算機仿真技術(shù)結(jié)合了數(shù)學模型和智能算法，對實際生產(chǎn)業(yè)務進行了計算機模擬仿真，以驗證模型和算法的可行性和有效性，模擬結(jié)果可以輔助現(xiàn)場管理人員作出決策。本文通過仿真實驗，分析結(jié)果如下：

（1）NSGA－Ⅱ在解決多目標 NP－h(huán)ard問題時具有良好的計算能力。案例中，即使對具有4臺加熱爐、20批次60支坯料的問題也能在10min之內(nèi)（算法運行時間為552．96s）給出調(diào)度方案，明顯優(yōu)于人工現(xiàn)場調(diào)度，完全能夠滿足實際需求，有利于減輕調(diào)度人員的工作強度。

（2）由圖11可看出，對于常見異常情況，可以利用本文中建立的沖突消解模型進行第二次優(yōu)化仿真，實現(xiàn)坯料的重調(diào)度。仿真結(jié)果驗證了加熱爐—熱軋區(qū)間的生產(chǎn)調(diào)度數(shù)學模型和重調(diào)度數(shù)學模型的正確性。熱軋機出現(xiàn)斷軋的時間大幅度降低，加熱爐、軋機的利用率明顯提高，組成同一批次的加熱爐滿足后續(xù)軋制要求，坯料出爐的延遲問題也得到了解決。

（3）如圖10所示，1號、2號和3號加熱爐發(fā)生出坯延遲后，此時ttar≥tbuffter，熱軋機不能通過延長軋制時間緩沖坯料出爐的延遲時間，只能出現(xiàn)斷軋。對3號加熱爐中的坯料鋼號“42CrMo（B7），3”進行保溫處理，后續(xù)軋次采用加熱爐—熱軋區(qū)間的重調(diào)度數(shù)學模型進行局部調(diào)整，生成重調(diào)度甘特圖。

（4）由圖10可以看出，3號加熱爐中坯料鋼號為“42CrMo（B7），3”的入爐時間明顯遲于其他爐中的坯料，這是由于3號加熱爐的最早可用時間過長，導致熱軋機等待時間過長，降低了熱軋機的利用率。因此，可以根據(jù)仿真結(jié)果得到這樣一個結(jié)論：坯料集合的加工時間長度取決于每臺加熱爐中第一塊板坯的時間安排，這需要良好的軋次計劃作為支撐，這也是下一步研究的問題。

4 結(jié)束語

本文建立了加熱爐—熱軋區(qū)間的生產(chǎn)調(diào)度和重調(diào)度數(shù)學模型，并基于仿真優(yōu)化思想設計出解決該模型的多目標非支配排序遺傳算法。根據(jù)國內(nèi)某大型鋼鐵企業(yè)的實際生產(chǎn)數(shù)據(jù)，對所建立的模型和算法進行了仿真與驗證。仿真過程重點突出了加熱爐故障和熱軋機斷軋等異常情況對生產(chǎn)計劃的影響以及重調(diào)度方案的有效性。利用該方法可以在計劃實施前對仿真結(jié)果進行分析和評價，然后將結(jié)果應用于生產(chǎn)作業(yè)現(xiàn)場的指導，從而提高了重調(diào)度方案的可行性。通過實驗表明，基于仿真的多目標非支配排序遺傳算法在求解生產(chǎn)調(diào)度問題時便于考慮生產(chǎn)中的不確定因素，所得到的重調(diào)度方案更加接近企業(yè)的實際需求，具有較大的應用潛力和研究價值。

本文建立調(diào)度模型時主要考慮了加熱爐故障這類異常，在企業(yè)的生產(chǎn)實際中還存在訂單變化如插單、撤單等不確定的因素。因此，可進一步研究多種異常因素影響下的調(diào)度問題。另外，鋼鐵生產(chǎn)過程中設備發(fā)生故障后，可采用更換、簡單維修和小修等維修方式，因此需要考慮設備修復時間的重調(diào)度問題。

［1］ TANG L，LIU J，RONG A，et al．A review of planning and scheduling systems and methods for integrated steel production［J］．European Journal of Operational Research，2001，133（1）：1－20．

［2］ TANG L，LUH P B，LIU J，et al．Steel－making process scheduling using Lagrangian relaxation［J］．International Journal of Production Research，2002，40（1）：55－70．

［3］ NUMAO M，MORISHITA S．Scheplan－a scheduling expert for steel－making process［C］//Proceedings of the International Workshop on Artificial Intelligence for Industrial Applications．Washington，D．C．，USA：IEEE，1988：467－472．

［4］ NING Shushi，WANG Wei，LIU Quanli．An optimal scheduling algorithm for reheating furnace in steel production［J］．Information and Control，2006，21（10）：1138－1142（in Chinese）．［寧樹實，王 偉，劉全利．鋼鐵生產(chǎn)中的加熱爐優(yōu)化調(diào)度算法研究［J］．控制與決策，2006，21（10）：1138－1142．］

［5］ SUN Xuegang，YUN Chao，AN Zhengang．Optimization of scheduling for special steel reheat furnace based on immune－culture algorithm［J］．Control Theory ＆ Applications，2010，27（8）：1007－1011（in Chinese）．［孫學剛，贠 超，安振剛．基于免疫文化算法的特鋼加熱爐調(diào)度優(yōu)化［J］．控制理論與應用，2010，27（8）：1007－1011．］

［6］ LIANG Helan，LI Sujian，DENG Youhao．A two stage method for optimal scheduling problem of reheating furnace in hybrid charge mode production［J］．China Management Informationization，2009，12（15）：42－43（in Chinese）．［梁合蘭，李蘇劍，鄧又好．兩階段法求解混裝模式下的加熱爐調(diào)度［J］．中國管理信息化，2009，12（15）：42－43．］

［7］ CHEN Ailing，YANG Genke，WU Zhiming．Rolling plan op

timization model and algorithm for hot rolling processes［J］．Journal of System Simulation，2006，18（9）：2484－2488（in Chinese）．［陳愛玲，楊根科，吳智銘．軋制計劃的優(yōu)化模型及其算

法的應用研究［J］．系統(tǒng)仿真學報，2006，18（9）：2484－2488．］

［8］ GAO Huimin，ZENG Jianchao，SUN Guoji．Hybrid algorithm for hot strip mill rolling scheduling problem［J］．Journal of Xi'an Jiaotong University，2002，36（12）：1291－1294（in Chinese）．［高慧敏，曾建潮，孫國基．熱軋帶鋼調(diào)度問題的混合并行策略［J］．西安交通大學學報，2002，36（12）：1291－1294．］

［9］ LI Jianxiang，TANG Lixin，PANG Hali，et al．On production planning and sequencing of hot rolling seamless steel tube［J］．Control and Decision，2004，19（2）：238－240（in Chinese）．［李建祥，唐立新，龐哈利，等．熱軋無縫鋼管排產(chǎn)計劃研究［J］．控制與決策，2004，19（2）：238－240．］

［10］ SHIGUI R．Connective stability for large scale systems described by functional differential equations［J］．IEEE Transactions on Automatic Control，1988，33（2）：198－200．

［11］ YANG Yejian，JIANG Zeyi，ZHANG Xinxin．Model and algorithm of furnace area production scheduling in slab hot rolling［J］．Journal of University of Science and Technology Beijing，2012，34（7）：841－846（in Chinese）．［楊業(yè)建，姜澤毅，張欣欣．鋼坯熱軋加熱爐區(qū)生產(chǎn)調(diào)度模型與算法［J］．北京科技大學學報，2012，34（7）：841－846．］

［12］ WANG Shijin，XI Lifeng，TAO Lihua，et al．A heuristic algorithm for identical machines scheduling problem with weighted earliness and tardiness penalties［J］．China Mechanical Engineering，2004，15（22）：27－31（in Chinese）．［王世進，奚立峰，陶麗華，等．互替機床提前/延期懲罰調(diào)度問題的啟發(fā)式算法［J］．中國機械工程，2004，15（22）：27－31．］

［13］ CHENG T C E．Optimal common due－date with limited completion time deviation［J］．Computers ＆ Operations Research，1988，15（2）：91－96．

［14］ ZHU Baolin，YU Haibin．Production scheduling model and algorithm for steelmaking－continuous casting－h(huán)ot rolling processes［J］．Computer Integrated Manufacturing Systems，2003，9（1）：33－36（in Chinese）．［朱寶琳，于海斌．煉鋼—連鑄—熱軋生產(chǎn)調(diào)度模型及算法研究［J］．計算機集成制造系統(tǒng)，2003，9（1）：33－36．］［15］ 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)度多目標混合優(yōu)化［J］．控制與決策，2006，21（9）：996－1000．］

［16］ SUNJ，XUE D．A dynamic reactive scheduling mechanism for responding to changes of production orders and manufacturing resources［J］．Computers in Industry，2001，46（2）：189－207．

［17］ JENSEN M T．Improving robustness and flexibility of tardiness and total flow－time job shops using robustness measures［J］．Applied Soft Computing，2001，1（1）：35－52．

［18］ SABUNCUOGLU I，BAYLZ M．Analysis of reactive scheduling problems in a job shop environment［J］．European Journal of Operational Research，2000，126（3）：567－586．

［19］ LU Kebin，HUANG Kewei，ZHANG Ruiyou，et al．Simulation based genetic algorithm for production planning of steelmaking－continuous casting process［J］．Control and Decision，2011，26（1）：137－140（in Chinese）．［盧克斌，黃可為，張瑞友，等．煉鋼—連鑄作業(yè)計劃的基于仿真的遺傳算法［J］．控制與決策，2011，26（1）：137－140．］

［20］ SHAPIRO A．Simulation based optimization［C］//Proceed

ings of the 28th Conference on Winter simulation．Washing

ton，D．C．，USA：IEEE Computer Society，1996：332－336．

［21］ DEB K，PRATAP A，AGARWAL S，et al．A fast and elitist

multiobjective genetic algorithm：NSGA－Ⅱ［J］．IEEE Trans

actions on Evolutionary Computation，2002，6（2）：182－197．

［22］ ZHU Daofei，ZHENG Zhong，GAO Xiaoqiang．Optimization model based on genetic algorithms for production planning of steelmaking and continuous casting process［J］．Iron ＆Steel，2008，43（7）：26－31（in Chinese）．［朱道飛，鄭 忠，高小強．煉鋼—連鑄作業(yè)計劃的遺傳優(yōu)化模型［J］．鋼鐵，2008，43（7）：26－31．］

［23］ SHI Feng，WANG Hui，YU Lei，et al．Thirty analysis cases

of intelligent algorithm by using MATLAB［M］．Beijing：Beihang University Press，2011（in Chinese）．［史 峰，王

輝，郁 磊，等．MATLAB智能算法30個案例分析［M］．北京：北京航空航天大學出版社，2011．］

［24］ CHEN Chaowu，DONG Shaohua，DING Wenying．Optimization of multi stage production planning in ERW pipe manufacturing［J］．Journal of University of Science and Technology Beijing，2006，28（7）：691－695（in Chinese）．［陳超武，董紹華，丁文英．ERW鋼管多階段生產(chǎn)計劃的編制及優(yōu)化［J］．北京科技大學學報，2006，28（7）：691－695．］

［25］ LAWRENCE S．Resource constrained project scheduling：an experimental investigation of heuristic scheduling techniques［R］．Graduate School of Industrial Administration，Pittsburgh，Pen．，USA：Carnegie－Mellon University，1984．