基于相關(guān)機會目標規(guī)劃的鋼板切割分配建模

張永全,徐克林,孫 禹

(同濟大學 機械工程學院, 上海201804)

造船業(yè)是一個國家經(jīng)濟和技術(shù)實力的重要體現(xiàn).近年來,我國造船業(yè)發(fā)展迅速,2008 年,全國造船產(chǎn)量已達2 .881 ×107載重噸, 占全球市場份額29 .5 %,居世界第3 位[1].但是, 我國造船效率與國際先進船廠相差巨大,骨干船廠生產(chǎn)效率只有日本、韓國的1/3～1/4[2].因此, 我國要成為造船強國, 必須提高造船效率.

目前, 造船業(yè)競爭的焦點已由規(guī)模轉(zhuǎn)向核心競爭力.鋼板切割是船廠的核心競爭力之一, 也是影響造船效率的一個重要因素.為了提高鋼板的利用率,國內(nèi)外對鋼板排樣、套料進行了深入的研究[3-6],分析了利用率和規(guī)格之間的關(guān)系[7];為了提高切割效率,對劃線、切割路徑等進行了優(yōu)化[4,8-9],將成組技術(shù)與調(diào)度規(guī)則結(jié)合起來[10];為了實現(xiàn)準時制生產(chǎn),采用多目標柔性作業(yè)車間調(diào)度技術(shù)實現(xiàn)多機工作負荷分配[11-12].然而, 對于供給不確定情況下如何在不同的切割機上分配待切割的鋼板的研究較少.本文假設在鋼板排樣、劃線、切割路徑等都已經(jīng)確定情況下,利用相關(guān)機會目標規(guī)劃對多個不確定鋼板供給端向多個數(shù)控切割機分配切割任務, 以滿足生產(chǎn)的有序性和多目標要求.

1 鋼板切割的供給-分配系統(tǒng)

某船廠預處理后的鋼板主要通過3 種途徑供給4 臺不同的數(shù)控切割機(CNC)進行切割:①地面堆放;②平板車存放;③臨時抽板, 其供給與分配情況如圖1 所示, 圖中,x1～x4 分別為平板車存放供給CNC1～CNC4 的鋼板量;x5～x8分別為地面堆放供給CNC1～CNC4 的鋼板量;x9和x10分別為臨時抽板供給CNC3 和CNC4 的鋼板量.按照生產(chǎn)計劃,在班前將每天要切割的鋼板放置于地面和平板車上,如果出現(xiàn)生產(chǎn)遺漏、設計變更等需要補料和插單情況,則按臨時抽板處理, 并在班后統(tǒng)計3 種供給量.受鋼板厚度、前道工序及生產(chǎn)準備影響,這3 種供給量每天都是不確定的, 無法準確按照生產(chǎn)要求順序供給和逆序碼放.因此,該鋼板切割供給-分配系統(tǒng)是一種典型的隨機任務分配問題.

圖1 鋼板切割的供給-分配示意Fig .1 Supply-distribution illustration of steel plate cutting

由于鋼板切割過程中大量的并行作業(yè)彼此穿插、相互影響,人員、設備、物料投入密集, 復雜程度高、控制難度大[1],作業(yè)時間變動范圍廣, 無法在較低成本下精確按照多目標柔性作業(yè)調(diào)度方案進行切割任務分配, 只能根據(jù)作業(yè)人員的經(jīng)驗向數(shù)控切割機分配鋼板.而人為分配具有很大的隨機性, 經(jīng)常造成關(guān)鍵設備利用率不高及生產(chǎn)混亂情況, 同時, 這種隨機性還會造成鋼板搬運任務增加, 場地占用長久等, 使物流成本升高, 甚至會造成鋼板積壓、生產(chǎn)不暢、交貨延遲等現(xiàn)象,降低了船廠的競爭力.通常認為造成這種現(xiàn)象的源頭在于鋼板供給端的不確定性, 是不能控制和消除的, 以至于嚴控臨時抽板量.因此, 必須尋求一種介于完全隨機分配和多目標柔性精確分配之間的分配策略, 在維持生產(chǎn)有序進行狀態(tài)下挖掘切割潛力, 滿足生產(chǎn)的多目標要求.

