高淑婷,李碧青

(1.河南農(nóng)業(yè)職業(yè)學(xué)院,鄭州451450;2.賀州學(xué)院,賀州542899)

0 引 言

電機(jī)生產(chǎn)企業(yè),每年需要消耗大量硅鋼板材用來制造電機(jī)鐵心[1]。鐵心毛坯一般為圓形。由于硅鋼板材比較昂貴,因此優(yōu)化下料方案來提高硅鋼板材下料利用率可降低企業(yè)生產(chǎn)成本[2-3]。

一般采用剪切和沖裁工藝下料[4]。首先剪床將硅鋼板材剪切成條帶,然后沖床將條帶沖裁出圓形片。從而存在兩個(gè)布局問題:條帶中的圓形片布局問題和板材中的條帶布局問題。圓形片在條帶中的布局方式在設(shè)計(jì)模具時(shí)就固定,無法更改;而條帶在板材中的布局方式可在下料過程中進(jìn)行優(yōu)化[5]。本文主要研究下料過程中條帶的優(yōu)化布局問題。

目前針對矩形毛坯剪沖下料問題研究較多[6-8],針對圓形片剪沖下料問題研究較少。崔耀東[2,9]提出了基于直切排樣方式和T型排樣方式的下料算法,這兩種算法都是基于列生成的線性規(guī)劃思想,用一個(gè)矩陣表征下料方案中的各個(gè)排樣方式,其中每列表征某個(gè)排樣方式中各種圓形片的數(shù)量。

本文介紹基于4塊排樣方式的混合下料算法,首先采用線性規(guī)劃和無約束排樣算法生成下料方案的線性解,保留線性解的整數(shù)部分;然后用順序啟發(fā)式算法和有約束排樣算法求解線性解小數(shù)部分對應(yīng)的圓形片的下料問題。數(shù)值實(shí)驗(yàn)結(jié)果表明,本文算法能有效地提高板材下料利用率。

1 下料問題的數(shù)學(xué)模型及算法

1.1 數(shù)學(xué)模型

圓形片下料(以下簡稱CPC)問題:用若干張尺寸為L×W的板材切割出m種圓形片,(di,qi)為第i種圓形片的直徑和需求量;下料優(yōu)化目標(biāo)為使用最少張數(shù)板材切割出所有需要的圓形片。

令G為單張板材上圓形片所有可能的排樣方式的數(shù)量,aij為第j種排樣方式中包含第i種圓形片的數(shù)量,yj為按照第j種排樣方式切割板材的張數(shù),N為自然數(shù)集合。CPC問題的數(shù)學(xué)模型:

目標(biāo)函數(shù)為最小化板材切割張數(shù);第一行約束條件表示下料方案中每種圓形片的需求量得到滿足;第二行約束條件表示每種板材切割的張數(shù)為自然數(shù)。對于中大規(guī)模下料問題,由于所有可能的排樣方式數(shù)G非常巨大,不可能枚舉出所有可能的排樣方式,因此式(1)無法直接采用數(shù)學(xué)規(guī)劃軟件求解。本文采用線性規(guī)劃和順序啟發(fā)式算法近似求解上述模型,用線性規(guī)劃算法生成下料方案的第一部分解,用順序啟發(fā)式算法生成下料方案的第二部分解。

1.2線性規(guī)劃算法

CPC問題的線性松弛模型:

式(2)中ZR為下料方案總共切割的板材張數(shù),Y=(y1,…,ym)為解向量,其中yj表示按照第j種排樣方式切割的板材張數(shù),A為下料方案矩陣,其中aij表示第j種排樣方式中包含的第i種圓形片的數(shù)量,Q=(q1,…,qm)為圓形片需求量向量。用如下線性規(guī)劃算法求解式(2)。

步驟1:構(gòu)造式(2)的初始可行解,解中包含m種排樣方式,第i種排樣方式中排放1個(gè)第i種圓形片;此時(shí)A為單位矩陣,下料方案總共切割∑m i=1qi張板材。

步驟2:確定圓形片當(dāng)前價(jià)值向量V=(1,…,1)A-1=(v1,v2,…,vm)。

步驟3:考察可能改善下料方案的排樣方式。假設(shè)當(dāng)前考察的排樣方式P=(p1,…,pm)T,其中pi為排樣方式中包含第i種圓形片的數(shù)量。依據(jù)線性規(guī)劃原理,若VP＞1,則引進(jìn)排樣方式P能改善當(dāng)前下料方案。通過求解如下式(3)構(gòu)造P。

