面向訂單的銅板帶生產(chǎn)組批及優(yōu)化

面向訂單的銅板帶生產(chǎn)組批及優(yōu)化晏曉輝1,2,朱云龍1,呂賜興1【摘要】摘要:如何有效地解決計劃中的組批問題是銅板帶加工首要考慮的問題。在深入研究銅板帶生產(chǎn)中訂單組批規(guī)律的基礎(chǔ)上，建立了綜合考慮鑄錠化學(xué)成分、工藝路線以及經(jīng)濟(jì)性的多目標(biāo)組批優(yōu)化模型,采用一種基于基因段思想的遺傳算法，設(shè)計了基于基因段的編碼、解碼、交叉和變異規(guī)則，并通過加權(quán)因子綜合了鑄錠個數(shù)和工藝路線重合度，將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)進(jìn)行求解。生產(chǎn)數(shù)據(jù)試驗表明，采用的方法能夠減少需要的鑄錠數(shù)量和中間工序分卷次數(shù)，有效地解決了生產(chǎn)中的組批優(yōu)化問題?！酒诳Q】計算機(jī)集成制造系統(tǒng)【年(卷)，期】2011(017)009【關(guān)鍵詞】關(guān)鍵詞:訂單組批;裝箱問題;遺傳算法;基因段;銅板帶1問題的提出典型的銅加工過程包括熔鑄和壓延兩部分，屬于混合制造模式。其中熔鑄部分是連續(xù)加工，而壓延工藝相對復(fù)雜，涉及步進(jìn)爐加熱、熱軋、雙面銑、初軋、切邊、鐘罩爐退火、酸堿洗、精軋、氣墊爐退火、清洗、拉彎矯直以及剪切包裝等十幾道工序，部分工序為離散加工，而在步進(jìn)爐加熱和退火等工序中，需要聚批連續(xù)加工。初軋之前，所有產(chǎn)品的工藝路線大致相同，初軋之后根據(jù)不同的訂單和產(chǎn)品工藝路線進(jìn)行分卷處理，分卷之后的料卷根據(jù)各自的工藝?yán)^續(xù)進(jìn)行加工，如圖1所示。由于銅板帶價格高昂，為減小庫存積壓,訂單往往表現(xiàn)出即時、小批量等特性,通常多個訂單的訂貨量組合到一起才能達(dá)到一個標(biāo)準(zhǔn)規(guī)格鑄錠的重量。因此，在制定熔鑄生產(chǎn)計劃時,對于訂貨量小的訂單似及大訂單分配到鑄錠中后的剩余部分,需要將其按照牌號相同、工藝路線相近、交貨期相近的規(guī)則組合到各個標(biāo)準(zhǔn)規(guī)格鑄錠中進(jìn)行生產(chǎn)，并在后續(xù)的壓延、剪切工序中將中間產(chǎn)品分配給各個訂單，這個將訂單分配到各個標(biāo)準(zhǔn)規(guī)格鑄錠中生產(chǎn)的過程即為銅加工訂單組批過程。組批問題并非銅加工行業(yè)獨(dú)有，在鋼鐵行業(yè)已有兩種關(guān)于組批的研究，一種關(guān)注的是在某道工序上對多個鑄錠的加工進(jìn)行計劃排序如趙瑁等對冷軋板組批調(diào)度進(jìn)行了建模，采用單親遺傳和臨域搜索相結(jié)合的方法來求解該問題［1］,SungdeukMoon等采用了整數(shù)線性規(guī)劃的方法對退火爐的組批生產(chǎn)進(jìn)行了求解［2］;另一種研究是針對鋼管生產(chǎn)過程中短尺合同進(jìn)行組批，以確定鋼管在熱區(qū)分割時的熱分區(qū)長度，如李虎等對該問題進(jìn)行了建模，將特定規(guī)則加入到一步算法中來對該問題進(jìn)行求解［3］。銅板帶加工的訂單組批問題與上述鋼鐵行業(yè)的第二種組批類似，但也有不同之處:鋼管的合同組批目的是使熱分區(qū)長度符合更多的訂單長度，銅加工的訂單組批則是將多個訂單合并到鑄錠中去。另外，前者只需考慮合同要求的長度而后者在熔鑄之前必須考慮牌號、工藝路線等多種因素。因而鋼鐵行業(yè)組批優(yōu)化在銅加工行業(yè)中不具有直接借鑒意義。目前，對銅板帶加工的生產(chǎn)組批優(yōu)化還缺乏相關(guān)的研究和應(yīng)用，銅加工行業(yè)生產(chǎn)組批主要由計劃員根據(jù)經(jīng)驗手工完成，存在鑄錠余量較大、占用增加、中間工序分卷次數(shù)多等不足。在牌號、重量、工藝路線等條件的限制下，如何合理地實現(xiàn)生產(chǎn)組批，減少需要生產(chǎn)的鑄錠個數(shù)，提高成品率，并將工藝路線相近的訂單組在一起，使得制造分離點(diǎn)向后推移，成為銅板帶加工行業(yè)迫切需要解決的一個實際組合優(yōu)化問題。為此，本文采用整數(shù)規(guī)劃方法對銅板帶生產(chǎn)組批問題進(jìn)行建模，進(jìn)而把組批問題抽象為一個帶特性的多目標(biāo)裝箱問題，應(yīng)用一種基于基因段思想的遺傳算法，以解決面向訂單的銅板帶生產(chǎn)組批優(yōu)化問題。2組批問題建模在接收訂單后，首先要對訂單進(jìn)行工藝設(shè)計，確認(rèn)訂單的加工路線及加工方法，根據(jù)產(chǎn)品的成品率計算訂單需要的熔鑄重量，工藝設(shè)計完畢后，再對訂單進(jìn)行組批,確認(rèn)各種牌號鑄錠需要生產(chǎn)的數(shù)量，以便進(jìn)行后續(xù)的排產(chǎn)。在組批時，對熔鑄重量大于標(biāo)準(zhǔn)規(guī)格重量的訂單，需要拆分到多個鑄錠中，對拆分后的剩余重量和熔鑄重量較小的訂單，需要組合到標(biāo)準(zhǔn)規(guī)格鑄錠中。組批分為橫向組批和縱向組批：i橫向組批指組在一個鑄錠中的訂單工藝完全相同，鑄錠可以作為一個整體一直加工，最后在剪切工序分卷，交付給不同用戶;④縱向組批指組在一起的訂單工藝路線只有一部分相同，必須在中間工序分卷，分卷之后各自單獨(dú)進(jìn)行加工。中間工序分卷給物料加工和跟蹤造成了不便同時，也加大了設(shè)備占用和能源的消耗因此，組批時在不增加料卷的前提下應(yīng)盡量以橫向組批為主，避免中間分卷似實現(xiàn)批量經(jīng)濟(jì)。由上所述，訂單組批的目標(biāo)為：i盡量使用最少的鑄錠來滿足訂單;④組在同一個鑄錠中的訂單的工藝路線盡量一致。在組批時需考慮如下約束條件：i組在同一個鑄錠中的訂單熔鑄重量之和不超過—個標(biāo)準(zhǔn)規(guī)格鑄錠的重量;④組在同一個鑄錠中的訂單牌號必須相同。牌號代表鑄錠的化學(xué)成分，在同爐次熔鑄的鑄錠成分相同。用一個四元組來表示訂單:order=-id,w/a/c-。式中:id為訂單編號,w為訂單考慮成品率之后的重量,a為訂單牌號,c為工藝規(guī)程編號。設(shè)標(biāo)準(zhǔn)規(guī)格鑄錠重量為WS,對于訂單重量大于標(biāo)準(zhǔn)規(guī)格鑄錠重量的情況，只需考慮訂單分配給鑄錠之后的剩余部分，不失一般性，可以假定對所有訂單，均有w<WS。對n個訂單的組批問題，建立訂單牌號對比矩陣A,建立訂單工藝路線重合度矩陣C,假設(shè)初始預(yù)估鑄錠數(shù)為m,建立分配矩陣X,則需要的鑄錠數(shù)最少的目標(biāo)函數(shù)表示為：同時,工藝路線重合度最大的目標(biāo)函數(shù)可表示為：根據(jù)一個訂單只能被分配到一個鑄錠中去，有約束：根據(jù)一個鑄錠中的訂單總重量不超過一個標(biāo)準(zhǔn)鑄錠的重量，有約束：根據(jù)同一個鑄錠中訂單的牌號全部相同這一要求可知，當(dāng)XijXkj=1時,要求Aik=1,當(dāng)XijXkj=0時Aik=0或1,i=123,...,n,j=123,...,m,故該約束可表示為：綜上，建立組批問題的模型上述模型可以抽象為一種特殊的裝箱問題——帶特性的多目標(biāo)一維裝箱問題。訂單代表需裝箱的物品,有牌號、工藝規(guī)程、重量等屬性，鑄錠相當(dāng)于固定重量的箱子,尋求一種裝箱方案,在同種牌號才能組合在一個鑄錠中且同一鑄錠中的訂單重量不能超過標(biāo)準(zhǔn)鑄錠重量的前提下，使所需鑄錠數(shù)最少，并且裝箱組合盡量使工藝路線重合度較高。裝箱問題是一個NP-hard問題,根據(jù)裝箱問題考慮的維度可以分為一維、二維和三維裝箱。根據(jù)箱子大小是否可變，可分為固定裝箱問題和大小可變裝箱問題。根據(jù)物品在裝箱時的要求,可分為帶特性的裝箱問題和不帶特性的裝箱問題。對于不帶特性的裝箱問題,有許多算法進(jìn)行求解，主要包括近似算法如首次適應(yīng)（降序)法FF/FFD(firstfit/decreasing)、下次適應(yīng)(降序)法NF/NFD(nextfit/decreasing)、最佳適應(yīng)(降序)法BF/BFD(bestfit/decreasing)和調(diào)和算法［4-6］;智能算法如:啟發(fā)式算法、遺傳算法、粒子群算法、禁忌搜索算法等［7-9］。近似算法是基于特定規(guī)則來求解,不能保證求得最好解，但規(guī)則適合問題的情況下可能求得滿意解。智能算法采用隨機(jī)試探的方式，在針對二維、三維等存在擺放方位約束的問題上有較好的表現(xiàn)。對于帶特性的裝箱問題，由于換箱時有特性限制，常規(guī)的智能算法在換箱操作即編碼變換時存在困難，該類裝箱問題通常采用FFD-k、NFD-k、BFD-k等近似算法求解。董一鴻等針對有色裝箱問題采用KC-FD,KC-FF和KC-FFD等多種方法進(jìn)行了對比,并提出了SCPF-A(samecolorpackedfirst)算法，在裝箱之前先對顏色進(jìn)行分類排序［10］。HansKellerer等對帶有特性的裝箱問題(k-BP)的近似算法進(jìn)行了時間復(fù)雜度分析［11］。LeahEpstein等在此基礎(chǔ)上進(jìn)一步分析了特性種數(shù)k在不同取值時各近似算法的時間復(fù)雜度變化［12］。但這些近似算法所求得的解的優(yōu)劣受限于問題的數(shù)據(jù)，并且上述研究均為單一特性約束，不能處理多特性約束的裝箱問題。針對前述多目標(biāo)組批優(yōu)化模型，本文采用了一種基于基因段的遺傳算法,使得在隨機(jī)搜索時仍能保證只有同種牌號才能組到一個鑄錠中，既保留了遺傳算法的優(yōu)點(diǎn)，又克服了它在處理帶特性問題上的困難。基于基因段的遺傳算法是在原遺傳算法的基礎(chǔ)上加入基因段的概念，將個體編碼即整個基因分成若干個基因段，只有同一個基因段內(nèi)的基因才能相互交換,在變異時也局限于該基因段之內(nèi)。對于帶特性的裝箱問題，在對個體進(jìn)行編碼時可以按照物品特性將編碼分為若干個基因段，保持基因只能在同基因段內(nèi)交叉和變異，這樣，就解決了特性，而其他目標(biāo)和約束條件可以放在目標(biāo)函數(shù)中通過適應(yīng)度來體現(xiàn)。采用基于基因段的遺傳算法求解組批問題的流程圖如圖2所示。3.1基于基因段的編碼規(guī)則針對裝箱問題，有兩種常見的編碼方式［13F基于箱子的編碼表示(Bin-BasedRepresentation,BBR),用基因的位置表示物品，基因的值表示該物品所放入的箱子:④基于物品的編碼表示(Object-BasedRepresentation,OBR),只對物品的排列進(jìn)行編碼，然后應(yīng)用解碼器得到對應(yīng)的解。本文采用BBR法，即個體編碼為定長編碼，長度為訂單的數(shù)目，基因位置代表訂單編號,基因值代表該訂單所分配的箱號，箱號不超過初始箱子數(shù)m。由wvWS可知，對于n個訂單，最多需要n個鑄錠就能把他們?nèi)垦b進(jìn)去，且為了保證在后面的交換過程中有足夠的空間使訂單在鑄錠之間得到充分交換，對上述模型，可以取初始鑄錠數(shù)m=n。本文中的特性為訂單牌號,基因段根據(jù)訂單的牌號特性來確定。為方便交換，首先按照牌號將各訂單排序，分析牌號種類及每種牌號訂單的個數(shù),假設(shè)這n個訂單牌號有k種，第i種牌號訂單個數(shù)為對長度為n的編碼，分為k個基因段，第i個基因段的長度為Qi,取值范圍為只有在同一個基因段之間的訂單才能交叉互換，以保證不同牌號的訂單不會裝到同一個鑄錠中去,并且變異時的取值也限定在本基因段的取值范圍內(nèi)。3.2解碼規(guī)則對于基于上述編碼的個體，可以將其解碼為前述分配矩陣X。對于矩陣X,當(dāng)基因位置i上的基因值為j時置Xij=1,其他元素為0。由于在編碼時，先對訂單按照牌號特性進(jìn)行了排序，在解碼時也要對基因個體還原順序。3.3交叉設(shè)定交叉因子，并以交叉因子的概率隨機(jī)選中兩個個體，再隨機(jī)選擇交叉點(diǎn)，判斷交叉點(diǎn)所在的基因段,對該基因段內(nèi)交叉點(diǎn)之后的基因進(jìn)行交換，其他位置的基因取值均不變。3.4變異設(shè)定變異因子，并以變異因子的概率選中一個個體，再隨機(jī)選擇一個變異點(diǎn)，判斷變異點(diǎn)所在的基因段，重新生成變異點(diǎn)的基因值，該基因值取值范圍為所在基因段的取值范圍。3.5適應(yīng)度函在組批問題基本模型的基礎(chǔ)上，將工藝路線重合度目標(biāo)以加權(quán)因子a加入到鑄錠個數(shù)目標(biāo)中,將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)，目標(biāo)函數(shù)變?yōu)橛捎赬ij,Xkj=0或1,Cik<1,m<n,又因為矩陣X為稀疏矩陣,值較小，通常都不會超過n2,故將該部分目標(biāo)放大，取使工藝路線目標(biāo)不超過1,在優(yōu)化時以減少需要的鑄錠個數(shù)為主要優(yōu)化目標(biāo)。XijXkj<Aik這一牌號相同的約束條件已經(jīng)在編碼中得到保證，對于重量約束將以罰函數(shù)的形式加入到目標(biāo)函數(shù)中來進(jìn)行限制。設(shè)懲罰因子為同在原目標(biāo)函數(shù)上加上來對超出限制的重量進(jìn)行懲罰。取懲罰因子p=io,對一個鑄錠中訂單重量超過標(biāo)準(zhǔn)規(guī)格重量的,每超過0.1XWS的重量懲罰相當(dāng)于增加一個鑄錠。綜上啟標(biāo)函數(shù)變?yōu)椋簩ΨN群中的各個個體，取適應(yīng)度為目標(biāo)函數(shù)越小，適應(yīng)度越大，用2次方加強(qiáng)較優(yōu)基因被選中的概率。4生產(chǎn)數(shù)據(jù)試驗帶特性的裝箱問題常用FFDk,NFDk和BFDk等近似算法求解，本文分別采用基于基因段的遺傳算法和近似求解方法中表現(xiàn)較好的FFDk來對數(shù)據(jù)進(jìn)行求解。由于FFDk不能直接求解多目標(biāo)問題，在采用FFDk法時先以重量為限制條件求解然后再按式(2)和式(6)得到工藝路線重合度和總目標(biāo)值。4.1試驗一試驗數(shù)據(jù)取自洛陽某銅加工企業(yè)電子銅板帶廠的實際訂單。訂單數(shù)據(jù)經(jīng)處理如表1所示有12個訂單，訂單的牌號、工藝路線編號、重量分別如表1所示，不同牌號之間不能組批,工藝路線11與12的重合度為0.8,11與13之間的重合度為0.6,12與13之間的重合度為0.7,21與22之間的重合度為0.9,21與23之間的重合度為0.7,22與23之間重合度為0.8,據(jù)此建立牌號可交換矩陣A和工藝路線重合度矩陣C,C矩陣具有一致性。對基于基因段的遺傳算法，設(shè)定種群大小為50,交叉因子為0.1,變異因子為0.07,進(jìn)化100次,10次求解，7次求得最優(yōu)組批方式為:(1,7),(2,12),(3,8),(4,5,11),(6,9,10)，其中每個括號中的數(shù)字代表組批在一個鑄錠中的訂單號，需要鑄錠個數(shù)為5,工藝路線重合度為0.1944,總目標(biāo)值f=4.8056,3次求得組批方式為:(1,7),(2,12),(3,8),(4,9,11),(5,6,10),需要鑄錠個數(shù)為5,工藝路線重合度為0.1889,總目標(biāo)值f=4.8111。用FFDk法對該問題求解,求得組批方式為(1,7),(3,8),(2,12),(4,10),(5,6,11),(9)。需要鑄錠個數(shù)為6,根據(jù)結(jié)果計算工藝路線重合度為0.1681,總目標(biāo)值f=5.8319。該結(jié)果表明,使用基于基因段的遺傳算法，比FFDk法少用一個鑄錠，并且工藝路線的組合上也更優(yōu)。4.2試驗二為測試算法在處理大規(guī)模訂單組批時的性能,采用30個訂單、5種牌號;30個訂單、7種牌號;50個訂單、7種牌號;50個訂單、10種牌號；100個訂單、7種牌號;100個訂單,10種牌號這六種情況的訂單數(shù)據(jù)進(jìn)行試驗。試驗結(jié)果如表2所示，基于基因段的遺傳算法結(jié)果為10次求解的平均值。由試驗結(jié)果可以看出，基于基因段的遺傳算法所求得的鑄錠個數(shù)基本上都優(yōu)于FFDk法求得的結(jié)果，僅在訂單數(shù)量為30、牌號種數(shù)為7時遺傳算法與FFDk法求得的鑄錠個數(shù)相同。隨著訂單數(shù)的增加，基于基因段的遺傳算法表現(xiàn)出更優(yōu)越的特性。需錠個數(shù)少與工藝路線重合度高這兩個目標(biāo)在一定程度上是相互沖突的,需錠個數(shù)越少，組批越緊密，由式(2)可知工藝路線重合度可能也越小。在工藝路線重合度高這一目標(biāo)上,基于基因段的遺傳算法有5次是最優(yōu)的，僅在訂單數(shù)量為100、牌號種數(shù)為10時次于FFDk法，但差別很小，且在需要鑄錠個數(shù)最少目標(biāo)上遠(yuǎn)優(yōu)于FFDk法。以上試驗表明，基于基因段的遺傳算法比傳統(tǒng)的FFDk法優(yōu)越，能較好地解決組批優(yōu)化問題。5結(jié)束語銅板帶的訂單組批是生產(chǎn)組織優(yōu)化的第一步，如何更合理地進(jìn)行組批,是銅板帶生產(chǎn)過程中提高生產(chǎn)效率、降低原料成本和減少能量消耗的關(guān)鍵。本文采用整數(shù)規(guī)劃方法對實際銅板帶加工的生產(chǎn)組批問題進(jìn)行了建模，并把該模型抽象為一類特殊的裝箱問題——帶特性的多目標(biāo)一維裝箱問題。同時，針對常用裝箱問題算法在求解這一特殊的裝箱問題時的不足，應(yīng)用了一種基于基因段的遺傳算法對組批問題進(jìn)行優(yōu)化求解。通過洛陽某銅加工企業(yè)的應(yīng)用結(jié)果表明，與歷史記錄相比,采用本文提出的模型和優(yōu)化組批方法后，熔鑄所需鑄錠減少4.1%,中間工序分卷次數(shù)減少8.4%。在縮減熔鑄成本的同時還能降低壓延部分的能量消耗和設(shè)備損耗，為該企業(yè)創(chuàng)造可觀的經(jīng)濟(jì)和社會效益。參考文獻(xiàn)：ZHAOJun,WANGWei,LIUQuanli.Modelandalgorithmofgroupingbatchschedulingforcoldroilingsheetproductionline[J].ComputerIntegratedManufacturingSystems,2008,14(10):1957-1965(inChinese).[趙瑁，王偉,劉全利.冷軋薄板生產(chǎn)線組批調(diào)度模型與算法[J].計算機(jī)集成制造系統(tǒng),2008,14(10):1957-1965.]MOONS,HRYMAKAN.Schedulingofthebatchannealingprocess—deterministiccase[J].ComputersandChemicalEngineering,1999,23(9):1193-1208.LIHu,HUOJiazhen.Aheuristicalgorithmforseamlesssteeltubeorder-groupingproblem[J].IndustrialEngineeringandManagemen,2004,9(1):86-88(inChinese).[李虎,霍佳震.鋼管生產(chǎn)的合同組批優(yōu)化算法[J].工業(yè)工程與管理,2004,9(1):86-88.]GUXiaodong,XUYinlong,CHENGuoliang,etal.Astochasticanalysisoftheharmonicbin-packingalgorithm[J].ChineseJournalofComputers,2001,24(5):548-552(inChinese).[顧曉東，許胤龍,陳國良，等.調(diào)和裝箱算法的平均性能分析[J].計算機(jī)學(xué)報,2001,24(5):548-552.]KONGLiang,DUBin,ZHUJun.Multi-constrainedvariablesizedbinpackingproblem[J].ControlEngineeringofChina,2008,15(5):176-178(inChinese).[孔亮，杜斌，朱俊.多約束的箱子大小可變的裝箱問題[J].控制工程,2008,15(5):176-178.]BEINW,CORREAJR,XINHan.Afastasymptoticapproximationschemeforbinpackingwithrejection[J].TheoreticalComputerScience,2008,393(1/2/3):14-22.ZHAIYu,SUNXiaoming.Aheuristicalgorithmforthree-dimensionalcontainerloadingproblemwithnon-identicalitems[J].JournalofShanghaiJiaotongUniversity,2007,41(8):1244-1247(inChinese).[翟鈺，孫小明.多種物品三維裝箱問題的一種啟發(fā)式算法[J].上海交通大學(xué)學(xué)報,2007,41(8):1244-1247.]JIANGBaochuan,XIONGWeiqing.Hybridgeneticalgorithmsolvingforthree-dimensionalcontainerloadingproblem[J].ComputerEngineeringandApplications,2007,43(26):200-202(inChinese).[江寶釧，熊偉清.一種求解三維集裝箱裝箱問題的混合遺傳算法[J].計算機(jī)工程與應(yīng)甩2007,43(26):200-202.]LIUDS,TANKC,HUANGSY,etal.Onsolvingmultiobjectivebinpackingproblemsusingparticleswarmoptimization[J].EuropeanJournalofOperationalResearch,2008,190(2):357-382.DONGYihong,ZHAOJieyu.Approximationalgorithmsfortheconstrainedbinpackingproblem[J].ComputerEngineeringandApplications,2003,39(18):41-44(inChinese).[董一鴻,趙杰煜.帶約束的一維裝箱問題近似算法的研究[J].計算機(jī)工程與應(yīng)用,2003,39(18):41-44.]KELLERERH,PFERSCHYU.Cardinalityconstrainedb