2 相關(guān)機會目標規(guī)劃

2.1 求解隨機任務分配問題的方法

通常情況下, 求解隨機任務分配問題的方法有3 種[13].

(1)從期望值的角度出發(fā), 用函數(shù)的期望值分別代替原來目標函數(shù)和約束條件中的不確定函數(shù),建立期望值模型.

(2)從機會測度的角度出發(fā),由于必須在觀測到約束條件中的隨機變量實現(xiàn)之前決策,故允許決策在一定程度上不滿足約束條件, 只要求其機會測度不小于給定的置信水平, 建立機會約束規(guī)劃模型[14].

(3)從極大化事件實現(xiàn)的機會出發(fā), LIU 提出了相關(guān)機會規(guī)劃理論[15].該理論用不確定環(huán)境取代可行集,使事件的機會函數(shù)在不確定環(huán)境下達到最優(yōu),即極大化隨機事件成立的機會[16].

在期望值模型和機會約束規(guī)劃中, 對實際問題建模后,其可行集本質(zhì)上已經(jīng)確定, 但有時給出的最優(yōu)解在現(xiàn)實中可能無法執(zhí)行.相關(guān)機會規(guī)劃并不假定可行集是確定的, 雖然它也給出一個確定的解, 但只是要求該解在實際問題中盡可能地被執(zhí)行[13].

2 .2 相關(guān)機會目標規(guī)劃模型

在鋼板切割的供給-分配系統(tǒng)中, 許多目標是互斥的, 決策者會根據(jù)其重要性為這些目標建立一個優(yōu)先結(jié)構(gòu).相關(guān)機會目標規(guī)劃就是在給定的優(yōu)先結(jié)構(gòu)下極小化各目標函數(shù)與目標值的偏差(正偏差或負偏差).在隨機任務分配問題的通用模型[13]中,對于同一優(yōu)先級下的多個目標偏差的處理采用(·)形式,其中n表示系統(tǒng)目標的個數(shù),(·)表示偏差求和.在該模型中, 對于任一優(yōu)先級, 系統(tǒng)目標的偏差和被計算1 次.當存在多個優(yōu)先級時, 目標的偏差和被重復計算了, 否則需要定義大量的偏差零權(quán)重因子, 使模型復雜性增大.針對這一問題, 本文對其同一優(yōu)先級下多目標的處理過程進行了修正.對于含有s個優(yōu)先級、t個目標、m個隨機約束的決策系統(tǒng),修正的相關(guān)機會目標規(guī)劃模型為

式中:s為優(yōu)先級的數(shù)目;λi為優(yōu)先級因子, 表示各個目標的相對重要程度, 且對于?i,λi?λi+1;t i為第i個優(yōu)先級中的目標數(shù)目,且為對應于優(yōu)先級i的第j個目標正偏差的權(quán)重因子;w ij為對應于優(yōu)先級i的第j個目標負偏差的權(quán)重因子;e ij(x , ξ)≤0 ,i=1 ,2 , …,s,j=1 ,2 , …,t i為第i個優(yōu)先級中的第j個目標事件,設為E ij, x 為決策向量, ξ為隨機向量, Pr{eij(x , ξ)≤0 ,i=1 ,2 , …,s,j=1 , 2 , …,t i}表示事件E ij的概率測度;b ij為第i個優(yōu)先級中的第j個目標事件的目標值;d+ij為第i個優(yōu)先級中的第j個目標偏離目標值bij的正偏差,且設f ij(x)=Pr{e ij(x ,ξ)≤0 ,i=1 ,2 , …,s,j=1 ,2 , …,t i}為事件E ij的機會函數(shù), 即d+ij=;d-ij為第i個優(yōu)先級中的第j個目標偏離目標值b ij的負偏差, 即d-ij=;隨機約束S k(x , ξ)≤0 ,k=1 ,2 , …,m為系統(tǒng)約束中的不確定環(huán)境.