用P替換矩陣A的第k列,其中k由單純型法確定[6],轉(zhuǎn)步驟2;若VP≤1,則不存在能使當(dāng)前下料方案得到改善的排樣方式,輸出下料方案,算法結(jié)束。

1.3 順序啟發(fā)式算法

上節(jié)的線性規(guī)劃算法求得的下料方案解中可能存在為小數(shù),傳統(tǒng)下料算法一般對解取上整操作,即將(作為最終解,其中為向上取整數(shù)符號。取上整操作會使得下料方案板材利用率不高。本文對線性規(guī)劃解進(jìn)行取下整操作,即將作為下料方案的第一部分解。 由于取下整操作而剩余的圓形片構(gòu)成第二部分下料問題,采用如下順序啟發(fā)式算法求解:

Step1:初始化圓形片的剩余需求量Q=Q-AY-。

Step2:用圓形片當(dāng)前剩余需求量調(diào)用有約束排樣算法生成一個(gè)有約束4塊排樣方式P,其中對任意i∈{1,…,m}有pi≤qi。 通過求解如下式(4)構(gòu)造P。

Step3:確定按照排樣方式P切割的板材張數(shù)λ=,更新圓形片剩余需求量λpi;如果對任意均有qi=0,則算法結(jié)束,輸出下料方案,否則,轉(zhuǎn)Step2。

2 排樣方式生成算法

4塊排樣方式的相關(guān)概念可參見文獻(xiàn)[5]。如圖1所示(圖中的數(shù)字為圓形片的編號),用一條父分界線和兩條子分界線將板材劃分為4個(gè)塊,每個(gè)塊中排放方向和長度均相同的條帶。條帶中可排放一行或多行圓形片(一般不超過3行)。按照是否能約束排樣方式中每種圓形片的數(shù)量,相應(yīng)的排樣算法可分為無約束排樣算法和有約束排樣算法;無約束排樣算法對排樣方式中圓形片數(shù)量沒有約束,有約束排樣算法限定排樣方式中每種圓形片的數(shù)量不超過其上界。

圖1 4塊排樣方式

下面設(shè)計(jì)有約束排樣算法。假設(shè)第i種圓形片的數(shù)量上界為bi,i∈{1,…,m}。當(dāng)bi取足夠大的數(shù)時(shí),有約束排樣算法即可變形為無約束排樣算法。

由于條帶中最多包含3行圓形片,因此對于m種圓形片,條帶共有3m種不同的寬度,其中第i種,第(i+m)種和第(i+2m)種寬度對應(yīng)第i種圓形片,即第j種條帶對應(yīng)第j%m種圓形片,其中“%”為取余數(shù)符號。令s(j,x)為條帶x×wj(長為x,寬為wj)的價(jià)值,n(j%m,x)為條帶x×wj中包含第j%m種圓形片的數(shù)量。則有:

其中n(j%m,x)的求解可參見參考文獻(xiàn)[9]。

對于塊x×y(長為x,寬為y),設(shè)塊的價(jià)值為F(x,y),x≤L,y≤W,令塊中包含條帶x×wj的數(shù)量為g(j,x)。則有:

式(6)為有界背包問題,具體算法可參考文獻(xiàn)[10]。求解式(6)后統(tǒng)計(jì)塊x×y中包含各種圓形片的數(shù)量,記第i種圓形片形數(shù)量為n(i,x,y)。

設(shè)4塊排樣方式的父分界線位置為x,兩條子分界線位置分別為y1,y2,其中x,y1,y2均為整數(shù)。令4塊排樣方式價(jià)值為V。則有:

目標(biāo)函數(shù)為最大化排樣方式價(jià)值,約束條件為排樣方式中每種圓形片的數(shù)量不超過其上界。

3 實(shí)驗(yàn)計(jì)算

用Java語言實(shí)現(xiàn)本文算法,所用實(shí)驗(yàn)環(huán)境為E-clipse IDE for Java Developers4.5.2 和 LINGO 16.0。實(shí)驗(yàn)所用計(jì)算機(jī)主頻2.7 GHz,內(nèi)存2 GB。

采用文獻(xiàn)[2]實(shí)例,某電機(jī)廠制造電機(jī)鐵芯需要10種圓形片,具體數(shù)據(jù)見文獻(xiàn)[2]表1,所有圓形片剪沖工藝余量均為5 mm。

3.1 實(shí)驗(yàn)一

市場上有3種不同尺寸的板材可供選購,分別為2 m×1 m,2.2 m×1.1 m,2.4 m×1.2 m。 對于 3種板材,本文算法和文獻(xiàn)[2]算法下料方案使用板材情況如表1所示?？梢妼τ?種不同尺寸的板材本文算法下料利用率分別比文獻(xiàn)[2]算法高4.65%,5.35%和 4.97%。 另外文獻(xiàn)[2]算法采購兩種板材時(shí)下料利用率最高為72.02%,采購3種板材時(shí)下料利用率最高為73.76%,均低于本文算法采購一種板材時(shí)的下料利用率。由于板材種數(shù)越多,下料工藝越復(fù)雜,因此本文算法不僅可以提高下

表1 3種板材的下料情況

料方案的板材利用率,還可以簡化下料工藝。圖2為本文算法使用2.4 m×1.2 m板材時(shí)的下料方案,共包含10種排樣方式,其中,“26張”表示按照排樣方式圖2(a)切割板材26張。

圖2 采用板材2.4 m×1.2 m時(shí)的下料方案

3.2 實(shí)驗(yàn)二

已知板材長度、寬度分別在區(qū)間[1.5 m,2 m],[0.75 m,1 m]取值,確定板材最優(yōu)尺寸使得下料方案板材利用率最高。按照文獻(xiàn)[2]表5對板材尺寸進(jìn)行離散取值,共考察36種不同尺寸的板材。文獻(xiàn)[2]算法最優(yōu)板材尺寸為1.7 m×0.95 m,相應(yīng)下料利用率為73.14%;本文算法最優(yōu)板材尺寸為1.9m×1 m,相應(yīng)下料利用率為75.34%,具體的下料方案如圖3所示。

圖3 采用板材1.9 m×1 m時(shí)的下料方案

4 結(jié) 語

本文針對電機(jī)鐵心用圓形片下料問題,介紹了一種基于線性規(guī)劃和順序啟發(fā)式的確定性下料算法。構(gòu)造了有約束4塊排樣方式生成算法和無約束四塊排樣方式生成算法,分別供線性規(guī)劃和順序啟發(fā)式算法調(diào)用。數(shù)值計(jì)算結(jié)果表明,本文下料算法能夠較大地提高硅鋼板材下料利用率,節(jié)約企業(yè)生產(chǎn)成本。

[1]鄧衛(wèi)國,趙威,巫書豪,等.鐵心疊鉚轉(zhuǎn)動工藝及模具設(shè)計(jì)[J].微特電機(jī),2016,44(10):94-96.

[2]季君,崔耀東,劉麗娜.電機(jī)用硅鋼板材尺寸合理選用[J].微特電機(jī),2005,33(3):40-42.

[3]崔柏偉,鄧衛(wèi)國.電機(jī)定轉(zhuǎn)子鐵心雙排無廢料級進(jìn)模設(shè)計(jì)[J].微特電機(jī),2013,41(5):71-74.

[4]蘇蘭.沖裁條帶三塊排樣方式的動態(tài)規(guī)劃算法[J].河南師范大學(xué)學(xué)報(bào)(自然版),2014(6):143-147.

[5]曾兆敏,管衛(wèi)利,潘衛(wèi)平,等.沖裁件條料最優(yōu)四塊剪切下料方案的生成算法[J].計(jì)算機(jī)工程與應(yīng)用,2016,52(20):75-79.

[6]季君.基于同形塊的剪切下料布局算法研究[D].北京:北京交通大學(xué),2012.

[7]MACEDOR,ALVESC,DECARVALHO JM V D.Arc-flow model for the two-dimensional guillotine cutting stock problem[J].Computers&Operations Research,2010,37(6):991-1001.

[8]SILVA E,ALVELOSF,DE CARVALHO JM V D.An integer programmingmodel for two-and three-stage two-dimensional cutting stock problems[J].Europe Journal of Operational Research,2010,205(3):699-708.

[9]CUIY D.Generating optimal T-shape cutting patterns for circular blanks[J].Computers&Operations Research,2005,32(1):143-152.

[10]KELLERER H,PFERSCHY U,PISINGER D.Knapsack problems[M].Berlin:Springer,2004.