熱軋實(shí)施計(jì)劃中最優(yōu)倒垛問(wèn)題整數(shù)模型及遺傳算法

264期2000年7月

自動(dòng)化學(xué)ACTAAUTOMATICASIN

Vol.26,No.Jul.,整數(shù)規(guī)劃模型及遺傳算法1)唐立 (東學(xué)系統(tǒng)工程沈陽(yáng) (Ealqhjylx@alsylncn)摘要對(duì)鋼鐵企業(yè)板坯庫(kù)中的最優(yōu)倒垛問(wèn)題建立了0和1整數(shù)規(guī)劃模型這一模型是一個(gè)且目標(biāo)函數(shù)的系數(shù)與變量的取值相關(guān)聯(lián)屬于NP難問(wèn)題,獲得較大規(guī)模的最優(yōu)解是不可能或非常.為了求解此問(wèn)題,本文構(gòu)造了改進(jìn)遺傳算法:(1)提出了適合于最優(yōu)倒垛問(wèn)題的遺傳編碼,運(yùn)用此編碼,不但能夠產(chǎn)生可行的初始,而且能夠保證在交叉和變異操作后的仍然可行;(2)改進(jìn)了遺傳算法結(jié)構(gòu),在新的結(jié)構(gòu)中,增加了一個(gè)培育操作,改進(jìn)了交叉操作.通過(guò)精選隨機(jī)產(chǎn)生的問(wèn)題例子的實(shí)驗(yàn)顯示出,算法的性能明顯7.04%.,板坯倒垛,,改進(jìn)遺傳算法.ALGORITHMFOROPTIMALTURNEDOUTSLABPILEFORHOTROLLINETANG YANG(InstituteofSystemsEngineering,NortheasternUniversity, Theoptimalturned-outslabpile(TOSP)problemintheslabyardofiron&steelindustryisformulatedasabinaryintegerprogrammingmodelinthispaper.Thisisaquadraticprogrammingmodelandthecoefficientsoftheobjectivefunctionarerelatedtothevaluesofvariables.BecauseofNP-hardnessofTOSPproblem,itisdifficult,orevenimpossible,tofindtheoptimalsolutiontothelarge-scaleactualproblem.InordertosolveTOSP,thispaperdevelopsthemodifiedgeneticalgorithm(MGA)forthisproblem:1)toconstructthegeneticcodingsuitablefortheoptimalTOSPproblem.Itcannotonlygeneratefeasibleinitialchromosomes,butalsoensurechromosomefeasibilityaftercrossoverandmutation.2)toformaMGArk:anewcultivatingoperationisintroduced;andcrossover)國(guó)家863/CIMS計(jì)劃支持項(xiàng)目(8635708009)和國(guó)家自然科學(xué)基金資助項(xiàng)目( ),國(guó)家教育部?jī)?yōu)秀年輕教師研究基金和中國(guó)機(jī)器人學(xué)開(kāi)放課題收稿日 999 收修改稿日 99909 26isimproved.ThecomputationalexperimentswiththeselectedcasesoftherandomlyproducedproblemsshowthattheproposednewMGAisremarkablybetterthantheoriginalheuristicsforTospproblem,withthebestimprovementof7.04%Iron&steelindustry,productionscheduling,turned-outslabpile,integerprogramming,modifiedgeneticalgorithm.引板坯庫(kù)是連接煉鋼和熱軋生產(chǎn)工藝的中間緩沖環(huán)節(jié).它既是其緊前上游工序——煉鋼工序生產(chǎn)出來(lái)的板坯的存放地,也是其緊后下游工序——熱軋工序需要進(jìn)行加工的原料(板坯)的直接供給地.熱軋工藝是按照軋制單元計(jì)劃進(jìn)行組織生產(chǎn)的.每一個(gè)軋制單元計(jì)劃實(shí)質(zhì)就是一個(gè)板坯的加工序列.在制定軋制單元計(jì)劃時(shí),主要是根據(jù)合同產(chǎn)品涉及到的板坯號(hào)、板坯鋼級(jí)、板坯寬度、重量、厚度和交貨期等信息,不知道板坯庫(kù)中的板坯的實(shí)際垛位位置情況因而在軋制單元計(jì)劃實(shí)施前需要根據(jù)板坯的實(shí)際垛位情況對(duì)軋制單元計(jì)劃中的每一個(gè)軋制位置的板坯從其對(duì)應(yīng)的可交換板坯組中進(jìn)行重新選擇,保證總的倒垛次數(shù)最少,這個(gè)問(wèn)題簡(jiǎn)稱最優(yōu)倒垛問(wèn)題.倒垛次數(shù)高,吊機(jī)的負(fù)荷就大,生產(chǎn)效率低.因此,最優(yōu)倒垛問(wèn)題直接關(guān)系到車(chē)間的生產(chǎn)效率和企業(yè)的生產(chǎn)效益,是生產(chǎn)上迫切需要解決的問(wèn)題.對(duì)于板坯倒垛優(yōu)化問(wèn)題,80年代末,德國(guó)的梯森在我國(guó)寶鋼投產(chǎn)時(shí)開(kāi)發(fā)了一個(gè)啟發(fā)式算法,這一程序一直運(yùn)行到現(xiàn)在.但是隨著長(zhǎng)時(shí)間的大量使用發(fā)現(xiàn),原有的算法倒垛效率低.從國(guó)內(nèi)外公開(kāi)的文獻(xiàn)來(lái)看,已有的研究是圍繞煉鋼連鑄[1～3和熱軋[～6階段的生產(chǎn)管理問(wèn)題進(jìn)行的,對(duì)于倒垛問(wèn)題還沒(méi)有發(fā)現(xiàn)公開(kāi)的.本文的主要工作是對(duì)最優(yōu)問(wèn)題的描述及數(shù)學(xué)模11所示.圖1,需要的板坯是指軋制單元計(jì)劃所建議的板坯在圖中用陰在需要板坯的上面的板坯為倒垛板坯,只有這些倒垛板坯被移到其它垛位上,才能露出所需要的板坯.需要板坯露出后,通過(guò)吊車(chē)運(yùn)到相應(yīng)的加熱爐中進(jìn)行加熱,然后才能進(jìn)行

軋制.垛高是指該垛位疊放的板坯數(shù).板坯的記數(shù)是從垛底開(kāi)始的,這樣,圖14 唐立新等 垛底的板坯為垛位中的第一塊板坯一個(gè)軋制單元計(jì)劃是由M個(gè)軋制項(xiàng)目(板坯)組成,這些軋制項(xiàng)目的順序和位置在熱軋計(jì)劃中被確定,根據(jù)生產(chǎn)工藝的要求是固定不變的.一般在一個(gè)軋制單元計(jì)劃實(shí)施前,需要釋放3～5個(gè)軋制單元計(jì)劃,以便從其對(duì)應(yīng)的板坯構(gòu)成計(jì)劃預(yù)選池,軋制單元計(jì)劃板坯,從而構(gòu)成對(duì)應(yīng)這一位置的可交換板坯組.在軋制單元計(jì)劃中引入下面一些符號(hào),以已知參數(shù)如下={1,M為整個(gè)軋制單元計(jì)劃的組成項(xiàng)目的軋制位置集合M為一個(gè)軋制單元計(jì)劃包括的項(xiàng)目數(shù).S=1,N}為整個(gè)計(jì)劃預(yù)選池中板坯集合N為一個(gè)板坯庫(kù)計(jì)劃預(yù)選池中數(shù)Si=為第i個(gè)軋制位置對(duì)應(yīng)的可交換板坯集合,Si∩Sk ,為空集,其中i,k∈ik.

決策變量為1,ij塊板坯,i,j∈SiXij

0,否則數(shù)學(xué)規(guī)劃模型

( min.∑∑Ci,j*Xi,j (1jN>M>i>j∈

xi,j= i∈; (xi,j≤ j∈ (xi,j= i∈; (xi,j=0,i∈,j∈S但jSi. 在這里系數(shù)Ci,j表示當(dāng)位置i需要板坯j時(shí),需要的凈倒垛次數(shù).它是動(dòng)態(tài)變化的,不是一個(gè)常數(shù),它的取值依賴于前i-1個(gè)項(xiàng)目選擇的板坯垛位情況.Ci,j應(yīng)是一個(gè)凈數(shù)量,設(shè)置Dj在計(jì)劃執(zhí)行前第j塊板坯上面的原始板坯數(shù)量,則Ci,j具體表達(dá)如下:i-Ci,j=Dj-∑∑min{max{Dj-Dk,0} Xn,kn1k∈m (目標(biāo)函數(shù)(1)是使得總的導(dǎo)垛次數(shù)最小.約束(2)使得每一個(gè)軋制位置必須有一塊且只能有一塊板坯.約束(3)是使得任一板坯最多只能分配到一個(gè)軋制單元計(jì)劃中的相應(yīng)位置當(dāng)中.約束(4)是使得每一個(gè)軋制位置一定是由其對(duì)應(yīng)的可交換板坯集合的任一板坯來(lái)填充.約束5是使得每一個(gè)軋制位置不能由其對(duì)應(yīng)的可交換板坯集合以外的板坯來(lái)填充.這實(shí)質(zhì)是一個(gè)二次規(guī)劃模型,求解其最優(yōu)解是相當(dāng)?shù)? 最優(yōu)倒垛問(wèn)題(P)的改遺傳算法(GA)是一類基于自然進(jìn)化和選擇機(jī)制自適應(yīng)的搜索算法,它成功地應(yīng)用到多種優(yōu)化問(wèn)題的求解[7.一般遺傳算法求解最優(yōu)倒垛問(wèn)題有兩個(gè):1)可行化的遺傳編碼構(gòu)造;2)最優(yōu)性能難以保證針對(duì)這種情況,本文構(gòu)造了下面的改進(jìn)遺傳算法.改進(jìn)遺傳算法(MGA)結(jié)

改進(jìn)遺傳算法結(jié)構(gòu)如圖2所示,與一般遺傳算法相比有兩點(diǎn)不同:增加了一個(gè)培育操作,改進(jìn)了交叉操作.培育操作:通過(guò)實(shí)驗(yàn)顯示出,當(dāng)遺傳算法在一定代數(shù)不能改進(jìn)時(shí),大約為30代,如果繼續(xù)迭代下去,則解的質(zhì)量很難改變或改變較少.在這里修改了遺傳算法操作,如果當(dāng)連續(xù)迭代的代數(shù)超過(guò)一個(gè)給定數(shù)量時(shí),解的育最有希望的,既把最好的通過(guò)鄰域搜索算法進(jìn)行改進(jìn),然后返回選擇操作當(dāng)中,繼續(xù)進(jìn)行下一代的迭代.模式交叉操作:傳統(tǒng)的交叉模式是隨機(jī)產(chǎn)生兩個(gè)配對(duì)進(jìn)行交叉,產(chǎn)生兩個(gè)新的子代,這種交叉效果不是很好.圖2對(duì)的兩個(gè)采用位交叉方法進(jìn)行交叉

色體和隨機(jī)產(chǎn)生的另一個(gè)相配對(duì),配對(duì)于最優(yōu)倒垛問(wèn)題,用傳統(tǒng)的二進(jìn)制編碼和無(wú)的自然數(shù)編碼[7,初始無(wú)法保證可行,更談不上交叉和變異后保持可行.在下面構(gòu)造的一種新的遺傳編碼方法,不但能夠產(chǎn)生初始可行的,而且交叉和變異后的仍然可行.編碼的基本思想和方法的是用制單元計(jì)劃對(duì)應(yīng)的板坯序列號(hào)構(gòu)造..如果一個(gè)軋制單元計(jì)劃是一個(gè)由M塊板坯組成的板坯序列,每一個(gè)軋制位置對(duì)應(yīng)的可交換板坯集合中的元素用自然數(shù)從小到大進(jìn)行單獨(dú)編號(hào),則的長(zhǎng)度為M,位置與軋制單元計(jì)劃的軋制位置相一致,并一一對(duì)應(yīng),的值是由對(duì)應(yīng)軋制位置的可交換板坯集合中的板坯序號(hào)構(gòu)成的.對(duì)應(yīng)間.設(shè)的組成為序列P1P2…PL,則其數(shù)學(xué)描述及具體規(guī)定如下:L= (Pi1,,Sii∈1,MSii個(gè)可交換板坯集合的元素?cái)?shù)量,范為4 唐立新等 1≤Si≤ (1O11,2,3}O2={1,2}O3={1,2,3,4,5},O={1,2,3,4,5,6}一個(gè)軋制單元計(jì)劃對(duì)應(yīng)的4個(gè)軋制位置的可交換板坯集合.一個(gè)為A=2145的染色體的含義是軋制單元計(jì)劃有4塊板坯組成,第一個(gè)值表示第一個(gè)軋制位置是由O1中第2塊板坯組成,第二個(gè)值表示第二個(gè)軋制位置是由O2中第1塊板坯組成,第三個(gè)值表示第三個(gè)軋制位置是由O3中第4塊板坯組成,第四個(gè)值表示第四個(gè)軋制位置是由O中第5塊板坯組成.性質(zhì)1.滿足條件(6)和(7)形式的為原問(wèn)題的可行解證明滿足原問(wèn)題可行解的充分條件是要滿足模型P)的約束條件(2)3),(4),(5).設(shè)一P1P2…PL滿足上面的條件(6)和(7),則Pi(i∈)對(duì)應(yīng)可交換板坯集Si中的第Pi個(gè)元素P中整個(gè)板坯序號(hào)屬于大排序的Si中的第Pi個(gè)元素對(duì)應(yīng)一個(gè)Ji(也就是對(duì)應(yīng)一個(gè)確定性的板坯序號(hào)Ji)=J(PiJi)Si.Xi,Ji=1;而對(duì)于jSJiXij=0;kK{iXkJ=0,所以存在如下關(guān)系對(duì)于i∈,∑Xi,j=Xi,J(i ∑Xi,j=1,所以模型(P)的約束(2)滿足j∈ j∈S\JjS,jR={J1),J2),JMjSR兩種情況jRj=JmXm,J(m=1,k\{mXkJ(i=0,Xi,=1,jSRi,Xij=0,

Xi,j,=綜合以上兩種情況,jS

Xi,j,1.這樣,模型(P)的約束3)滿足i

i

Xi,j=Xi,J(i j∈Si\J(

Xi,j=1,這樣,P)的約束4)滿足i,jSJi)jSjSi的情況i,jSjSi,Xi,j=0.模型(P)的約束(5)滿足 證畢要計(jì)算適應(yīng)度函數(shù),首先要計(jì)算目標(biāo)函數(shù)值.根據(jù)一個(gè)值確定目標(biāo)函數(shù)的過(guò)程稱為譯碼計(jì)算.從性質(zhì)1的證明過(guò)程可看出,對(duì)于任一P1P2…PM對(duì)應(yīng)問(wèn)P)一個(gè)可行解,Xiji,jS的值全部都能確定P)1)式能夠計(jì)算目標(biāo)函數(shù).這樣就把的值轉(zhuǎn)換為目標(biāo)函數(shù)的值.選擇策略采用傳統(tǒng)的滾動(dòng)策略[7采用位交叉方法進(jìn)行交叉其過(guò)程為:根據(jù)隨機(jī)產(chǎn)生的交叉點(diǎn),兩個(gè)隨機(jī)配對(duì)的染色體從交叉點(diǎn)后進(jìn)行互換,形成兩個(gè)新的.性質(zhì)2.兩個(gè)可行通過(guò)位交叉操作后產(chǎn)生的兩個(gè)新的仍為原問(wèn)題的可行解..假設(shè)有兩個(gè)配對(duì)的O1=A1A2A3…AMO2=B1B2B3…BM 假設(shè)交叉位置在k,交叉以后的D1=A1A2 BkBk+1…BMD2=B1B2 AkAk+1…AM因?yàn)镺1和O2為兩個(gè)可行,有Ai∈{1,…,Si},Bi∈{1,…,Si},i∈.這就說(shuō)明,D1和D2滿足約束(6)和(7)式的要求,根據(jù)性質(zhì)1,交叉后的D1和D2仍然可行. 證畢.對(duì)于變異,經(jīng)常使用的兩種方法是:1)變值變異方法,是將需要變異的由0(或1)到1(或0)進(jìn)行變值.這種方法只適用于二進(jìn)制編碼的遺傳算法當(dāng)中.(2)交換變異方法,是將兩個(gè)位置進(jìn)行交換.這種交換策略適合于用無(wú)的自然數(shù)編碼的遺傳算法變異當(dāng)中上面兩種變異策略對(duì)于倒垛問(wèn)題(P)都不能保證變異后可行.例2.對(duì)于(P)采用前面3.2節(jié)的遺傳編碼方法產(chǎn)生的為Q=52461,假設(shè)=5,S2=2,采用位交換變異方法如下12Q= 位交換變 Q1=因?yàn)镾2=2,而Q1中第二位是5,大于S2,根據(jù)性質(zhì)1,Q1是不可行本文提出了適合倒垛問(wèn)題的變異方法,對(duì)于任一Pi,當(dāng)變異時(shí)候,其值變?yōu)镠iSi+1-Pi,采用這種值變異方法,能夠保證變異后的仍然可行性質(zhì)3.一個(gè)可行的通過(guò)上面的值變異方法變異后仍為原問(wèn)題的可行解證明.設(shè)任一可行為P1P2…PM,假設(shè)其中的Pg經(jīng)過(guò)變異后變?yōu)镠g,其它不變,因?yàn)?≤Pi≤Si,i∈K所以存在1≤Pg≤Sg,兩邊乘-1后得到--Pg-1,兩邊加上Sg+1得,1≤Sg+1-Pg≤Sg,所以有1Hg≤Sg,這樣對(duì)于變異后的新仍然滿足性質(zhì)1的條件.則變異后的仍然可行.證畢.本節(jié)敘述3.1節(jié)提到的培育操作中使用的鄰域搜索算法的鄰域結(jié)構(gòu)定義1.替換鄰域結(jié)構(gòu):對(duì)于整個(gè)軋制單元計(jì)劃的每一個(gè)位置的軋制項(xiàng)目,都可以用其對(duì)應(yīng)的組選板坯集合中的板坯來(lái)替換,構(gòu)成一個(gè)鄰域結(jié)構(gòu)設(shè)這個(gè)鄰域結(jié)構(gòu)為..M域的計(jì)算量為i

