基于遺傳算法的合同計劃編制模型

基于遺傳算法的合同計劃編制模型

1日、日合同計劃的管理今天，鋼鐵工業(yè)的主要特點是，它不僅要在不同的條件下確保生產(chǎn)的連續(xù)性，還要滿足對產(chǎn)品質(zhì)量和按時交付的要求。在實現(xiàn)這一目標(biāo)的過程中，合同計劃是各生產(chǎn)過程中的一個重要組成部分，它決定了生產(chǎn)能否在不同條件下成功完成。鋼廠生產(chǎn)計劃主要包括年計劃、月計劃、合同計劃和日生產(chǎn)計劃.年計劃主要進(jìn)行全廠范圍內(nèi)的能力平衡,作為資源計劃的依據(jù),用于指導(dǎo)定貨;月計劃對設(shè)備的生產(chǎn)能力進(jìn)行核定、預(yù)報;合同計劃根據(jù)客戶的定貨要求和設(shè)備的生產(chǎn)能力,安排合同的生產(chǎn),提出材料申請,從而指導(dǎo)日生產(chǎn)計劃的編制;日生產(chǎn)計劃根據(jù)合同計劃,考慮各機(jī)組的生產(chǎn)工藝規(guī)程,對生產(chǎn)進(jìn)行具體的調(diào)度.在市場經(jīng)濟(jì)環(huán)境下,合同計劃是體現(xiàn)以銷定產(chǎn)的生產(chǎn)計劃,它的主要任務(wù)是根據(jù)合同的交貨期、各生產(chǎn)工序上機(jī)組的生產(chǎn)能力等來安排一個合同的生產(chǎn)周期,即確定每道工序的生產(chǎn)時間.在合同計劃編制中,要考慮各工序的生產(chǎn)能力和需要生產(chǎn)的合同(時間、數(shù)量、質(zhì)量)的要求,保證整條生產(chǎn)線的順利生產(chǎn).國內(nèi)外學(xué)者對鋼廠合同計劃的編制進(jìn)行了許多研究,C.N.Redwine和D.A.Wismer應(yīng)用混合整數(shù)規(guī)劃模型來解決軋鋼廠合同計劃問題,目標(biāo)為最小化合同總拖期,引進(jìn)了拖期懲罰表,但文中未考慮過早完成合同而增加的成本,懲罰表只能表示合同重要性,而不能完全決定合同的優(yōu)先權(quán),因此不一定獲得最佳經(jīng)濟(jì)效益.滕學(xué)等人對鋼管廠熱軋機(jī)組的生產(chǎn)過程進(jìn)行了分析,建立了合同分配模型,并進(jìn)行了優(yōu)化分析和實驗,優(yōu)于人工作業(yè).但未給出成熟的模型和算法,最小時間單位選擇為月是偏大的.本文通過對鋼廠生產(chǎn)過程的分析,提出了合同計劃的一種數(shù)學(xué)模型和算法,研究工作包括三個部分:1)以半旬為最小時間單位,最小化全部合同的提前和拖期總懲罰為目標(biāo),建立了合同計劃編制的整數(shù)規(guī)劃模型;2)提出基于可重復(fù)自然數(shù)編碼和三變異算子的遺傳算法對模型求解;3)通過實驗驗證模型和算法的有效性.2合同計劃的數(shù)學(xué)模型方法2.1合同計劃和能力合同計劃的編制可以概述如下:假設(shè)有N個合同、M道工序,每個合同的重量、交貨期及其生產(chǎn)路徑(通過的工序和在每道工序可使用的機(jī)器(不唯一))已知,每個合同通過的工序相同,每臺機(jī)器的能力一定,合同計劃是在滿足能力約束和前序關(guān)系的前提下,安排每個合同在每道工序通過的機(jī)器和通過的時間,使所有合同的提前和拖期總懲罰最小.(每個合同必須通過所有工序,在每一工序必須且僅能在一臺機(jī)器上加工,且同時最多只能在一臺機(jī)器上生產(chǎn),一臺機(jī)器同時最多只能生產(chǎn)一個合同.)2.2合同提前、拖期總懲罰的模型如果對每種產(chǎn)品都只考慮大工序,其加工路徑確定,這是一般的flowshop(FS)問題,問題相對簡單;如果考慮某些品種在某工序有多于一臺的并行機(jī)可供選擇時,則是一類flexible(柔性)flowshop(FFS)問題,問題變得復(fù)雜得多.1973年,Salvador基于石油化工的工業(yè)背景首次定義了FFS問題,它是一般FS問題推廣.本文的合同計劃問題是一類FFS問題,不同的是本文的合同計劃只對合同安排其加工的時間段,而不對該時間段內(nèi)的合同排序.本模型中合同的交貨期和生產(chǎn)時間段以半旬為單位,目標(biāo)函數(shù)為所有合同的提前和拖期總懲罰最小.對于各工序,假設(shè)1)每道工序中每臺機(jī)器的每半旬總能力己知;2)每道工序的各臺機(jī)器相同,假設(shè)某合同,對于不同機(jī)器,其虛擬生產(chǎn)量不同,從而表示機(jī)器的不同性;3)各合同在各工序的通過時間(從進(jìn)入一工序到本工序完成的時間)小于一個半旬,同一合同的多道工序可在同一半旬中完成;4)不單獨考慮中間庫存.為了便于表示,建立以下數(shù)學(xué)符號:N——合同總數(shù);M——工序數(shù);T——計劃周期;[di-ui,di+vi]——交貨期窗口(以半旬為單位)(已知);tij——第i個合同在第j道工序的開工半旬;ei——合同i的實際合同量(已知);eijk——合同i在工序j的第k機(jī)器上的虛擬生產(chǎn)量(已知);ci——合同i的完工半旬,即最后一道工序的通過時間(半旬);Ejkt——工序j的機(jī)器k在t半旬的總能力(已知).xtjkt={1?合同i在半旬t內(nèi)在?序j的第k機(jī)器上加??0?否則?xtjkt={1?合同i在半旬t內(nèi)在?序j的第k機(jī)器上加??0?否則?其中:xijkt為決策變量,i表示合同號(i=1,…,N),j表示工序號(j=1,…,M),k表示j工序中的機(jī)器號(k=1,…,M),t表示時間段(t=1,…,T).建立數(shù)學(xué)模型如下:其中,αi是合同i的提前懲罰系數(shù),βi是合同i的拖期懲罰系數(shù).目標(biāo)(1)是最小化所有合同的提前—拖期總懲罰值;約束(2)保證每個合同必須通過每一工序,在每一工序必須且僅能在一臺機(jī)器上加工;約束(3)保證每半旬某機(jī)器所加工合同的合同量總和不能超過此機(jī)器的總加工能力(能力約束);約束(4)表示合同i在工序j的開工時間(半旬)不小于在工序j-1的開工時間;(5)表示決策變量的取值范圍.3合同計劃算法algorithmoffer代理3.1遺傳算法使用的原因已經(jīng)證明,FFS是NP-難問題.從本文模型可以看出,該合同計劃模型是一個非線性0-1整數(shù)規(guī)劃模型,由于變量維數(shù)比較多,目標(biāo)函數(shù)的非線性增加了計算的復(fù)雜性,用精確算法在可行時間內(nèi)難以求解.遺傳算法已經(jīng)廣泛用于TSP,flow-shop等各種組合優(yōu)化問題雖然遺傳算法不能使搜索空間減小,但由于群體搜索的并行性使它能在較短的時間內(nèi)搜索較大的空間,所以本文決定使用遺傳算法.1工序j的機(jī)器k的通過段本文采用可重復(fù)自然數(shù)編碼,設(shè)計染色體的基因aijk:A={aijk}?A={aijk}?這里,i=1,…,N,j=1,…,M,k=1,…,Mj,aijk表示合同i在工序j的機(jī)器k的通過時間段.其中,我們稱{ai11,ai12,…,ai1M1,…,aiM2,…,aiMMM}為大段,稱大段中的AiMj{aij1,aij2,…,aijMj}為小段,每一小段內(nèi)只有一個基因不為0(基因為0表示此合同不在此機(jī)器上加工),這種編碼方式保證了約束(2)的可行性.不為0基因的數(shù)值取一時間值,同一個大段內(nèi)其取值范圍為1到(T+td)的自然數(shù)(詳見2)),且各小段之間必須滿足約束(4);不同大段之間其數(shù)值可以重復(fù).完工半旬ci就是相應(yīng)第i大段的第M小段中不為0的值.2s12,a1mm—)初始種群.根據(jù)上述染色體編碼的要求,采用隨機(jī)的方式產(chǎn)生初始種群L個染色體.①由于產(chǎn)生一個染色體中的每個大段的方法相同,這里先產(chǎn)生一個大段{a111,a112,…,a11M1,…,a1M1,a1M2,a1MM}.首先,產(chǎn)生一個從1到M1的隨機(jī)整數(shù)k11,作為不為0的元素號,再產(chǎn)生一個從1到T+td的隨機(jī)整數(shù),作為此元素a11k11的值,這樣就產(chǎn)生了第一個小段;然后,產(chǎn)生一個從1到M2的隨機(jī)整數(shù)k12,作為不為0的元素號,再產(chǎn)生一個從a11k11到T+td的隨機(jī)整數(shù),作為此元素a12k12的值,于是第二個小段被產(chǎn)生;依次類推,直到產(chǎn)生一個大段;(這里T+td是為了考慮合同的拖期,td是一個輔助計算的整數(shù))②重復(fù)①的方法再分別產(chǎn)生這個染色體中的其它大段,于是隨機(jī)產(chǎn)生了一個染色體;③重復(fù)①和②的方法,再分別產(chǎn)生L-1個染色體.3離idl的復(fù)制設(shè)對于種群中的第l個染色體有目標(biāo)函數(shù):Fl=∑i=1Nei(aimax{0,di?ui?ci}+βimax{0,ci?di?vi}).(6)Fl=∑i=1Νei(aimax{0,di-ui-ci}+βimax{0,ci-di-vi}).(6)為了限制不滿足約束(3)的染色體在新一代種群中的比例,特設(shè)計用于復(fù)制的選擇函數(shù).定義每個染色體對約束(3)的可行距離IDl,用以表征染色體l的非可行程度:IDl=∑j=1M∑k=1Mj∑t=1Tmax{(∑i=1Nxijkteijk?Ejkt),0},(7)ΙDl=∑j=1Μ∑k=1Μj∑t=1Τmax{(∑i=1Νxijkteijk-Ejkt),0},(7)則用于復(fù)制的選擇函數(shù)fl為:fl=C?Fl?γIDl?(8)fl=C-Fl-γΙDl?(8)其中,令C=maxl∈Q{Fl+γ∑j=1M∑k=1Mj∑t=1Tmax{(∑i=1Nxijkteijk?Ejkt),0}}+λ,(9)C=maxl∈Q{Fl+γ∑j=1Μ∑k=1Μj∑t=1Τmax{(∑i=1Νxijkteijk-Ejkt),0}}+λ,(9)Q={1,2,…,L}——種群集合,L——種群規(guī)模,γ——約束(3)的不可行懲罰系數(shù),λ——適當(dāng)?shù)恼麛?shù).本算法采用滾輪盤的方式進(jìn)行復(fù)制,復(fù)制的選擇概率由如下(10)式獲得.Pl=fl∑a=1Lfa?l=1,2,?,L.(10)Ρl=fl∑a=1Lfa?l=1,2,?,L.(10)可以看出,如果C值僅設(shè)為一個較大的常數(shù),當(dāng)各染色體目標(biāo)值數(shù)值不太大,而它們的值相差很大時,得到的fl值就掩蓋了各染色體的質(zhì)量差別,因此,本算法在復(fù)制時,C值設(shè)置為(9)式產(chǎn)生的變量.4erpsc按交叉概率Pc,進(jìn)行部分段交叉partsectioncrossover(PSC),即把兩個染色體a和b在兩個隨機(jī)位置間的所有大段進(jìn)行交換(相應(yīng)小段只交換不為0的值,而原不為0的值的位置不變).由于交叉操作以大段為單位,在對應(yīng)小段之間進(jìn)行,因此染色體始終保證滿足約束(2)和(4).5系統(tǒng)實驗方法由于每個染色體中存在大段和小段,用普通的變異算子不能完成計算過程,為了保證搜索的全局性和滿足約束(2)和(4)的可行性,采用三變異算子,構(gòu)成一次變異操作.對染色體中不為0值的基因的位置及數(shù)值進(jìn)行變換.在各變異中同時完成對變異后新染色體的擇優(yōu),按如下適值函數(shù):fl′=C′?Fl?γ∑j=1M∑k=1Mj∑t=1Tmax{(∑Xijkteijk?Ejkt),0}?(11)fl′=C′-Fl-γ∑j=1Μ∑k=1Μj∑t=1Τmax{(∑Xijkteijk-Ejkt),0}?(11)其中,C′為一足夠大的常數(shù).變異一:大段間變異.以大段為單位,根據(jù)變異概率Pm1,在染色體A′={B1,B2,…,BN}的大段Bi間進(jìn)行2交換變異.具體步驟如下:①從種群的第1個染色體開始,a=1;②隨機(jī)產(chǎn)生從0到1的小數(shù),如果此小數(shù)不大于Pm1,則此染色體進(jìn)行變異,轉(zhuǎn)③;否則,轉(zhuǎn)④;③從此染色體中的第一個大段開始,分別把每兩個大段進(jìn)行交換(相應(yīng)小段只交換不為0的值,而原不為0的值的位置不變),比較每個交換所得到的新染色體的適應(yīng)值,選擇一個最好的交換.如果按此最好交換產(chǎn)生的新染色體的適應(yīng)值大于原染色體,則用此新染色體代替原染色體;否則,不接受新染色體.然后,進(jìn)行小段內(nèi)變異(變異二),再進(jìn)行大段內(nèi)變異(變異三).然后轉(zhuǎn)④.④如果a<L,則a=a+1,轉(zhuǎn)②;否則,結(jié)束.變異二:小段內(nèi)變異.設(shè)染色體A′={B1,B2,…,BN}=A.其中Bi={ai11,ai12,…,ai1M1,…,aiM1,aiM2,…,aiMMM}為第i大段.大段Bi={Si1,Si2,…,SiM},小段Sij={aij1,aij2,…,aijMj},根據(jù)變異概率Pm2,在某染色體的每個Sij內(nèi)的基因間進(jìn)行2交換變異.具體步驟如下:①對此染色體,設(shè)小段j=1;②隨機(jī)產(chǎn)生從0到1的小數(shù),如果此小數(shù)不大于Pm2,則此段進(jìn)行變異,轉(zhuǎn)③;否則,轉(zhuǎn)④;③把不為0的數(shù)分別放在其它Mj-1個位置上,比較交換后的Mj-1種結(jié)果的適應(yīng)值,選擇一個最好的交換.如果按此最好交換產(chǎn)生的新染色體的適應(yīng)值大于原染色體,則用此新染色體代替原染色體;否則,不接受新染色體.然后轉(zhuǎn)④.④如果j<M,則j=j+1,轉(zhuǎn)②;否則,結(jié)束.變異三:大段內(nèi)變異.①對此染色體,設(shè)大段i=1;②隨機(jī)產(chǎn)生從0到1的小數(shù),如果此小數(shù)不大于Pm3,則此大段進(jìn)行變異,轉(zhuǎn)③;否則,轉(zhuǎn)④;③重新隨機(jī)產(chǎn)生元素值,即產(chǎn)生一個從1到T+td的隨機(jī)整數(shù),作為元素ai1ki1的值,然后,再產(chǎn)生一個從ai1ki1到T+td的隨機(jī)整數(shù),作為元素ai2ki2的值,依次類推,直到產(chǎn)生一個大段{ai11,ai12,…,ai1m1,…,aiM1,aiM2,…,aiMMM}(原不為0的值的位置不變).如果按此方法產(chǎn)生的新染色體的適應(yīng)值大于原染色體,則用此新染色體代替原染色體;否則,不接受新染色體.然后轉(zhuǎn)④;④如果i<N,則i=i+1,轉(zhuǎn)②;否則,結(jié)束.3.2快速支持的適應(yīng)函數(shù)設(shè)計綜上所述,本算法對傳統(tǒng)的遺傳算進(jìn)行了一些改進(jìn):1)采用可重復(fù)自然數(shù)編碼,滿足了約束(2)和約束(4)的可行性.2)提出三變異算子,構(gòu)成一次變異操作,有效地完成整個變異過程.3)算法的整個過程始終保證約束(2)和(4)的可行性.4)為了滿足計算的需要,把用于復(fù)制的函數(shù)和用于評價的適應(yīng)函數(shù)區(qū)分開來,對于不同迭代數(shù)下的種群,(8)式中的C為一個變量,無論染色體如何變化,(8)式都能體現(xiàn)出各染色體的質(zhì)量差別,保證了復(fù)制的有效進(jìn)行.5)適應(yīng)性函數(shù)設(shè)計為(11)式,同時考慮模型的目標(biāo)函數(shù)及約束(3)的可行距離,擇優(yōu)選擇時選取目標(biāo)函數(shù)和可行距離均較小的解,并未拒絕可行距離不為0的解進(jìn)入新一代,這是搜索的內(nèi)點法和外點法的結(jié)合,既從不可行解向可行解的方向搜索(外點法),又從質(zhì)量差的可行解向質(zhì)量好的可行解搜索(內(nèi)點法),這保證了搜索的全局性.整個算法流程如圖1.4算法的有效性驗證由于熱軋帶鋼產(chǎn)品在合同訂貨中占極其重要的地位,因此我們以上海寶山鋼鐵公司熱軋廠合同計劃為例來測試本文的模型與算法.熱軋廠工藝流程緊密銜接,所涉及的生產(chǎn)工序包括煉鋼—精煉—連鑄—熱軋—精整.帶鋼的加工過程包括煉鋼—精煉—連鑄—熱軋—精整五道工序,由于對于每個合同,其規(guī)格的帶鋼通過煉鋼工序后需經(jīng)過何種精煉(即通過哪臺精煉工位)是固定的,因此可以把煉鋼和精煉看作一道工序.另外,由于工藝要求,每種產(chǎn)品在經(jīng)過煉鋼或精煉后必須立刻進(jìn)入連鑄機(jī),如不考慮連鑄機(jī)的選擇,把煉鋼—精煉—連鑄抽象為一道工序,這樣,原來的五道工序就可以簡化為煉鋼(+精煉+連鑄)—熱軋—精整三道工序,其中只考慮精整工序中有并行機(jī).在寶鋼實際生產(chǎn)中,計劃員一般需掌握兩個月的合同,即從兩個月的合同中選取合同來編制計劃,因