朱朝月

摘要：為了多目標優(yōu)化煉鋼-連鑄生產(chǎn)調(diào)度問題，引入了快速非支配排序遺傳算法（NSGA-II）。以最小化澆次計劃完工時間和最小化中間等待時間作為優(yōu)化目標，依據(jù)煉鋼-連鑄工藝要求建立數(shù)學模型，通過NSGA-II在解空間搜索Pareto最優(yōu)解集。仿真結果表明，該算法解決煉鋼-連鑄調(diào)度問題，能夠迅速得到性能優(yōu)越的Pareto前端，編排出高質(zhì)量的生產(chǎn)計劃，提高決策者的工作效率。

關鍵詞：NSGA-II 煉鋼-連鑄 生產(chǎn)調(diào)度多目標優(yōu)化

中圖分類號：TP273 文獻標識碼：A 文章編號：1007-9416（2016）08-0061-02

煉鋼和連鑄工序的協(xié)調(diào)生產(chǎn)對改善鋼廠的生產(chǎn)組織方式和提高系統(tǒng)的運行效率起著非常重要的作用[1]。該過程中各方面約束限制和不可控因素較多，煉鋼-連鑄調(diào)度計劃的優(yōu)化，對于提高企業(yè)生產(chǎn)效率，降低資源、人力消耗等具有重要意義。對煉鋼-連鑄調(diào)度的優(yōu)化往往涉及多個優(yōu)化目標。不同的優(yōu)化目標可能相互制約，即某些目標的改善可能導致其它目標的惡化。NSGA-II是近年來興起的一種多目標優(yōu)化算法，它降低了非劣排序遺傳算法（NSGA）的復雜性，具有運行速度快，解集的收斂性好等優(yōu)點。本文引入NSGA-II對煉鋼-連鑄調(diào)度進行多目標優(yōu)化，并通過仿真實驗，驗證了該方法的有效性。

1 煉鋼-連鑄調(diào)度模型

1.1 問題描述

煉鋼-連鑄主要包含冶煉、精煉和連鑄三個主要環(huán)節(jié)，每個環(huán)節(jié)都存在多個并行機組。冶煉多為氧氣頂吹轉(zhuǎn)爐冶煉；精煉分為多種精煉工藝，如LF、RH、AOD等；連鑄是將液態(tài)鋼水連續(xù)澆鑄成固態(tài)鑄坯的過程。不同鋼種所需的精煉工藝存在差別，有的只經(jīng)過一道精煉工序，有的可能需要多重精煉。因此，煉鋼-連鑄調(diào)度問題屬于多工件、多階段和多并行機的，具有有限緩沖能力的混合流水車間調(diào)度問題[2]。通過煉鋼-連鑄調(diào)度計劃編制，協(xié)調(diào)各工序各設備的生產(chǎn)節(jié)奏，在滿足約束條件的前提下，盡可能縮短爐次的等待時間，縮短澆次計劃的完工時間。

1.2 基本假設

考慮到鋼鐵生產(chǎn)流程的復雜性，為了便于煉鋼-連鑄調(diào)度問題的數(shù)學抽象，現(xiàn)根據(jù)實際情況做如下假設：（1）只考慮冶煉、精煉和連鑄三個主要環(huán)節(jié)的工序及設備。（2）澆次計劃已知，包括澆次總數(shù)、各澆次所包含的爐次數(shù)、爐次的加工流程及對應的目標鑄機。（3）已知爐次在上下工序間的運輸時間、最長等待時間以及同一連鑄機上相鄰澆次間的最短間隔時間。

1.3 符號和變量

符號：表示第j個澆次第i個爐次；表示第k種的第l個設備。變量：、分別表示在上加工的開始時間和結束時間；常數(shù)：N為爐次總數(shù)；P為澆次總數(shù)；R為設備種類總數(shù)（k=1為轉(zhuǎn)爐，k=R為連鑄機）；表示爐次在兩設備間運輸所需的時間，表示爐次在兩設備間的最長運輸時間。

1.4 數(shù)學模型

基于對模型的基本假設，構建煉鋼-連鑄調(diào)度的多目標優(yōu)化模型如下：