Si-1)證明因?yàn)閷?duì)于一個(gè)軋制單元計(jì)劃中的板坯Pi,其對(duì)應(yīng)的可交換板坯集合的元素個(gè)數(shù)為Si,但是因?yàn)榭山粨Q板坯集合中包括現(xiàn)有板坯Pi,這樣Pi可替換的板坯數(shù)為Si 1,因?yàn)檐堉祈?xiàng)目的鄰域的計(jì)算量為這種替換的全部單回路(單程)過(guò)程枚舉之和,該M制單元計(jì)劃包括M個(gè)軋制項(xiàng)目,所以其鄰域計(jì)算量為i

(Si- 證畢4 唐立新等 仿真數(shù)據(jù)的產(chǎn)生涉及到以下三種因素問(wèn)題的結(jié)構(gòu).問(wèn)題的結(jié)構(gòu)涉及到兩個(gè)因素:一個(gè)是軋制單元計(jì)劃包括的項(xiàng)目數(shù),另一個(gè)是垛高分布情況.在此實(shí)驗(yàn)中,軋制項(xiàng)目數(shù)分為5種情況;而垛高分布分為4種情況,共有20種不同情況.每一種情況,產(chǎn)生10次不同的隨機(jī)數(shù),板坯虛擬編碼的變化范圍是不變的,這樣總共產(chǎn)生200種情況的例子.情況下的算法性能,選擇了5種不同的項(xiàng)目數(shù)的情況,如表1所示.因?yàn)閷?shí)際一個(gè)軋制單元計(jì)劃最多包括180個(gè)板坯,所以最大的項(xiàng)目數(shù)設(shè)置為180.4種不同的垛高數(shù)的變化情況.每一種垛高的變化范圍如表2所示,數(shù)字的選擇覆蓋了實(shí)際的垛高范圍.每一種情況的垛高是在其規(guī)定范圍內(nèi)按照均勻分布產(chǎn)生的整數(shù).表1項(xiàng)目數(shù)的變化情況項(xiàng)目表2垛高范圍HXY 4垛高分布HXY)6802MSC.6.0在Pentium主頻為133的計(jì)算機(jī)上實(shí)現(xiàn)了最優(yōu)倒垛問(wèn)題的改進(jìn)遺傳算法,通過(guò)大量的仿真,改進(jìn)遺傳算法的最優(yōu)參數(shù)配置如表3所示.表3MAXGENPOPS00為了比較算法和原系統(tǒng)的算法性能,本文也實(shí)現(xiàn)了老系統(tǒng)的啟發(fā)式算法,并通過(guò)了實(shí)際數(shù)據(jù)的案例,檢驗(yàn)了算法實(shí)現(xiàn)的正確性.對(duì)于20種不同的情況,算法的計(jì)算結(jié)果如表4所示在表4中,第2和3列表示算法的相對(duì)最優(yōu)性能,用下面的相對(duì)測(cè)量方法 來(lái)表示相對(duì)最優(yōu)性對(duì)于每一種情況的結(jié)果,分別表示為(C1/C*))/10和(C2 i iCi10的計(jì)算結(jié)果,Ci=min{C1iC2iC1iC2i分別為同一種情況,12i次隨機(jī)數(shù)的目標(biāo)函數(shù)值564為基礎(chǔ)進(jìn)行計(jì)算的,分從表4～表6的計(jì)算結(jié)果得出如下結(jié)論在最優(yōu)性方面,對(duì)于二十種情況,從表4的第二列和第三列可以看出,改進(jìn)遺傳算法全部都優(yōu)啟發(fā)式算法.最好的情況可以達(dá)到改進(jìn)率7.04%.5的第二列和第三列可以看出,隨著項(xiàng)目數(shù)的增加,改進(jìn)遺傳算法與原系統(tǒng)的啟發(fā)式算法比較,相對(duì)性能明顯提高.從表6的第二列和第三列可以看出,隨著垛位分布數(shù)的下降, 統(tǒng)的啟發(fā)式算法比較,相對(duì)性能明顯提高計(jì)算時(shí)間方面.從實(shí)際運(yùn)行來(lái)看,由遺傳算法但是它換來(lái)了產(chǎn)生最終方案人工..表 s60380300320360980900920960800020060580206880408202表 (003009052058表 倒垛問(wèn)題隨垛位分布變化的新老系統(tǒng)性能比((607280720007220724 唐立新等 5倒垛問(wèn)題給出了一種新的定量方法,在建立了數(shù)學(xué)模型基礎(chǔ)上,提出了改進(jìn)的遺傳算法.并以此模型和算法為,開(kāi)發(fā)了整個(gè)最優(yōu)倒垛調(diào)度仿真系統(tǒng).該系統(tǒng)于1997年12月在微機(jī)環(huán)境下開(kāi)發(fā)完畢,在寶鋼熱軋廠仿真系統(tǒng)進(jìn)行了運(yùn)行.根據(jù)實(shí)際數(shù)據(jù)的仿真計(jì)算,證明了算法的有效性.從國(guó)內(nèi)外公開(kāi)的文獻(xiàn)來(lái)看,還沒(méi)有發(fā)現(xiàn)此類模型和及相應(yīng)的算法,本文對(duì)這一問(wèn)題的定量方法,除了具體參數(shù)不同外,對(duì)其他鋼鐵企業(yè)的板坯庫(kù)的倒垛問(wèn)題具有較好的通用性.參考文LeeHS,MurhySS,HaderSWetalPraryproduconschedulngaseelakngndusresIBMJournalofRese