在相關(guān)機會目標規(guī)劃模型中, 雖然決策向量x不是隨機向量, 但是具有一些不確定性質(zhì).它主要由2 個因素確定,一個來自于隨機變量ξ的實現(xiàn),另一個來自于實際系統(tǒng)給定的約束.

3 模型求解

在通常情況下, 相關(guān)機會目標規(guī)劃模型都很復雜,多采用人工智能方法進行求解.這里采用融合隨機模擬、BP 神經(jīng)網(wǎng)絡(error back propagation neural network)和遺傳算法的混合智能算法進行求解, 流程如圖2 所示.

圖2 混合智能算法流程Fig .2 Flow chart of hybrid intelligent algorithm

3.1 隨機模擬環(huán)節(jié)

在相關(guān)機會目標規(guī)劃模型中, 設在不確定環(huán)境Sk(x,ξ)≤0 ,k=1,2,…,m下 有t個 事 件e ij(x ,ξ)≤0 ,i=1,2,…,s,j=1 ,2,…,t i,根據(jù)不確定原理,該事件的機會等于此事件相容的概率[13],可得事件E ij的機會函數(shù)為

在混合智能算法中, 首先利用隨機模擬為不確定函數(shù)

產(chǎn)生訓練數(shù)據(jù).根據(jù)Chebyshev 弱大數(shù)定律,結(jié)合事件E ij本身的實值函數(shù),隨機產(chǎn)生事件E ij的相關(guān)支撐E**ij的向量x′與隨機向量ξ′,并記錄不等式S k(x′,ξ′)≤0 成立的次數(shù)N′.當隨機模擬次數(shù)為N時,用N′/N作為事件E ij的機會函數(shù)值,即f ij(x)=N′/N并作為BP神經(jīng)網(wǎng)絡的一個訓練數(shù)據(jù).

3.2 神經(jīng)網(wǎng)絡環(huán)節(jié)

在混合智能算法中, 經(jīng)過隨機模擬產(chǎn)生不確定函數(shù)U的多組訓練數(shù)據(jù)進入神經(jīng)網(wǎng)絡環(huán)節(jié)進行訓練,如圖2 所示.設E*為所有事件Eij的支撐E*ij的并集, α為E*中獨立變量的數(shù)目,β 為包含概率測度的事件的數(shù)目.采用單隱含層BP 神經(jīng)網(wǎng)絡來逼近不確定函數(shù)U,并以E*中獨立變量作為輸入神經(jīng)元,以事件的概率測度作為輸出神經(jīng)元, 則隱含層神經(jīng)元數(shù)目γ可根據(jù)經(jīng)驗公式獲得:

在此BP 神經(jīng)網(wǎng)絡中,設訓練數(shù)據(jù)為f k(x), 訓練輸出為F k(x), 通過訓練尋找權(quán)重向量來極小化誤差函數(shù)其中,n為訓練次數(shù).若此誤差函數(shù)值小于預先設定的精度ε0且滿足訓練次數(shù),則保存此BP 神經(jīng)網(wǎng)絡的權(quán)重向量,混合智能算法進入遺傳算法環(huán)節(jié), 否則繼續(xù)訓練.

3.3 遺傳算法環(huán)節(jié)

在本環(huán)節(jié)中, 直接采用浮點向量作為染色體解向量.將經(jīng)過訓練的BP 神經(jīng)網(wǎng)絡用來計算染色體的目標值,并使用基于序的評價函數(shù)e(Vi)計算每個染色體V i的適應度,即e(Vi)=ρ(1-ρ)i-1,ρ為序參數(shù),ρ∈(0 ,1),i=1 ,2,…,p(p為種群大小).