式（1）是最小化完成整個澆次計劃的時間；式（2）是最小化各爐次等待時間。根據(jù)實際煉鋼-連鑄過程，模型需滿足以下約束條件：（1）每個爐次屬于且僅屬于一個澆次；（2）爐次在加工過程中，必須完成一個工序后，才能開始下一個工序；（3）每個爐次都有固定的工序順序；（4）每個設備在同一時間加工的爐次數(shù)不超過其工位數(shù)；（5）每個工序加工時間不小于其必要加工時間；（6）鋼包在工序間停留時間小于允許的最長等待時間；（7）同一鑄機相鄰澆次間隔時間，不小于其最小間隔時間。

2 NSGA-II算法

NSGA-II是在NSGA（非支配排序遺傳算法）的基礎上進行改進的算法，具有以下特點：（1）采用快速非支配排序，降低了算法的計算量；（2）提出了擁擠度比較算子，并在快速排序后作為衡量同級個體優(yōu)劣的標準；（3）引入精英策略，將交叉變異操作前后的種群合并，共同競爭產(chǎn)生下一代種群[3]。

2.1 NSGA-II排序方法

對種群中任一個體x，都有支配x的個體數(shù)和x所支配的解集。首先，選出種群中所有=0的個體，構成集合；然后對于中的每個個體y，找出其所支配的解集中的每個個體z的，若=1，則將個體z存入另一個集合。繼續(xù)對作上述分級操作，直到所有個體都被分級。最后，分別賦予每級個體非支配序號（=1，=2，=3…）。

2.2 比較算子

為了確保種群的多樣性，NSGA-II提出了擁擠度的概念，即個體周圍其他個體的密集程度。對于個體x，計算由個體x+1和x-1構成的最小長方形的平均邊長，作為x的擁擠度距離。比較兩個體優(yōu)劣時，首先比較其所屬非劣等級，等級需要越小越好；等級相同時，比較兩個體的擁擠度距離，越大越好。

3 NSGA-II對煉鋼-連鑄調(diào)度的多目標優(yōu)化

3.1 編碼方式

3.2 求解步驟

Step1：確定種群規(guī)模，截止進化代數(shù)等算法相關參數(shù)。Step2：=0，隨機生成足夠多的個體，篩選符合約束條件的個，構成種群。Step3：交叉、變異，生成子代種群。將和合并，規(guī)模2。Step4：將混合后的種群進行非支配排序，同一等級的個體按照擁擠度距離排序。選出優(yōu)良個體組成下一代種群。重復Step3和Step4，直到=。Step5：種群中非劣等級為1的個體構成Pareto最優(yōu)解集，將其輸出并結束運行[4]。

4 仿真實驗

國內(nèi)某鋼廠，設有180 t轉(zhuǎn)爐3座，LF爐2臺，RH爐1臺，板坯連鑄機2臺（CC1、CC2）。現(xiàn)以表1中的澆次計劃進行仿真實驗[5]。

仿真結果如圖1所示，完成澆次計劃總時間為605min，各爐次加工流程順暢，沒有長時間等待停留。通過NSGA-II編制的作業(yè)計劃可以保證連續(xù)澆鑄，且各工位作業(yè)時間沒有沖突。

5 結語

綜上所述，基于NSGA-II的煉鋼-連鑄調(diào)度多目標優(yōu)化方法能夠保證各爐次加工過程順暢，縮短澆次計劃完工時間，提高作業(yè)效率。該方法能夠借助計算機運行，在短時間內(nèi)編制出高質(zhì)量的作業(yè)計劃，降低決策者工作量，具有較高的現(xiàn)實意義和推廣價值。

參考文獻

[1]鄭忠，朱道飛，高小強.基于蟻群算法的煉鋼-連鑄作業(yè)計劃編制方法[J].北京科技大學學報，2009（4）：504-510.

[2]王剛，王彬，王寶，等.基于“爐機對應”原則的煉鋼—連鑄調(diào)度模型[J].北京科技大學學報，2013（8）.

[3]高媛.非支配排序遺傳算法（NSGA）的研究與應用[D].浙江大學，2006.

[4]高振東，丁宇菁.基于遺傳算法的加油車智能派工系統(tǒng)的設計與實現(xiàn)[J].數(shù)字技術與應用，2012（5）：111-112.

[5]龍建宇，鄭忠，高小強，等.基于遺傳算法的煉鋼--連鑄重計劃方法[J].北京科技大學學報，2014（1）.