基于NSGA—II的煉鋼—連鑄調(diào)度多目標(biāo)優(yōu)化

朱朝月

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

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

中圖分類號：TP273 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2016）08-0061-02

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

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

1.1 問題描述

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

1.2 基本假設(shè)

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

1.3 符號和變量

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

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

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

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

2 NSGA-II算法

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

2.1 NSGA-II排序方法

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

2.2 比較算子

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

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

3.1 編碼方式

3.2 求解步驟

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

4 仿真實(shí)驗(yàn)

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

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

5 結(jié)語

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

參考文獻(xiàn)

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

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

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

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

[5]龍建宇，鄭忠，高小強(qiáng)，等.基于遺傳算法的煉鋼--連鑄重計(jì)劃方法[J].北京科技大學(xué)學(xué)報(bào)，2014（1）.