對于未達到進化代數(shù)的染色體,通過選擇、交叉和變異后重新計算染色體的目標值.首先, 通過輪盤賭方式選擇染色體,然后以概率Pc進行線性交叉以取代其父代.即對于選中的2 個父代染色體Vi和V j來說,經(jīng)過交叉操作產(chǎn)生子代染色體V′i和V′j,V′i=ωV i+(1-ω)V j,V′j=(1-ω)V i+ωV j,i,j=1 ,2,…,p,其中, ω為隨機數(shù), 且0 ＜ω＜1 .最后以概率P m進行變異以取代原染色體, 即對于染色體V i,根據(jù)目標實值定義一個較大的數(shù)θ和變異方向τ,使得變異后染色體V′i滿足V′i=V i+θτ,i=1 ,2,…,p,其中, τ為隨機數(shù),且-1 ＜τ＜1 .為保證所有產(chǎn)生染色體的合法性, 在選擇、交叉和變異環(huán)節(jié)嵌套約束檢查模塊.經(jīng)選擇、交叉和變異后得到新種群可進入下一代進化, 直至達到進化代數(shù),并輸出最優(yōu)染色體作為該相關(guān)機會目標規(guī)劃模型的最優(yōu)解.

3.4 最優(yōu)解的執(zhí)行

在期望值模型和機會約束規(guī)劃中, 當求得問題最優(yōu)解x*后, 可以分別執(zhí)行或同時執(zhí)行x*的每一個分量,對結(jié)果無影響.而在相關(guān)機會目標規(guī)劃中,可行集是隨機的, 解向量的各個分量中存在等級結(jié)構(gòu).因此, 在執(zhí)行最優(yōu)解的各個分量時, 必須嚴格按照目標結(jié)構(gòu), 依次執(zhí)行各優(yōu)先級目標對應事件的支撐,滿足級別高的分量優(yōu)于級別低的分量.

4 應用實例與分析

某船廠切割車間鋼板供給-分配系統(tǒng)如圖1,通過平板車存放、地面堆放和臨時抽板3 種途徑對4 臺數(shù)控切割機分配鋼板.CNC1 和CNC2 為新購設備, 切割效率高;CNC3 和CNC4 為舊設備, 切割效率較低.如遇補料和插單, 需中斷原切割計劃, 并以臨時抽板方式供給CNC3 和CNC4 .為防止鋼板堆積過多而變形,平板車和地面堆放鋼板數(shù)量有限制;而臨時抽板屬實時運送, 無此限制.受鋼板厚度、前道工序、生產(chǎn)準備影響,這3 種供給量每天都是隨機的.

考慮到鋼板厚度等的差異, 該船廠對鋼板切割長度 進 行 了 如 下 換 算:lC =lA αT +lBαM+(l′A +l′B)αE,其中,lC為鋼板切割長度;lA為數(shù)控切割長度;αT為厚度系數(shù);lB為數(shù)控劃線長度;αM為劃線長度系數(shù);l′A為切割空程長度;l′B為劃線空程長度;αE為空程長度系數(shù).

考慮到設備性能, 該船廠對4 臺數(shù)控切割機預設了最大切割長度和完成最大切割長度的目標概率,如表1 所示.計算方便起見,采用千米為單位.

表1 最大切割長度和目標概率Tab.1 Each supreme cutting length and corresponding target probability

由于CNC1 切割效率最高, 對生產(chǎn)影響較大,優(yōu)先級最高;CNC2 切割效率次之, 優(yōu)先級較高;CNC3和CNC4 切割效率較低, 優(yōu)先級一般.在生產(chǎn)中, 希望極大化它們完成最大切割長度的機會.對于臨時抽板, 由于擔心會造成生產(chǎn)混亂, 希望極小化其供應量,但是優(yōu)先級最低.為了合理地從3 個不確定供給端向4 臺數(shù)控切割機分配鋼板, 對該鋼板切割供給-分配系統(tǒng)建立的相關(guān)機會目標規(guī)劃模型如下:

其中,lexmin表示按字典序極小化目標向量;d+1～d+4,d-1～d-4分別表示4 臺數(shù)控切割機偏離切割目標的正、負偏差;d+5,d-5分別表示臨時抽板數(shù)量偏離目標零的正、負偏差;隨機變量ξ1,ξ2,ξ3分別表示3 種途徑的日供給量,該船廠統(tǒng)計資料顯示, ξ1,ξ2,ξ3分別近似服從正態(tài)分布N1(2 .095 755, 0 .642 8362),N2(3 .185 918 ,0 .802 7962)和N3(0 .115 436 ,0.087 1932).

