亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于最小勢(shì)能原理的不規(guī)則零件排樣算法*

        2011-06-25 06:32:36劉虓葉家瑋胡金鵬
        關(guān)鍵詞:形心排樣參考點(diǎn)

        劉虓 葉家瑋 胡金鵬

        (華南理工大學(xué)土木與交通學(xué)院,廣東廣州510640)

        排樣在造船、布匹和皮革加工業(yè)中有著廣泛應(yīng)用.排樣效率的微小提升可帶來(lái)巨大的經(jīng)濟(jì)效益,而排樣算法屬于組合優(yōu)化問(wèn)題,具有極高的計(jì)算復(fù)雜度,國(guó)內(nèi)外對(duì)此進(jìn)行了幾十年持續(xù)不斷的研究.大多數(shù)零件具有不規(guī)則的幾何外形,因此其排樣問(wèn)題具有重大的現(xiàn)實(shí)意義.

        目前不規(guī)則零件排樣的求解策略主要基于兩點(diǎn):“靠左向下”原則(BL)和臨界多邊形(NFP).BL最初由Baker等[1]提出,由于其簡(jiǎn)便性和良好表現(xiàn)被廣泛采用,同時(shí)一些改進(jìn)算法也相繼出現(xiàn)[2].由于BL會(huì)在母板上形成孔洞,造成浪費(fèi),于是有學(xué)者提出“靠左向下并填充孔洞”求解策略(BLF),其計(jì)算復(fù)雜度為 O(N3)(N 為零件數(shù)).Chazelle[3]則提出了一種改進(jìn)的 BLF算法,其算法復(fù)雜度為O(N2).

        由Art[4]首次提出的NFP是一種功能強(qiáng)大的幾何工具,它與BL結(jié)合產(chǎn)生了各種排樣算法[5].不少學(xué)者對(duì)NFP進(jìn)行了專(zhuān)門(mén)研究[6-7].NFP的求解非常耗時(shí),求解時(shí)間與零件數(shù)量N及零件的旋轉(zhuǎn)角個(gè)數(shù)(RN)成平方關(guān)系.以歐洲排樣研究組織(ESICUP)提供的標(biāo)準(zhǔn)問(wèn)題SWIM(N=10,RN=2)為例,Burke等[7]聲稱(chēng)每個(gè)NFP耗時(shí)1/66s,所有NFP計(jì)算時(shí)間為1/66×(10×2)2=6.08 s.但如果 RN=32,則計(jì)算時(shí)間將高達(dá)1/66×(10×32)2=1551.52s.

        Burke等[8]在母材上布置一排垂線,零件沿線移動(dòng)尋找最優(yōu)旋轉(zhuǎn)角使零件“包圍盒”寬度最小.Dowsland等[9]指出:如將零件看作砂礫,母材看作玻璃瓶,不斷搖晃“玻璃瓶”可使“砂礫”排列更緊密.這說(shuō)明重力在排樣中起到了重要作用.Lee等[10]在母材上布置多個(gè)排樣點(diǎn),在各點(diǎn)對(duì)零件進(jìn)行旋轉(zhuǎn)以找到最優(yōu)排樣姿態(tài)使零件形心坐標(biāo)x,y最小.該算法本質(zhì)上還是BL.

        受Burke、Dowsland和Lee的啟發(fā),運(yùn)用最小勢(shì)能原理對(duì)排樣問(wèn)題的物理意義進(jìn)行了解釋?zhuān)岢隽瞬灰?guī)則零件排樣新算法HAPE,該算法不需要計(jì)算NFP.

        1 排樣問(wèn)題的最小勢(shì)能原理

        結(jié)構(gòu)力學(xué)最小勢(shì)能原理:結(jié)構(gòu)體系在受力和變形過(guò)程中總是盡量使總勢(shì)能取得更小的值.

        結(jié)構(gòu)體系總勢(shì)能Π表達(dá)形式如下

        式中:Π為結(jié)構(gòu)體系總勢(shì)能;U為結(jié)構(gòu)體系變形勢(shì)能;V為結(jié)構(gòu)體系位置勢(shì)能.

        排樣問(wèn)題中零件沒(méi)有彈性變形(U=0).另外V=Gyc(G、yc分別為零件重力和形心高度).故

        下面給出排樣問(wèn)題最小勢(shì)能原理:零件在排樣過(guò)程中總是盡可能地通過(guò)平移或旋轉(zhuǎn)使其形心高度降低.

        如圖1所示,假設(shè)零件由多邊形表達(dá),含n個(gè)頂點(diǎn)和 n 條邊(lq,q=1,2,…,n),其面積和形心坐標(biāo)可由格林公式導(dǎo)得:

        令式(3)中的P=-y,Q=0,則零件面積為

        式中:xq、yq為頂點(diǎn)q的坐標(biāo);當(dāng)q=n時(shí),q+1=1.

        由式(4)、(5)可得到零件形心高度坐標(biāo) yc,yc=Mx/A.

        圖1 多邊形Fig.1 A polygon

        如圖2所示,某零件在不同的姿態(tài)下的形心高度是不同的.姿態(tài)2對(duì)應(yīng)的形心最高,也最不穩(wěn)定,零件在這種姿態(tài)下極易翻轉(zhuǎn);姿態(tài)4對(duì)應(yīng)的形心高度最低,零件在這種姿態(tài)下是最穩(wěn)定的.

        圖2 不同姿態(tài)下的形心高度Fig.2 Different height of center with different attitude yc1-yc4為零件在不同姿態(tài)1-4下的形心高度

        如圖3(a)所示,4個(gè)矩形零件以“倒金字塔”方式置于母材底部.該排樣姿態(tài)很不穩(wěn)定,如受外界干擾,“倒金字塔”極易“傾覆”,如圖3(b)所示.各零件將散落在母材底部,如受到圖3(c)所示更“強(qiáng)烈”的外界干擾,零件將排列得更加緊密.

        圖3 倒金字塔零件的排樣Fig.3 Layout of upside-down pyramid composed of shapes

        2 定義

        定義1 零件參考點(diǎn)(RP).

        RP可以在任意位置選取.如圖4所示,零件的平移和旋轉(zhuǎn)均基于RP.

        定義2 零件排樣姿態(tài)(Att).

        如圖4所示,Att包含兩個(gè)要素:RP和旋轉(zhuǎn)角α.

        圖4 參考點(diǎn)和排樣姿態(tài)Fig.4 Reference point and nesting attitude

        使用C語(yǔ)言定義Att:

        定義3 排樣點(diǎn)和排樣點(diǎn)間距(PPD).

        如圖5所示,在母材上以一定的水平和垂直間距(PPD)布置的離散點(diǎn)被稱(chēng)為排樣點(diǎn).

        圖5 排樣點(diǎn)和排樣姿態(tài)Fig.5 Nesting point and nesting attitude

        定義4 可行排樣姿態(tài).

        假設(shè)零件平移至某個(gè)排樣點(diǎn)(參考點(diǎn)和排樣點(diǎn)重合),然后旋轉(zhuǎn)某一個(gè)角度.如在此排樣姿態(tài)下,該零件在母材內(nèi)部且與其它零件不重疊,則稱(chēng)其為“可行”排樣姿態(tài).

        如圖4所示,零件旋轉(zhuǎn)角定義如下:

        式中:j=0,1,…,RN -1.

        在每個(gè)排樣點(diǎn),零件有RN個(gè)排樣姿態(tài).如圖5所示,虛線排樣姿態(tài)為“不可行”排樣姿態(tài);實(shí)線的則為“可行”排樣姿態(tài).

        3 基于最小勢(shì)能原理的排樣算法HAPE

        HAPE的算法流程如圖6所示.

        圖6 HAPE流程圖Fig.6 Flow chart of HAPE

        流程圖中有幾個(gè)地方需要注意:

        (a)PPN為排樣點(diǎn)個(gè)數(shù),xi,yi為第i個(gè)排樣點(diǎn)的坐標(biāo)(i=1,2,…,PPN);

        (b)算法流程圖中的零件旋轉(zhuǎn),實(shí)際上是將圖1中的多邊形頂點(diǎn)基于參考點(diǎn)進(jìn)行旋轉(zhuǎn):

        式中:xk,yk為零件頂點(diǎn) k的坐標(biāo)(k=1,2,…,n,n為零件頂點(diǎn)個(gè)數(shù));xr,yr為零件參考點(diǎn)坐標(biāo);

        (c)Center_Y(part)表示計(jì)算零件part形心坐標(biāo)yc的函數(shù),計(jì)算參考式(4)、(5).

        4 算例

        圖7 母板和零件Fig.7 Stock sheet and part

        圖8 HAPE排樣圖Fig.8 Layout by HAPE

        對(duì)4種不同形狀的船體零件(N=66)進(jìn)行排樣(圖7中交叉點(diǎn)為參考點(diǎn)),母材尺寸:5 000 mm×3050mm,PPD=100 mm,RN=8.零件1-4按照面積大小依次進(jìn)行排樣.在Visual C++6.0環(huán)境下編程,電腦處理器為2.66 GHz Celeron? CPU.如圖8(a)所示,HAPE可以處理凹多邊形零件以及具有鋸齒邊緣的零件,并可以利用孔洞進(jìn)行排樣.由于排樣點(diǎn)是離散的,母材上仍然留下了很多的縫隙,縫隙大小與PPD成正比.如圖8(b)所示,這種“天然”的縫隙可通過(guò)靠接算法消除之[11-12],具體算法見(jiàn)參考文獻(xiàn)[12].如圖9(a)所示,零件1、2之間以及零件1與母材底部之間存在空隙.如圖9(b)所示,零件1通過(guò)垂向靠接消除了與母材底部之間的空隙;如圖9(c)所示,零件2通過(guò)水平靠接消除了與零件1之間的空隙.

        圖9 通過(guò)垂向和水平移動(dòng)消除空隙Fig.9 Elimination of gaps by vertical/horizontal moving

        如果將PPD減至25 mm,排樣效果如圖10所示.使用軟件Nestlib排樣效果如圖11所示.可以發(fā)現(xiàn)HAPE已經(jīng)接近商業(yè)排樣軟件水平.

        圖10 HAPE排樣圖Fig.10 Layout by HAPE

        圖11 Nestlib排樣圖Fig.11 Layout by Nestlib

        5 結(jié)論

        綜上所述,HAPE具有如下特點(diǎn):(1)物理意義明確,算法簡(jiǎn)便,排樣效果接近商業(yè)軟件水平;(2)不需要計(jì)算NFP;(3)可以處理不規(guī)則零件,并利用孔洞進(jìn)行排樣;(4)HAPE的計(jì)算時(shí)間與排樣點(diǎn)密度(1/PPD2)成正比,在計(jì)算速度上雖然與商業(yè)軟件存在較大差距,但絕對(duì)的計(jì)算時(shí)間尚在可接受范圍內(nèi).

        需要特別指出的是:除了不需要計(jì)算 NFP,HAPE也不需要考慮“盡量向左”的準(zhǔn)則.這兩點(diǎn)正是HAPE與普通BL算法的最大區(qū)別.

        [1]Baker B S,Coffman J E G,Rivest R L.Orthogonal packings in two dimensions[J].SIAM Journal on Computing,1980,9(4):846-855.

        [2]Liu De-quan,Teng Hong-fei.An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles[J].European Journal of Operational Research,1999,112(2):413-420.

        [3]Chazelle B.The bottom-left bin-packing heuristic:an efficient implementation [J].IEEE Transactions on Computers,1983,C32(8):697-707.

        [4]Art R C.An approach to the two-dimensional irregular cutting stock problem [R].Cambridge:IBM Cambridge Centre,1966.

        [5]Dowsland K A,Vaid S,Dowsland W B.An algorithm for polygon placement using a bottom-left strategy[J].European Journal of Operational Research,2002,141(2):371-381.

        [6]Bennell J A,Dowsland K A,Dowsland W B.The irregular cutting-stock problem—a new procedure for deriving the no-fit polygon[J].Computers & Operations Research,2001,28(3):271-287.

        [7]Burke E K,Hellier R S R,Kendall G,et al.Complete and robust no-fit polygon generation for the irregular stock cutting problem [J].European Journal of Operational Research,2007,179(1):27-49.

        [8]Burke Edmund,Robert Hellier,Graham Kendall,et al.A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem [J].Operations Research,2006,54(3):587-601.

        [9]Dowsland K A,Dowsland W B,Bennell J A.Jostling for position:local improvement for irregular cutting patterns[J].The Journal of the Operational Research Society,1998,49(6):647-658.

        [10]Lee Wenchen,Ma Heng,Cheng Borwen.A heuristic for nesting problems of irregular shapes[J].Computer-Aided Design,2008,40(5):625-633.

        [11]宋亞男,葉家瑋,鄧飛其,等.不規(guī)則圖形排樣系統(tǒng)中靠接算法比較研究[J].計(jì)算機(jī)工程,2004,30(19):8-10.Song Ya-nan,Ye Jia-wei,Deng Fei-qi,et al.Analysis and comparison of collision algorithm in packing(nesting)[J].Computer Engineering,2004,30(19):8-10.

        [12]劉虓,葉家瑋.基于多邊形重疊檢測(cè)的沖裁件優(yōu)化排樣[J].鍛壓技術(shù),2010,35(5):155-158.Liu Xiao,Ye Jia-wei.Optimal stamping blank layout based on algorithm of polygon intersection detecting[J].Forging & Stamping Technology,2010,35(5):155-158.

        猜你喜歡
        形心排樣參考點(diǎn)
        Heisenberg李代數(shù)的形心
        FANUC數(shù)控系統(tǒng)機(jī)床一鍵回參考點(diǎn)的方法
        基于MATLAB圖像特征提取的零件位置識(shí)別
        基于MATLAB圖像特征提取的零件位置識(shí)別
        參考點(diǎn)對(duì)WiFi位置指紋算法的影響
        數(shù)控機(jī)床返回參考點(diǎn)故障維修
        基于壓縮因子粒子群的組合排樣的研究
        FANUC數(shù)控機(jī)床回參考點(diǎn)故障分析與排除
        U形電器支架的多工位模具的排樣及模具設(shè)計(jì)
        人工智能技術(shù)在排樣技術(shù)上的發(fā)展現(xiàn)狀
        人妻有码中文字幕| 一级a免费高清免在线| 国产中文字幕免费视频一区| 人与人性恔配视频免费 | 亚洲国产韩国欧美在线| 欧美性一区| 女同另类一区二区三区| 亚洲精品在线国产精品| 无码国产精品一区二区免费模式 | 免费a级毛片18以上观看精品| 日韩一线无码av毛片免费| 国产aⅴ丝袜旗袍无码麻豆 | 国产成+人+综合+亚洲专| 中文字幕人妻在线少妇完整版| 久久精品国产亚洲夜色av网站| 无码少妇一区二区浪潮av| 亚洲丁香五月激情综合| 人妻1024手机看片你懂的| 精品国产精品三级精品av网址| 精品亚洲成a人在线观看青青| 九九在线精品视频xxx| 日本av不卡一区二区三区| 亚洲av无码久久| 亚洲国产一区二区三区在线观看| 亚洲欧美日韩在线一区| 无码精品国产午夜| 日本一区二区三区在线视频观看| 国产亚洲超级97免费视频| 无码不卡av东京热毛片| 国内精品一区二区2021在线| 99热婷婷一区二区三区| 久久久亚洲欧洲日产国码aⅴ | 一本一本久久a久久精品 | 色婷婷一区二区三区四区成人网| 久久无码av三级| 无码高潮少妇毛多水多水免费 | 精品国产亚洲av高清大片| a级毛片免费观看在线| 韩国一级成a人片在线观看| 亚洲区1区3区4区中文字幕码| 女人av天堂国产在线|