基于加工時(shí)間可控的煉鋼-精煉-連鑄調(diào)度問題研究

基于加工時(shí)間可控的煉鋼-精煉-連鑄調(diào)度問題研究

1遺傳算法迭代模型求解普通精煉連鑄生產(chǎn)過程是鋼鐵產(chǎn)品生產(chǎn)過程的上游，是鋼鐵產(chǎn)品生產(chǎn)的重要因素。合理的生產(chǎn)過程可以有效地提高員工的生產(chǎn)效率，降低生產(chǎn)成本，并能源消耗。理論上，回顧精煉連鑄的生產(chǎn)計(jì)劃，主要是基于親水混合軸的問題。還有一些問題。由于煉鋼–精煉–連鑄生產(chǎn)調(diào)度問題在理論研究和實(shí)際應(yīng)用中的重要價(jià)值,一直吸引著國內(nèi)外學(xué)者和業(yè)界人士的研究和關(guān)注.文獻(xiàn)基于just-intime思想給出了非線性規(guī)劃模型,解決調(diào)度過程中的設(shè)備沖突問題,并轉(zhuǎn)化為線性規(guī)劃模型用標(biāo)準(zhǔn)線性規(guī)劃程序?qū)ζ溥M(jìn)行求解.文獻(xiàn)給出了整數(shù)規(guī)劃的調(diào)度模型,設(shè)計(jì)了拉格朗日松弛、動(dòng)態(tài)規(guī)劃和啟發(fā)式算法相結(jié)合的求解算法.文獻(xiàn)以實(shí)際鋼鐵企業(yè)為研究背景,給出了混合整數(shù)規(guī)劃模型,應(yīng)用標(biāo)準(zhǔn)軟件包對其進(jìn)行求解.文獻(xiàn)設(shè)計(jì)了蟻群優(yōu)化和非線性優(yōu)化相結(jié)合的混合算法,第1階段確定工件的加工設(shè)備及工件的加工順序,第2階段應(yīng)用非線性優(yōu)化方法確定工件的加工開始時(shí)間.文獻(xiàn)建立了0-1混合整數(shù)規(guī)劃模型,對模型進(jìn)行Benders分解,提出了第1階段應(yīng)用遺傳算法提高種群質(zhì)量和第2階段應(yīng)用線性規(guī)劃指導(dǎo)遺傳算法迭代的兩階段求解算法.文獻(xiàn)建立了帶運(yùn)輸時(shí)間的兩機(jī)器調(diào)度模型和煉鋼–精煉兩階段多并行機(jī)的調(diào)度模型,其中兩階段調(diào)度模型以最小化最大完成時(shí)間、設(shè)備空閑時(shí)間和爐次等待設(shè)備時(shí)間為調(diào)度目標(biāo),設(shè)計(jì)了禁忌搜索算法對模型進(jìn)行求解.目前,對加工時(shí)間可控的調(diào)度問題的研究不多,文獻(xiàn)給出了工序加工時(shí)間可控的排列流水車間(permutationflowshop)調(diào)度問題的模型,并設(shè)計(jì)了結(jié)合插入算子的局域搜索算法.文獻(xiàn)采用三角模糊數(shù)表示煉鋼連鑄生產(chǎn)中工序的不確定加工時(shí)間,建立了模糊規(guī)劃調(diào)度模型并設(shè)計(jì)了遺傳算法對其進(jìn)行求解.分析以上研究成果作者發(fā)現(xiàn),現(xiàn)有研究一般均假設(shè)鋼水在各設(shè)備上的加工時(shí)間為固定值,并把煉鋼–精煉–連鑄生產(chǎn)調(diào)度問題轉(zhuǎn)化為以makespan最小為優(yōu)化目標(biāo)的混合flowshop問題進(jìn)行求解.這種假設(shè)與煉鋼–精煉–連鑄實(shí)際生產(chǎn)過程存在以下差異:1)在實(shí)際生產(chǎn)過程中,鋼水在連鑄設(shè)備上的連續(xù)澆鑄是生產(chǎn)調(diào)度人員優(yōu)先保證的作業(yè)目標(biāo),為了實(shí)現(xiàn)連續(xù)澆鑄目標(biāo),調(diào)度人員可以根據(jù)生產(chǎn)實(shí)績在一定范圍內(nèi)動(dòng)態(tài)調(diào)整鋼水在各設(shè)備上的加工時(shí)間,即鋼水在各設(shè)備的加工時(shí)間可控;2)煉鋼–精煉–連鑄加工過程中鋼水在各階段的工藝溫度必須在一定的范圍內(nèi),因此,鋼水在設(shè)備間的傳擱時(shí)間存在上下限要求,并且要求連鑄工序連續(xù)加工;3)為了提高生產(chǎn)效率,降低能源消耗,生產(chǎn)調(diào)度的目標(biāo)不僅要考慮makespan最小,還要最小化鋼水在設(shè)備間的等待時(shí)間以及設(shè)備的空閑時(shí)間.上述研究成果中,文獻(xiàn)以爐次的最大完工時(shí)間、澆次的開澆提前/托期懲罰最小為調(diào)度目標(biāo),未考慮爐次等待設(shè)備時(shí)間的調(diào)度目標(biāo);文獻(xiàn)同時(shí)考慮了爐次等待時(shí)間和設(shè)備等待時(shí)間最小的調(diào)度目標(biāo),但均假定工序的加工時(shí)間是固定的,且文獻(xiàn)僅考慮了煉鋼和精煉兩階段的調(diào)度計(jì)劃模型.文獻(xiàn)考慮了permutationflowshop調(diào)度問題中工序加工時(shí)間的可控性,沒有考慮煉鋼–精煉–連鑄加工過程中鋼水在設(shè)備間傳擱時(shí)間的上下限要求及連鑄工序連續(xù)加工的特性.文獻(xiàn)考慮了煉鋼連鑄調(diào)度問題中加工時(shí)間不確定的特點(diǎn),但并未將爐次等待設(shè)備時(shí)間和設(shè)備等待爐次時(shí)間作為優(yōu)化目標(biāo).本文針對問題實(shí)際特點(diǎn)及現(xiàn)有研究方法的不足以最小化makespan、最小化爐次等待時(shí)間和設(shè)備等待時(shí)間之和為優(yōu)化目標(biāo),提出了煉鋼–精煉–連鑄生產(chǎn)調(diào)度計(jì)劃的兩階段優(yōu)化方法.第1階段以各爐次在各階段的正常加工時(shí)間為參數(shù),采用分散搜索(scattersearch,SS)算法確定各爐次在各階段的加工設(shè)備和各設(shè)備上的爐次加工順序.第2階段將第1階段求得的可行解轉(zhuǎn)化為時(shí)間約束網(wǎng)絡(luò)圖,綜合考慮makespan、爐次等待時(shí)間和設(shè)備等待時(shí)間最小的目標(biāo),建立工藝路徑已知、加工順序已知、加工時(shí)間可控的煉鋼–精煉–連鑄調(diào)度問題的混合整數(shù)規(guī)劃模型,應(yīng)用優(yōu)化軟件(CPLEX)求解確定各工序的開始時(shí)間和加工時(shí)間.本文其余部分組織結(jié)構(gòu)如下:第2節(jié)給出了加工時(shí)間可控的煉鋼–精煉–連鑄調(diào)度問題的描述;第3節(jié)給出了SS算法和數(shù)學(xué)規(guī)劃算法相結(jié)合的兩階段優(yōu)化算法,詳細(xì)介紹了SS算法的基本算子的實(shí)現(xiàn)過程,并基于時(shí)間約束網(wǎng)絡(luò)圖建立了煉鋼–精煉–連鑄調(diào)度問題的混合整數(shù)規(guī)劃模型;第4節(jié)針對隨機(jī)生成測試案例和國內(nèi)某煉鋼廠生產(chǎn)實(shí)績數(shù)據(jù)的實(shí)驗(yàn)結(jié)果進(jìn)行對比分析;最后給出了本文的結(jié)論.2工件運(yùn)輸及加工調(diào)度煉鋼–精煉–連鑄調(diào)度可具體描述成如下混合flowshop調(diào)度問題:n個(gè)工件(爐次)j={1,···,n}分別要順序地通過煉鋼、精煉、連鑄生產(chǎn)階段加工工件j包含工序{O1j,O2j,···,Olmaxj},其中l(wèi)max為最大工序階段數(shù).在第l個(gè)生產(chǎn)階段有ml臺(tái)相同的設(shè)備可供選擇,同一工件在同一時(shí)間只能在一個(gè)設(shè)備上加工,同一設(shè)備在同一時(shí)間只能加工一個(gè)工件.工件j在煉鋼或精煉生產(chǎn)階段加工完成后,由運(yùn)輸設(shè)備運(yùn)輸?shù)较乱簧a(chǎn)階段的目的設(shè)備,如果目的設(shè)備被占用,則工件j需要等待直到目的設(shè)備空閑.工件在運(yùn)輸及等待設(shè)備的同時(shí)伴隨溫度下降和熱能損失煉鋼–精煉–連鑄生產(chǎn)過程要求鋼水溫度保持在一定的范圍,因此,工件在設(shè)備間運(yùn)輸及等待時(shí)間必須控制在一定的范圍內(nèi),即大于等于最小運(yùn)輸時(shí)間、小于等于最大允許溫降時(shí)間.如果當(dāng)前設(shè)備上的工件加工完成,下一個(gè)待加工的工件未到達(dá),會(huì)出現(xiàn)加工設(shè)備等待加工工件的現(xiàn)象,等待時(shí)間過長會(huì)明顯降低設(shè)備的利用率.在連鑄階段為了提高材料收得率、降低生產(chǎn)成本,要求屬于同一澆次的工件按給定順序在同一連鑄設(shè)備上連續(xù)加工,而且后繼工件必須在當(dāng)前工件完成加工前到達(dá)澆鑄工位.同一連鑄機(jī)加工的相鄰兩澆次間必須有一定的設(shè)置時(shí)間.由于存在各種不同程度的擾動(dòng)因素,為了保證連鑄加工階段的鋼水連續(xù)澆鑄,可以在一定的范圍內(nèi)調(diào)整工件在各生產(chǎn)階段的加工時(shí)間.調(diào)度任務(wù)是確定煉鋼、精煉階段各設(shè)備的加工工件集合、各設(shè)備上工件的加工順序和各工序的加工時(shí)間,使得makespan最小、工件等待時(shí)間和設(shè)備等待時(shí)間之和最小,從而降低生產(chǎn)能耗、提高設(shè)備利用率.3兩個(gè)階段優(yōu)化方法兩個(gè)階段的optimalalgoristm3.1ss算法的基本過程煉鋼–精煉–連鑄調(diào)度問題是集指派和排序特點(diǎn)的一類復(fù)雜的組合優(yōu)化問題,連鑄階段的連澆要求和傳擱時(shí)間的上下限約束增加了問題的求解難度.因此,本文設(shè)計(jì)了SS算法.SS算法由Glover于1977年提出的一種基于種群進(jìn)化的啟發(fā)式算法,一些學(xué)者已成功應(yīng)用于求解各類組合優(yōu)化問題和非線性規(guī)劃問題.SS算法的基本過程描述如下:1)生成初始種群,用于初始化參考集;2)選擇初始種群中的最優(yōu)解與多樣性解構(gòu)成參考解集;3)選擇參考集中的兩個(gè)或多個(gè)解構(gòu)成若干個(gè)子集;4)對子集中的解應(yīng)用組合算子,生成新解;5)應(yīng)用局域搜索算子提高新解的質(zhì)量并對參考集進(jìn)行更新.SS算法的基本組成部分包括:初始解生成方法、參考集更新方法、子集生成方法、組合算子、局域搜索算子.3.1.1階段l加工設(shè)備的任務(wù)根據(jù)SS算法屬于元啟發(fā)式算法的特性和第2節(jié)對煉鋼–精煉–連鑄調(diào)度問題的描述,本文采用整數(shù)編碼.記π=(π1,···,πl(wèi)max)表示調(diào)度問題的可行解,其中πl(wèi)={πl(wèi)1,···,πl(wèi)ml}表示階段l所有設(shè)備的加工序列,πl(wèi)i={πl(wèi)i(1),πl(wèi)i(2),···,πl(wèi)i(nli)}為階段l加工設(shè)備i的加工工序集合,其中πl(wèi)i(k)表示階段l機(jī)器i第k個(gè)位置加工的爐次.3.1.2初始解的生成在煉鋼–精煉–連鑄生產(chǎn)組織過程中,各爐次在連鑄階段的加工設(shè)備和加工順序是事先給定的.因此,本階段SS算法只需要根據(jù)在連鑄階段確定的爐次加工設(shè)備和加工順序來優(yōu)化各爐次在煉鋼、精煉生產(chǎn)階段的加工設(shè)備和加工順序.本文采用分階段倒序方式生成初始解.首先,根據(jù)設(shè)備平均利用率相等的原則,隨機(jī)生成精煉階段每臺(tái)設(shè)備的加工工序集.其次,根據(jù)連鑄階段各設(shè)備的加工工序集和加工順序倒推計(jì)算各爐次在連鑄階段的加工開始時(shí)間,將精煉設(shè)備的工序集按各爐次的開澆時(shí)間升序排列,得到精煉階段的加工順序.煉鋼階段各設(shè)備的加工工序集和加工順序可同樣得出.本文給出的初始解生成方法保證了各階段設(shè)備利用率均衡,同時(shí)使加工階段間的加工序列銜接緊密,減少了因等待設(shè)備引起的熱能損失.3.1.3初創(chuàng)期的加工工件集合組合算子是SS算法的基本組成部分,合理設(shè)計(jì)組合算子即可提高解的優(yōu)質(zhì)性又可保證解的多樣性.本文根據(jù)煉鋼–精煉–連鑄調(diào)度問題特點(diǎn)及編碼方式采用標(biāo)準(zhǔn)兩點(diǎn)順序交叉的方法.下面以精煉階段各設(shè)備加工工件集合的產(chǎn)生過程為例描述組合算子的基本流程.1)重組.以設(shè)備為單元,將精煉階段加工工件集合重組成長度為(n+ml)的一維數(shù)組,相鄰設(shè)備的加工工件集合間插入設(shè)備編號(hào)(n+i代表該加工階段的第i臺(tái)設(shè)備).重組過程如圖1所示.2)兩點(diǎn)順序交叉.隨機(jī)產(chǎn)生父代中的兩個(gè)交叉點(diǎn),交換兩點(diǎn)間的工件.從第2個(gè)交叉點(diǎn)后第1個(gè)基因起列出原順序,到達(dá)個(gè)體尾時(shí)返回頭繼續(xù),去掉已有基因,將獲得的無重復(fù)順序填入新個(gè)體.交叉過程如圖2所示.3)分解.順序交叉后產(chǎn)生的個(gè)體,根據(jù)設(shè)備編號(hào)對其進(jìn)行分解.連續(xù)找出子代個(gè)體中的兩個(gè)設(shè)備編號(hào)X,Y設(shè)備編號(hào)間的工件為設(shè)備Y-n的加工工件集.直到找到最后一個(gè)設(shè)備編號(hào).最后一個(gè)設(shè)備編號(hào)后的工件序列和第1個(gè)設(shè)備編號(hào)前的工件序列為第1個(gè)設(shè)備編號(hào)代表的設(shè)備的加工工件集合.下面以子代C2解碼過程進(jìn)行說明,如圖3所示.4)排序.對產(chǎn)生的精煉設(shè)備的加工工件集合按工件在連鑄階段加工開始時(shí)間進(jìn)行升序排序.如圖4所示.煉鋼階段解的產(chǎn)生方法類似.順序交叉較好地保留了相鄰關(guān)系、先后關(guān)系,滿足煉鋼–精煉–連鑄調(diào)度問題的需要.3.1.4u2004移動(dòng)v.解的生成局域搜索算子對初始種群中的解和組合算子產(chǎn)生的解進(jìn)行操作,通過搜索鄰域內(nèi)最優(yōu)解提高解的質(zhì)量.為了更好的描述局域搜索算子,引入文獻(xiàn)中的block概念.關(guān)鍵路徑包括lmax個(gè)子路徑,第l個(gè)子路徑包括從最小位置el到最大位置fl間的工件序列.即點(diǎn)的序列表示為(lmax,πl(wèi)maxhlmax(elmax)),···,(lmax,πl(wèi)maxhlmax(flmax))其中:πl(wèi)hl(fl)=πl(wèi)+1,hl+1(el+1)(l=1,···,lmax-1)表示相同工件在相鄰階段的加工.關(guān)鍵路徑上的第l個(gè)子路徑構(gòu)成了階段l上的一個(gè)block.bl是blockBl上的工件個(gè)數(shù),bl=|Bl|=fl-el+1,l=1,···,lmax.在本文的SS算法中,鄰域解是通過插入類型的移動(dòng)產(chǎn)生的.l為所選的生產(chǎn)階段,a,b表示該階段的兩個(gè)設(shè)備,x,y分別是向量πl(wèi)a,πl(wèi)b的位置變量.向量v=(l,a,x,b,y)表示移動(dòng)向量,具體表現(xiàn)為工件πl(wèi)a(x)從集合πl(wèi)a的第x個(gè)位置移走,然后插入到集合πl(wèi)b中的第y個(gè)位置.具體移動(dòng)形式如圖5所示.通過移動(dòng)v的作用,產(chǎn)生新的解πv.π的鄰域由一系列根據(jù)移動(dòng)v產(chǎn)生的πv構(gòu)成,即{πv:v∈V(π)},相應(yīng)的移動(dòng)集合其中:a,b=1,···,ml,x=1,···,nla,l=1,···,lmax,集合Vlaxb(π)包含的移動(dòng)為工件πl(wèi)a(x)從πl(wèi)a中的第x個(gè)位置移走,然后插入到序列πl(wèi)b所有可能的位置.為了提高鄰域的搜索速度,應(yīng)盡可能的剔除鄰域集合里一些對目標(biāo)值沒有改進(jìn)的解,根據(jù)文獻(xiàn)中給出的剔除無效移動(dòng)的規(guī)則,縮減后的移動(dòng)集合V(π)表示為對于階段l,縮減后的移動(dòng)集合Wlhlxb(π)?Vlhlxb(π),b∈Ml,x=el,···,fl(這里假設(shè)a=hl),則梯度權(quán)重表示爐次在連鑄和精煉設(shè)備上的加工順序的權(quán)重值,連鑄和精煉階段的梯度權(quán)重分別以澆次和設(shè)備為單位進(jìn)行梯度計(jì)算.如:π31={1,3,5,6},π32={2,4,7,8},澆次序列為{1,3},{5,6},{2,4},{7,8},則8個(gè)爐次的梯度權(quán)重為w3={1,1,2,2,9,10,9,10},同一設(shè)備加工的,屬于不同澆次的爐次權(quán)重值是按工件數(shù)n梯度增長的.定理1如果最大等待時(shí)間則在以makespan最小為優(yōu)化目標(biāo)的最優(yōu)解中,對于同一連鑄機(jī)加工的爐次,在精煉階段同一設(shè)備上的加工順序按澆鑄階段的梯度權(quán)重升序排列.證反證法.對于同一連鑄機(jī)加工的爐次,在精煉階段同一設(shè)備上的加工順序按澆鑄階段的梯度權(quán)重降序排列.1)爐次屬于同一梯度.同一梯度即表示兩個(gè)爐次屬于同一澆次.假設(shè)存在同一連鑄機(jī)上加工的連續(xù)兩爐次π31(j)=q1,π31(j+1)=q2,在精煉階段同一加工設(shè)備上,兩爐次的加工順序按梯度權(quán)重降序排列為π21(k)=q2,π21(k+1)=q1.根據(jù)同一澆次連澆的約束條件,q2的澆鑄開始時(shí)間s3,q2=s3,q1+p3,q1,q1在精煉階段的加工開始時(shí)間s2,q1s2,q2+p2,q2,那么q2的等待時(shí)間w3,q2p2,q1+p3,q1min{plj+pl+1,j}>W,與等待時(shí)間不能超過給定上限值的約束矛盾.2)爐次屬于不同梯度.不同梯度即表示兩個(gè)爐次屬于不同澆次.假設(shè)存在同一連鑄機(jī)上加工的連續(xù)兩爐次π31(j)=q1π31(j+1)=q2,且屬于不同澆次,在精煉階段同一加工設(shè)備上,兩爐次的加工順序按梯度權(quán)重降序排列為π21(k)=q2,π21(k+1)=q1.基于不同澆次間存在設(shè)置時(shí)間的約束,q2的澆鑄開始時(shí)間s3,q2=s3,q1+p3,q1+S.q1在精煉階段的加工開始時(shí)間s2,q1s2,q2+p2,q2,那么q2的等待時(shí)間w3,q2p2,q2+p3,q2+S>min{plj+pl+1,j}>W,與等待時(shí)間不能超過給定上限值的約束矛盾,故上面假設(shè)不成立.證畢.推論1如果最大等待時(shí)間則在以makespan最小為優(yōu)化目標(biāo)的最優(yōu)解中,對于同一精煉設(shè)備加工的爐次,在煉鋼階段同一設(shè)備上的加工順序按精煉階段的梯度權(quán)重升序排列.根據(jù)定理1和推論1,移動(dòng)產(chǎn)生的解必須保證按爐次的梯度權(quán)重升序排列,在縮減移動(dòng)集中剔除移動(dòng)后爐次按梯度權(quán)重降序排列的移動(dòng).梯度權(quán)重既保證了當(dāng)前階段的爐次順序與后繼階段同一設(shè)備爐次加工順序一致,減少了設(shè)備等待爐次時(shí)間和熱能損失,又可實(shí)現(xiàn)同一階段不同設(shè)備間爐次排列順序的任意性,保證了解的多樣性.3.2步驟2：確定工藝的初始加工時(shí)間和長期加工持續(xù)時(shí)間晚修時(shí)間：分散時(shí)間和加工持續(xù)時(shí)間3.2.1節(jié)點(diǎn)間時(shí)間約束關(guān)系第1階段求得的可行解可以轉(zhuǎn)換為一張時(shí)間約束網(wǎng)絡(luò)圖.以4個(gè)爐次3個(gè)生產(chǎn)階段,每個(gè)生產(chǎn)階段設(shè)置2個(gè)生產(chǎn)設(shè)備為例,應(yīng)用SS算法求解后,產(chǎn)生的可行解{{{1,2},{3,4}},{{3,2},{1,4}},{{1,2}{3,4}}},轉(zhuǎn)化為時(shí)間約束網(wǎng)絡(luò)后如圖6所示.圖6中節(jié)點(diǎn)代表各爐次的不同工序,其中節(jié)點(diǎn)0和節(jié)點(diǎn)*為虛工序,分別代表整個(gè)調(diào)度計(jì)劃的開始和結(jié)束.節(jié)點(diǎn)上面的數(shù)據(jù)代表對應(yīng)工序的[最小加工時(shí)間,最大加工時(shí)間]范圍,節(jié)點(diǎn)間的弧線代表各爐次不同工序間的時(shí)間約束關(guān)系,分為以下3種:1)同一設(shè)備不同工序間的時(shí)間約束關(guān)系,通過虛線弧連接表示,箭頭方向代表加工順序,對應(yīng)[0,+∞)時(shí)間約束,表示前一工序加工完成后下一工序才能開始.如圖6所示,工序O11,O12被分配在第1生產(chǎn)階段的同一臺(tái)設(shè)備上,加工順序?yàn)镺11→O12,則它們間存在虛線弧[0,+∞]連接.2)同一爐次的不同工序在不同生產(chǎn)階段上加工的時(shí)間約束關(guān)系,通過實(shí)線弧連接表示,對應(yīng)[t1,t2]時(shí)間約束,表示工件在上一設(shè)備加工完成后到下一設(shè)備開始的時(shí)間大于等于設(shè)備間的運(yùn)輸時(shí)間t1,小于等于最大等待時(shí)間t2,t2由加工溫度等工藝約束決定.如圖6所示,工件1的工序O11完成后要轉(zhuǎn)移到第2個(gè)階段的某臺(tái)設(shè)備上進(jìn)行工序O21,則它們間存在連接弧連接.3)連鑄階段同一設(shè)備上不同工序間的時(shí)間約束關(guān)系,通過實(shí)線弧連接表示,對應(yīng)[t1,t2]時(shí)間約束,表示上一工件加工完成后到下一工件到達(dá)的時(shí)間大于t1,小于等于t2,這里t1,t2由連鑄工藝約束決定.對于相同澆次的相鄰兩爐次,后繼爐次必須在前繼爐次加工完成前若干分鐘到達(dá).如圖6中的O31到O32間的時(shí)間約束,表示爐次2必須在爐次1加工完成前5分鐘到達(dá)該工位.不同澆次的相鄰兩爐次間有一定的設(shè)置時(shí)間間隔.3.2.2加工時(shí)間規(guī)定以下符號(hào):l:階段號(hào),l=1,···,lmax;j:工件編號(hào),j=1,···,n;Olj:工件j在階段l對應(yīng)的工序;C:同一爐次的工序間先后關(guān)系的弧集(實(shí)線弧集);D:不同爐次但被分配到同一設(shè)備的工序間先后關(guān)系的弧集(虛線弧集);:工序Olj的加工時(shí)間最小值;:工序Olj的加工時(shí)間最大值;:工序Olj完成至工序Ol+1,j開始的最小時(shí)間間隔即運(yùn)輸時(shí)間;:工序Olj完成至工序Ol+1,j開始的最大時(shí)間間隔即最大等待時(shí)間;Caj:工件j的澆次號(hào);S:相鄰澆次間的設(shè)置時(shí)間;Pr:同一澆次爐次間的準(zhǔn)備時(shí)間;plj:工序Olj的加工時(shí)間,為決策變量;tlj:工序Olj的開始加工時(shí)間,為決策變量.3.2.3最大等待時(shí)間其中:目標(biāo)函數(shù)(1)表示所有工件的最大完成時(shí)間最小;目標(biāo)函數(shù)(2)表示各爐次等待設(shè)備時(shí)間與設(shè)備等待爐次時(shí)間之和最小;約束式(3)表示同一爐次的相鄰工序間時(shí)間間隔大于運(yùn)輸時(shí)間小于最大等待時(shí)間;約束式(4)表示分配在同一設(shè)備上的兩個(gè)爐次不能同時(shí)加工;約束式(5)表示在連鑄階段同一澆次的相鄰兩爐次必須滿足連澆約束;約束式(6)表示在連鑄階段工件必須在加工開始時(shí)間前一給定時(shí)間內(nèi)到達(dá);約束式(7)表示連鑄階段屬于不同澆次的相鄰兩爐次間有一定的設(shè)置時(shí)間;約束式(8)表示決策變量的取值范圍.基于CPLEX不能求解多目標(biāo)問題的特點(diǎn),本文采用加權(quán)和的方式將上述給出的多目標(biāo)數(shù)學(xué)模型轉(zhuǎn)化為單目標(biāo).加權(quán)和的方法能充分體現(xiàn)不同鋼鐵企業(yè)對工件的完工時(shí)間、工件等待時(shí)間和設(shè)備等待時(shí)間的重視程度不同,即目標(biāo)的權(quán)重大小不一.4實(shí)驗(yàn)結(jié)束后的結(jié)果4.1l設(shè)備加工的工件集合的交叉實(shí)驗(yàn)中,為了比較SS算法和數(shù)學(xué)規(guī)劃方法相結(jié)合的兩階段算法對本文問題的求解性能,本文作者設(shè)計(jì)了遺傳局域搜索(geneticlocalsearch,GLS)算法和數(shù)學(xué)規(guī)劃算法相結(jié)合的求解算法.GLS算法采用與SS相同的編碼的方式.交叉算子采用單點(diǎn)交叉.當(dāng)滿足交叉概率時(shí),對父代個(gè)體的每一生產(chǎn)階段l(l=1,···,lmax)執(zhí)行如下的交叉過程:首先,將兩父代個(gè)體當(dāng)前生產(chǎn)階段l各設(shè)備加工的工件集合重組成長度為(n+ml)的一維數(shù)組;其次,隨機(jī)生成交叉點(diǎn),對兩父代個(gè)體重組后的排列執(zhí)行單點(diǎn)交叉過程;再次,對交叉后產(chǎn)生的新的工件和設(shè)備的排列,根據(jù)設(shè)備編號(hào)進(jìn)行分解得到各生產(chǎn)設(shè)備加工的工件集合;最后,對交叉產(chǎn)生的子代個(gè)體按后繼階段的開始時(shí)間進(jìn)行升序排列,即確定各設(shè)備加工工件的順序.當(dāng)滿足變異概率時(shí),對父代個(gè)體每一生產(chǎn)階段l(l=1,···,lmax)執(zhí)行如下的變異過程:首先,對階段l設(shè)備加工的工件集合進(jìn)行重組;其次,隨機(jī)生成兩個(gè)變異結(jié)點(diǎn)位置,對換變異位置的值.再次,執(zhí)行同交叉算子中相同的分解和排序過程.將交叉算子和變異算子產(chǎn)生的新個(gè)體插入到新種群,對其中的個(gè)體執(zhí)行3.1.4節(jié)的局域搜索算子.選擇算子采用最優(yōu)和輪盤賭方法,在產(chǎn)生的新種群與父代種群中優(yōu)先選擇最好的個(gè)體復(fù)制到下一代,其余個(gè)體采用輪盤賭方法產(chǎn)生.將GLS生成的最優(yōu)解應(yīng)用3.2節(jié)介紹的數(shù)學(xué)規(guī)劃方法進(jìn)行求解確定各工件的開始時(shí)間及加工時(shí)間.4.2u3000計(jì)算公式和算法參數(shù)設(shè)置煉鋼–精煉–連鑄調(diào)度問題沒有標(biāo)準(zhǔn)的測試數(shù)據(jù),本文分別采用國內(nèi)某煉鋼廠生產(chǎn)實(shí)績數(shù)據(jù)和根據(jù)生產(chǎn)實(shí)績數(shù)據(jù)隨機(jī)生成的測試案例對模型及兩階段算法進(jìn)行測試.該煉鋼廠煉鋼、精煉、連鑄階段各有2臺(tái)加工設(shè)備,煉鋼與精煉間的傳擱時(shí)間取自區(qū)間,精煉與連鑄的傳擱時(shí)間為內(nèi)一定值.隨機(jī)生成案例參數(shù)設(shè)置:設(shè)各工件的最大等待時(shí)間均相等即dmaxlj,l+1j=20min,j=1,···,n,l=1,···,lmax-1,設(shè)置時(shí)間S=5min準(zhǔn)備時(shí)間Pr=3min.工件在各生產(chǎn)階段的最大最小加工時(shí)間在表1給出的區(qū)間內(nèi)隨機(jī)產(chǎn)生,不同工件的加工時(shí)間區(qū)間[最小加工時(shí)間,最大加工時(shí)間]不同,可全面的測試本文給出的兩階段算法和數(shù)學(xué)模型優(yōu)化效果和時(shí)間效率.根據(jù)每一澆次包含的爐次數(shù)以10為界,生成不同規(guī)模的兩組測試案例:工件數(shù)n1={32,48,54}n2={45,66}.設(shè)備組合m1*m2*m3={2*2*2,3*3*2,3*3*3,3*4*3,3*5*3,3*6*3},組合后的測試案例分別為({2*2*2,3*3*2}),({32,45,54}),({3*3*3,3*4*3,3*5*3,3*6*3}),({48,66}),除工件數(shù)n1=54,每臺(tái)連鑄機(jī)加工3個(gè)澆次外,其余案例中每臺(tái)連鑄機(jī)包含2個(gè)澆次,則一共生成14個(gè)測試案例.SS算法參數(shù)設(shè)置如下:算法的終止條件為最大迭代代數(shù)maxIter=100或最優(yōu)解的目標(biāo)值連續(xù)30代沒有變化,初始種群P的大小為100,參考集規(guī)模b=10.在實(shí)驗(yàn)中,GLS算法參數(shù)設(shè)置如下:算法的終止條件為最大迭代代數(shù)為100或最優(yōu)解的目標(biāo)值連續(xù)30代沒有變化,種群大小為20,單點(diǎn)交叉概率為0.85,變異概率為0.1.4.3cbd的等待時(shí)間本節(jié)主要對第1階段應(yīng)用SS算法和第2階段應(yīng)用CPLEX求解的等待時(shí)間進(jìn)行對比分析.SS算法中工件在當(dāng)前階段加工完成后馬上運(yùn)輸?shù)较乱浑A段進(jìn)行加工,即工件開始時(shí)間僅考慮當(dāng)前工件的等待時(shí)間最小,未從全局角度考慮多個(gè)工件間的相互協(xié)調(diào).CPLEX求解階段基于SS算法給出的工件加工設(shè)備和工件加工順序,利用加工時(shí)間可控性的特點(diǎn),綜合考慮工件間的相互協(xié)調(diào)以進(jìn)一步降低工件的等待時(shí)間和設(shè)備等待時(shí)間.記第1階段SS求得的最優(yōu)解對應(yīng)的等待時(shí)間為W1,第2階段采用CPLEX計(jì)算的等待時(shí)間為W2,表中比值CPLEX求得的等待時(shí)間與SS算法求得的等待時(shí)間的比值小說明兩點(diǎn):1)爐次等待設(shè)備時(shí)間少,即因爐次等待引起的熱能損失少;2)設(shè)備等待爐次時(shí)間少,即各加工階段的設(shè)備利用率高.實(shí)驗(yàn)中應(yīng)用兩階段算法對每個(gè)測試案例求解10次,統(tǒng)計(jì)每個(gè)實(shí)例每次的等待時(shí)間比值,以及10次比值的平均值.統(tǒng)計(jì)結(jié)果如表2所示.根據(jù)表2可以得出以下結(jié)論:1)相同設(shè)備組合下,隨著工件數(shù)的增多,SS階段和CPLEX階段的最優(yōu)解對應(yīng)的等待時(shí)間比值增大.如設(shè)備組合為2*2*2時(shí),工件數(shù)n=32的等待時(shí)間比值的平均值明顯比n=45的平均比值小.2)等待時(shí)間比值與每臺(tái)連鑄機(jī)上加工的澆次數(shù)量有關(guān),澆次數(shù)越多等待時(shí)間比值越大.設(shè)備組合為2*2*2時(shí),對2個(gè)澆次n=32的測試案例和3個(gè)澆次n=54的實(shí)例進(jìn)行比較,后者等待時(shí)間比值比前者明顯大很多.3)連鑄階段設(shè)備數(shù)相同時(shí),等待時(shí)間比值與煉鋼和精煉設(shè)備的數(shù)量成反比關(guān)系.如n=32時(shí),設(shè)備組合3*3*2的等待時(shí)間比值比設(shè)備組合2*2*2的等待時(shí)間比值大.4)對于煉鋼和連鑄設(shè)備數(shù)相等的情況下,精煉設(shè)備越多等待時(shí)間比值越大.當(dāng)n=48時(shí),等待時(shí)間比值依m(xù)2=3,4,5,6呈遞增趨勢.因此,等待時(shí)間與工件數(shù),澆次數(shù)和各階段的加工設(shè)備數(shù)有關(guān).從對等待時(shí)間的優(yōu)化效果的角度考慮,CPLEX的求解結(jié)果更能達(dá)到減少爐次等待時(shí)間和設(shè)備等待時(shí)間的目的.4.4連鑄機(jī)運(yùn)行優(yōu)化本節(jié)對應(yīng)用兩階段優(yōu)化算法求解的某鋼廠生產(chǎn)計(jì)劃的結(jié)果與生產(chǎn)實(shí)績數(shù)據(jù)進(jìn)行對比分析.實(shí)驗(yàn)結(jié)果如表3所示,其中castsize給出了生產(chǎn)計(jì)劃中每臺(tái)連鑄機(jī)加工的澆次數(shù)和每個(gè)澆次包含的爐次數(shù),如{{15,11},{10,13}}表示每臺(tái)連鑄機(jī)各加工2個(gè)澆次,第1臺(tái)連鑄機(jī)的第1個(gè)澆次包含15個(gè)爐次JWT,MWT分別表示爐次等待設(shè)備時(shí)間和設(shè)備等待爐次時(shí)間.根據(jù)表3可以得出以下結(jié)論:1)本文給出的兩階段優(yōu)化算法對爐次等待設(shè)備時(shí)間和設(shè)備等待爐次時(shí)間的優(yōu)化效果明顯好于某鋼鐵企業(yè)的生產(chǎn)實(shí)績.加工時(shí)間可控的特性充分保證了減少爐次等待設(shè)備的時(shí)間,即減少了因等待引起的熱能損失.2)爐次等待設(shè)備時(shí)間的上下限約束使得JWT明顯小于MWT,即嚴(yán)格保證了爐次等待設(shè)備時(shí)間最小的優(yōu)化目標(biāo).3)兩階段算法對makespan的優(yōu)化效果要優(yōu)于生產(chǎn)實(shí)績.因此,本文給出的兩階段求解算法和模型適合應(yīng)用于鋼廠生產(chǎn)實(shí)際.4.5算法性能分析基于不同工廠對爐次等待設(shè)備時(shí)間和設(shè)備等待爐次時(shí)間的側(cè)重不同,本文設(shè)置爐次等待設(shè)備時(shí)間的權(quán)重a和設(shè)備等待爐次時(shí)間的權(quán)重b取3組數(shù)據(jù),分別為(1)a=0.3,b=0.7,(2)a=0.6b=0.4,(3)a=0.8,b=0.2.實(shí)驗(yàn)中對生成的14個(gè)測試案例應(yīng)用兩階段優(yōu)化算法求解10次,給出了每個(gè)實(shí)例10次求解結(jié)果的平均目標(biāo)值、平均運(yùn)行時(shí)間、兩階段最優(yōu)解的目標(biāo)值間比值的平均值以及等待時(shí)間比值的平均值,分別表示為avgObjavgCPU,avgPerO,avgPerW.本節(jié)實(shí)驗(yàn)同時(shí)統(tǒng)計(jì)了應(yīng)用GLS與數(shù)學(xué)規(guī)劃方法相結(jié)合的求解算法在爐次等待設(shè)備和設(shè)備等待爐次不同權(quán)重組合下的求解性能.設(shè)SSH表示應(yīng)用SS與數(shù)學(xué)規(guī)劃方法相結(jié)合的求解算法,GLSH表示應(yīng)用GLS與數(shù)學(xué)規(guī)劃算法相結(jié)合的求解算法.統(tǒng)計(jì)結(jié)果如表4所示.分析不同爐次等待時(shí)間、設(shè)備等待時(shí)間權(quán)重對SS和數(shù)學(xué)規(guī)劃方法相結(jié)合求解算法性能的影響根據(jù)表4可以得出以下結(jié)論:1)隨著爐次等待設(shè)備時(shí)間權(quán)重的增加及設(shè)備等待爐次時(shí)間權(quán)重的減少,SSH求得的平均目標(biāo)值、平均等待時(shí)間比值和平均目標(biāo)值比值減少.當(dāng)n=32,設(shè)備組合為2*2*2時(shí),等待時(shí)間權(quán)重a=0.3,b=0.7的平均目標(biāo)值、等待時(shí)間比值和目標(biāo)時(shí)間比值明顯比a=0.6,b=0.4和a=0.8,b=0.2的大.2)SSH算法平均運(yùn)行時(shí)間隨爐次等待設(shè)備時(shí)間權(quán)重的增大而增大.當(dāng)n=66,設(shè)備組合為3*3*3時(shí),SSH算法平均運(yùn)行時(shí)間依a=0.3,b=0.7a=0.6,b=0.4和a=0.8,b=0.2順序增大.3)相同等待時(shí)間權(quán)重下,工件數(shù)相同的測試案例,隨著設(shè)備數(shù)的增大平均目標(biāo)值減少.充分說明了在給定的等待時(shí)間權(quán)重下,完成時(shí)間隨著設(shè)備數(shù)的增大而減少.如n=32,設(shè)備組合分別為3*3*3,3*