對該鋼板切割供給-分配系統(tǒng)的相關(guān)機會目標規(guī)劃模型運用混合智能算法求解.首先, 隨機模擬6 000代為不確定函數(shù)U產(chǎn)生訓練樣本, 然后采用3 000個樣本訓練BP 神經(jīng)網(wǎng)絡(6 個輸入神經(jīng)元,12 個隱含層神經(jīng)元,4 個輸出神經(jīng)元)來逼近不確定函數(shù)U,最后采用遺傳算法進行求解.在遺傳算法中,種群數(shù)p=35 ,交叉概率Pc=0 .32 ,變異概率Pm=0 .23 ,基于序的評價函數(shù)參數(shù)ρ=0 .05,遺傳迭代3 000次.通過執(zhí)行該混合智能算法,得到最優(yōu)解

圖3 各目標分量進化過程Fig .3 Evolution of each target component

圖4 各決策分量進化過程Fig .4 Evolution of each decision-making component

圖5 f 與x 1,x 2 的變化關(guān)系Fig .5 Relationship among f,x 1 and x 2

在最優(yōu)解x*中,決策分量x3=x4=0,x7≈x8≈0 ,說明系統(tǒng)幾乎未從平板車和地面堆放處向CNC3 和CNC4分配鋼板.由于平板車距離CNC3 和CNC4 較遠,這種分配可以降低電磁吊的行走距離, 減少浪費.x1,x2,x5,x6數(shù)值較大,說明系統(tǒng)向CNC1 和CNC2 供給鋼板數(shù)量較多.由于彼此間距離很近,減少了搬運作業(yè)工作量從而降低了物流成本.

在對應最優(yōu)解x*的目標向量中, 分量,說明CNC1 和CNC2 完成最大切割長度的概率可以達到目標值,即保證了關(guān)鍵設備的利用率.CNC3 和CNC4 完成最大切割長度的機會僅有2 .75 %(即(0 .69-0 .662 5)×100 %)和2 .61 %(即(0 .65-0 .623 9)×100 %),其切割潛力提升空間較大.此時, 臨時抽板量為2 .167 1 km,數(shù)量較大, 已經(jīng)不局限于補料和插單.地面堆放、平板車存放及臨時抽板供給量的隨機性對切割任務分配的影響也通過模型得到控制和消除.

由于CNC4 切割能力較小、負荷較輕,可以考慮撤去, 用來存放部分“臨時抽板”, 加大供給量, 極大化CNC1～CNC3 完成最大切割長度的機會,增強鋼板切割供給的穩(wěn)定性,且為進一步提升3 臺數(shù)控切割機的性能做準備.同時,由于現(xiàn)有的切割機加工坡口效率較低,也可考慮將原CNC4 所占空間專門用來加工坡口,降低CNC1～CNC3 作業(yè)難度,縮短切割周期,提高作業(yè)效率,有利于船廠競爭力的增強和素質(zhì)的全面提升.

總之,通過對該鋼板切割供給-分配系統(tǒng)進行相關(guān)機會目標規(guī)劃建模和求解, 基本滿足了生產(chǎn)的多目標要求, 而供給端的不確定性對生產(chǎn)造成的影響也通過運用相關(guān)機會目標規(guī)劃加以控制和消除,不會造成生產(chǎn)混亂.

5 結(jié)語

針對鋼板切割供給-分配系統(tǒng)中多個供給端的不確定性, 應用相關(guān)機會目標規(guī)劃對該系統(tǒng)進行建模, 證實由于供給的不確定性對生產(chǎn)系統(tǒng)造成的影響可以控制和消除, 極大化關(guān)鍵設備完成最大切割長度的機會, 減少了浪費, 實現(xiàn)了切割的多目標要求.根據(jù)求解結(jié)果提出加大臨時抽板量的同時維持生產(chǎn)的穩(wěn)定性.最后結(jié)合生產(chǎn)實際分析進一步提高效率的措施以最大程度挖掘切割潛力, 為生產(chǎn)過程存在不確定資源分配問題的類似作業(yè)提供參考.

致謝 感謝同濟大學經(jīng)濟與管理學院柯華老師的指導.

[1] ZH ANG Y Q,XU K L, ZHO U G S, et al.Simulation and optimization of hull erection based on P-F TPN[C] ∥2009 16th International Conference on Industrial Engineering and Engineering Management. Piscataway : IEEE, 2009:1860-1864.

[2] 金壯龍.推進戰(zhàn)略轉(zhuǎn)型建設世界造船強國[EB/ OL] .[2009-02-01] .http:∥www.ccps .gov .cn/ dxrd.php? col =161&file=4839.JIN Zhuanglong .T o build a w orld shipbuilding power by strategy transformation[EB/ OL] .[2009-02-01] .http:∥www.ccps.gov.cn/ dxrd.php? col=161&file =4839.

[3] La Brooy R.Amethod for optimising the nesting of multiple ,hig hly complex shapes using a modified simulated annealing algorithm[J] .International Journal of Systems Science, 2009,40(2):155.

[4] Jang C D,H an Y K .An approach to efficient nesting and cutting path optimization of irregular shapes[J] .Journal of Ship Production,1999, 15(3):129.

[5] Hifi M, Paschos V T ,Zissimopoulos V .A simulated annealing approach for the circular cutting problem [J] .European Journal of Operational Research, 2004, 159(2):430.

[6] Ramesh Babu A,Ramesh Babu N .A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms[J] .Computer-Aided Design, 2001, 33(12):879.

[7] 趙定剛, 劉建峰, 張志英, 等.提高造船鋼材利用率的方法研究[J] .江蘇科技大學學報:自然科學版, 2006, 20(6):5.ZH AO Dinggang,LIU Jianfeng,ZHANG Zhiying et al.Study on improving steel availability in shipbuilding[J] .Journal of Jiangsu University of Science and Technology :Natural Science Edition, 2006, 20(6):5.

[8] Kim Y,Gotoh K,Toyosada M. Global cutting-path optimization considering the minimum heat effect with microgenetic algorithm s[J] .Journal of Marine Science and Technology,2004, 9(2):70.

[9] 高偉增, 張寶劍, 陳付貴, 等.基于遺傳算法的切割路徑優(yōu)化[J] .西南交通大學學報, 2005, 40(4):457.GAO Weizeng,ZH ANG Baojian, CH EN Fugui,et al .Optimization of cutting path based on genetic algorithm[J] .Journal of Southw est Jiaotong University,2005, 40(4):457.

[10] 田劍.船用鋼板切割車間生產(chǎn)調(diào)度優(yōu)化研究[J] .成組技術(shù)與生產(chǎn)現(xiàn)代化, 2009, 26(1):15.TIAN Jian.Study on production scheduling optimization of ship steel plate cutting workshop[J] .G roup Technology &Production Modernization, 2009, 26(1):15.

[11] 谷峰.柔性作業(yè)車間調(diào)度中的優(yōu)化算法研究[D] .合肥:中國科學技術(shù)大學, 2006.GU Feng .Optimization algorithm of flexible job shop scheduling[D] .Hefei:University of Science and Technology of China, 2006.

[12] 吳秀麗.多目標柔性作業(yè)車間調(diào)度技術(shù)研究[D] .西安:西北工業(yè)大學, 2006.WU Xiuli .Research on multi-objective flexible job shop scheduling problem [D] .Xi' an:Northw estern Poly technical University,2006.

[13] 劉寶碇, 趙瑞清, 王綱.不確定規(guī)劃及應用[M] .北京:清華大學出版社, 2003.LI U Baoding,ZHAO Ruiqing,WANG Gang .Uncertain programming with application [M] .Beijing : Tsinghua University Press, 2003.

[14] Charnes A,C ooper W W .Chance-constrained prog ramming[J] .Management Science,1959, 6(1):73.

[15] LIU B D .Dependent-chance programming :a class of stochastic optimization [J] . Computers & Mathematics with Applications, 1997, 34(12):89.

[16] Rossi R, Tarim S A, Hnich B, et al.A note on Liu-Iw amura' s dependent-chance programming [J] .European Journal of Operational Research,2009, 198(3):983.