購買設(shè)計請充值后下載，，資源目錄下的文件所見即所得，都可以點開預覽，，資料完整，充值下載可得到資源目錄里的所有文件。。。【注】：dwg后綴為CAD圖紙，doc,docx為WORD文檔，原稿無水印，可編輯。。。具體請見文件預覽，有不明白之處，可咨詢QQ:12401814

運用緊湊相鄰法則對非規(guī)則零件圖樣進行大規(guī)模編排 S.K.陳 K.P.羅 香港 九龍 泰奇大道 香港城市大學 制造及管理工程系 摘要 目前廣泛應用的典型編排方法是對單個零件圖樣的幾何傾斜式編排，或者把圖樣自其初始位置到旋轉(zhuǎn)180一步一步地逐個選擇式編排。例如直交排布式。然而，這是一種對最佳原材料布置方法的盲目性探索。從幾何方面來說，當參與排樣的圖樣有多個時，該方法就變得毫無效率可言。它也不怎么適合處理具有一系列方向約束的零件圖樣。在本論文中，提出了一種結(jié)合緊湊相鄰法則（CNA）和遺傳運算法則（GA）來優(yōu)化大規(guī)模編排工藝的運算方法，該方法同時還考慮到了多方面的初始位置約束。 關(guān)鍵詞：原材料的切斷問題；編排；緊湊相鄰運算法則；遺傳算法；初始位置約束 1．簡介 原材料切斷問題在許多工業(yè)領(lǐng)域是一個有趣的問題，如服裝業(yè)，紙張工業(yè)，船體制造業(yè)各鋼鐵材料工業(yè)。Gilmore和Gomory最先開始研究運用線性程序平解決原材料的矩形切斷問題。對于原材料的不規(guī)則形狀切斷問題，Adamowicz嘗試運用一種對我們來說具有啟發(fā)示的方法來解決。他把這個問題分為兩個從屬的問題。即所謂的串叢式和筑巢式編排。串叢式編排是詳細地說明選擇的零件圖樣適合于給定的原材料，而巢式編排在其后進行。巢式或串叢式編排可以大概地分為兩個大的種類，即，大規(guī)模與小規(guī)模編排。它們之間的不同在于對給定原材料能編排的零件圖樣數(shù)量的級別。在小規(guī)模編排中，只需找到串叢編排和給定原材料的內(nèi)在方向關(guān)系。然而，這個問題在大規(guī)模巢式編排時變得非常復雜，因為同時還要考慮到編排的各個相同圖樣內(nèi)在的空間關(guān)系。根據(jù)傳統(tǒng)的方法，有兩種基本的方法普遍運用于處理這種類型的編排。它們分別是：“相似六邊形”方法和“直交編排”方法。 在此，選擇了一個典型的零件圖樣來解說這兩種技術(shù)方法。如圖1a所示，該零件同時具有外凸和內(nèi)凹的特征。在數(shù)字轉(zhuǎn)換器的幫助下得到了零件的輪廓形狀，如圖1b所示。其面積（）為74.44個平方單位。在Dori和BenBassat提出的“相似六邊形”法則中，該零件最初以一個外凸的多邊形來近似表達，然后，進一步地以包含更少圖形要素的外凸多邊形來表達，直到得到一個包住零件的六過形，如圖1c所示。然后，在給定的原村料上，互相不重疊地輔上這個六 圖1.（a）所選的用于示范CAN算法工作原理的平板形圖樣。（b）.由數(shù)字轉(zhuǎn)換器得到的圖樣外形輪廓。（c）相近多邊形。（d）相近直角圖形。(e)用相近六邊形法則得到的布局圖，材料利用率為60.05％。（f）用正交相近算法得到的布局圖，村料利用率為67.14％。(g)用CNA算法得到的布局圖，材料利用率為74.10％。 邊形圖樣。用這種方法產(chǎn)生的最終布局圖如圖1e所示。委容易證明，由于這種較差的相近表達原因，尤其是對于某些不規(guī)則零件圖樣，這種方法沒有較高的效率。加一個問題是零件的圖樣或串叢圖樣只能采取兩個位置方向（0或180），因而沒有開發(fā)的余地或考慮其它允許的編排方向。 在Nee所使用的第二種方法中，通過一個矩形來近似表達單個的零件或串叢圖形而得到編排方法，如圖1d所示。然后，這個矩形以正交的方式復制，得到的最終布局圖如圖1f所示。當零件圖樣沒有或只有部分方向約束時，這種方法應用起來非常容易，例如，單個零件或串叢圖形能在某個確定的角度轉(zhuǎn)動，從而適合于原材料的編排。和“相近六邊形”法則相似，這種方法的主要不足之處是正交排列在很大程度上依賴于零件的形狀。更多的是，在有多個方向約束的情況下，確定一個適合的旋向往往需要花費更多的時間。 為了增加編排的正確度及速度，S.K.陳和K.P.羅提出了一種緊湊相鄰法則（CNA），該法則考慮到相鄰圖樣的數(shù)量關(guān)系及它們之間的共同空間。圖1g所示為由CAN方法產(chǎn)生的布局圖，和相似六邊形及正交法則相比，在相同區(qū)域該方法具有更高的布置密度。然而，從目前形式來看，CNA主要設(shè)計用于編排具有完全方向約束的零件圖樣，對于零件圖樣有更多的自由度時達不到理想的要求。 本文探索的目的在于通過合并零件圖樣在初始方向具有的可能自由度和符合普通規(guī)則的遺傳算法來提高CNA的適應性。優(yōu)化布局圖的生成。這種新的方法被轉(zhuǎn)化輸入用面對對象語言編寫的C++計算機程序。這種算法能處理包括有任意直線和圓弧形狀的零件的兩個方向的平面巢編問題。通過一個有幫助的典型例子，可以看到，在本文中，CNA的重要作用和相關(guān)的計算機程序?qū)⑻幱跊Q定性的地位。 2．緊湊相鄰法則的描述 當零件被移動而形成不同的排列時，CNA追蹤變化的相鄰零件圖樣的特征，如圖2a-c所示簡要示意圖。當剪切位移面增加時，上面及下面的相鄰特征趨向于破壞，這是由于結(jié)晶化的方向發(fā)生了改變。最后，得到一個該材料的最大緊湊結(jié)構(gòu)和相關(guān)數(shù)值。即得到所謂的“全體緊湊利用率”（UCU）值。不論零件能夠旋轉(zhuǎn)與否，UCU指出了任何所選材料的最高屈服極限，因而可作為編排過程中一個臨界標準指數(shù)。找到緊湊相鄰的主要步驟包括：（1）產(chǎn)生一個“自滑移路徑”或者一個非適多邊形（NFP），如圖3a所示，來引導兩個非重疊零件圖樣的運動關(guān)系。 圖2圓形圖樣的典型相鄰相結(jié)圖（a）正交直角排布形成的單元，=8，=。（b）由于層的剪切導致的剪切正交排布。（c）六邊形排布的最湊結(jié)構(gòu)單元，=6，=。其中；表示單體的面積；r表圓形圖樣的半徑；表示與單元體相連的鄰邊結(jié)構(gòu)單元數(shù)目。 （2）定義結(jié)晶化方向，如圖3b所示，在大規(guī)模編排中提供基本的數(shù)據(jù)來建造充滿所給材料的全部相鄰圖樣。 3．大規(guī)模編排的建議算法 本單元論述通過利用遺傳算法而使所提及的CNA技術(shù)得到加強。一個平面零件圖樣可以被分為直線和元弧要素。多邊形表示法可以將外凸或內(nèi)凹的元弧以直線代替。確切的直線段數(shù)目決定于所要求的精確度。清除或偏移生成也是一個有助于CAD/CAM技術(shù)成功的必不可少的過程。一種算法產(chǎn)生所要求的偏移，稱作“三點島嶼跟蹤”方法，已經(jīng)與目前的編排系統(tǒng)結(jié)合在一起。 圖3 （a）以自滑移路徑方式產(chǎn)生相鄰結(jié)構(gòu)時所包含的步驟。（b）以六邊形排布得到的優(yōu)化相鄰結(jié)構(gòu)單元，UCU達到83.07％。 3.1 CNA用于大規(guī)模編排 在前述章節(jié)，已經(jīng)涉及到得到最緊湊相鄰編排所包括的一些基本步驟。如圖3b所示。接下來的重點是確定一個最適位置來放置第一個圖樣并擴展這種結(jié)構(gòu)，使其充滿整個原材料。編排全方位約束的零件圖樣時，只需確定一個“編排向量”，來定認相鄰圖樣的放置位置。然而，當偏排有限的或完全沒有約束的圖樣時，由于要考慮到可能的連接方式，這個問題變得非常復雜。在這種情況下，第一步是根據(jù)原始位置限制進行球形布排或不依靠原始位置約束而在原材料內(nèi)部區(qū)域隨意確定相鄰圖樣位置。例如，定義一個向量，然后，確定“編排方向”，因而就確定了一個適宜相鄰圖樣排布生長的方向。全部所需的幾何計算如圖4的簡括。優(yōu)化和非常重要，它們最終決定一個最緊湊相鄰結(jié)構(gòu)。有理由相信，沒有某種獨特的數(shù)學方法來計算這些參數(shù)。另外，我們并不能得到一個徹底的研究結(jié)果因為計算時間上的限制，尤其是編排某些具有許多要素和外凸特征的零件及要花費太長的時間用于計算的零件。因此，在本文論述中，應用了一種目前普遍流行的優(yōu)化方法，即GA。它的主要原理如下節(jié)所述。` 圖4 根據(jù)前個定義位置，以編排向量和從屬的旋轉(zhuǎn)編排角度轉(zhuǎn)換得到的相鄰結(jié)構(gòu) 3．2 GA用于優(yōu)化布局 GA在處理預見性問題時保持著流行的趨勢?；谄湫阅?，這些問題的最適解決方法不僅存在，而且類似于有性繁殖，通過與其它的候選方法交換信息而形成的新的一代。在進行任何遺傳操作之前，須定義最適宜功能和偏碼方法。如前所提及的，對零件進行編排的目的在于通過配合串叢圖樣而使它們占據(jù)一最小的面積從而減少廢料。為了表示一個詳細布局的緊湊性，可以確信最直接的方式就是使它和原材料的區(qū)域發(fā)生某種聯(lián)系。 在此，是給定原材料的面積，是從給定的原材料上切下的所有零件圖樣的面積總和。 編碼可以直接或間接地影響優(yōu)化過程，這是因為我們的重點是確定轉(zhuǎn)換位置（例如：偏排向量）和旋轉(zhuǎn)角度（如：偏排角度）因此它們被選作偏碼參數(shù)來引導交疊和遺傳操作的交換待征。 3．3 遺傳算法 該方法最初由Holland提出，GA的目的在于通過模仿自然界的進化過程優(yōu)化解決相關(guān)問題的方法。和人類的進化相似，一個典型的GA算法包括以下的遺傳待征。 3．3．1 初始化 首先，通過隨意選取所有參數(shù)的值產(chǎn)生第一次遺傳操作結(jié)果。在實際工作應用中，經(jīng)常出現(xiàn)限制自由級轉(zhuǎn)的情況，在級進模設(shè)計中，由于設(shè)置一致的導向裝置，減少隨意后進行的薄板沖壓時的彎曲角和相似裝置有較高的費用。用此有許多原始位置區(qū)域限制。圖5所示為兩個具有不同約束和非約束區(qū)域的典型零件，結(jié)果，可以假設(shè)零件被限制折當前情形下的兩個極限角度位置。因此。任意產(chǎn)生一個偏排角度后F面的不等式被證明滿足條件： （ 在此，和是編排零件產(chǎn)行圖樣的數(shù)量（例如：）和零件被約束的位置區(qū)域。 圖5 旋轉(zhuǎn)約束和第一個無約束區(qū)域的次級限制關(guān)系（a）固定圖樣（）：，=30；，。（b）活動圖樣（）：，；，。 3．3．2 適值計算 根據(jù)適宜原理，每一次產(chǎn)生的布局()和適宜值（）決定著的布局的緊湊性。這個值在隨后操作中用來決定將地繁殖步驟選用的候選值。 3．3．3 復制 根據(jù)最適值P，每一分體有一個會被選用于隨后的寬度隨意選擇過程。好的個體，例如高的P值，比低的適合值具有最多的機會被選用，這一點很重要。 3．3．4 疊合 這是決定F一代成員的最重要的一步。繁殖的個體稱作布局i和j在疊合操作中交差了，疊合操作有助于利用其偏排角度或向量。每一個新的值從屬于不相等的情況從而檢查其可用性。 3．3．5 轉(zhuǎn)變 事實上，有多種方法可以完成這種操作。在當前系統(tǒng)中，通過在15范圍內(nèi)隨意旋轉(zhuǎn)相鄰圖樣，1-0.5(Pi+Pj)的可能性外基本上是成功的。 3．4 多零件圖樣的大規(guī)模編排 對于多零件圖樣的切斷問題，前述的運算法則仍然是有效的。為了增大點大的研究空間，一種叢串過程首先用于收集零件。例如圖6所示的8個零件用技術(shù)收集面一種串叢如圖6所示： 串排以后，有一些操作用于移去所有內(nèi)部邊界。因而在隨后的操作中達到更快的計算速度。通過重復上述步驟，最后最終可得到最佳緊湊相鄰結(jié)構(gòu)如圖6C所示?，F(xiàn)在該法已適合于大規(guī)模的偏排。 為了測驗所提示的技術(shù)用于大規(guī)模偏排的效率，把所得到后結(jié)果與傳統(tǒng)偏排技術(shù)如正相似法，由于使用的方法在材料利用方面進行比較。在此使用200X200單位的材料。沒有任何位置限制在零件的偏排方面。一個由正交相近法產(chǎn)生的典型布局和兩個由所提出的技術(shù)得到的布局如圖7所示。相應的，就如所閱述的，本文年出的技術(shù)可以給出一個更加好的解決方法比傳統(tǒng)的方法。此外，這種方法經(jīng)過幾次傳代可得到更優(yōu)化的組合。當材料的尺寸更大時更時如此。當材料尺寸增大時，運用GA方法優(yōu)化偏排向量的值和偏排角度就變得更加重要。 圖6 解決多圖樣編排時原材料切斷問題所涉及的方法 （a）需編排或串叢的圖樣。（b）采用平移方法生成的串叢圖樣。（c）以CAN方法產(chǎn)生的六邊形排樣單元 4 個案研究 為了測驗所提出的技術(shù)用于大規(guī)模編排時的效率，把所得到的結(jié)果與傳統(tǒng)編排技術(shù)如正交相似法（由Nee最先所使用的方法）在材料利用率方面進比較。在此使用200x200單位的原材料，在零件的編排方面沒有任何位置限制。由正交相近法產(chǎn)生的典型排樣圖和兩個由本文中提及的方法得到的排樣圖如圖7所示。就如前所闡述的，本文提及的方法比傳統(tǒng)的方法能給出一個更加好的解決方案。此外，這種方法經(jīng)過幾次遺傳操作可以得到一個最優(yōu)的組合。當材料的尺寸較大時更是如此。當材料的尺寸增大時，運用GA方法優(yōu)化編排向量的值和編排角度值就變得更加重要。 圖7 （a）以直交相近法則得到的布局，材料利用率為72.8％。（b）以CNA方法經(jīng)過首次生成得到的最佳布局，材料利用率為73.9％。（c）以CNA方法經(jīng)過5次遺傳算法后得到的最佳布局圖，材料利用率為74.3％。 5 結(jié)論 對提高編排過程的效率進行了一次嘗試，考慮到零件的初始位置約束，提出了一種對于完全位置約束的零件進行編排的方法（GNA）， 有望發(fā)展成解決多零件編排CNA方法，它以UCU指導用戶獲得近似的優(yōu)化布局。結(jié)合CNA和GA的使用，可得到數(shù)學上的最佳解決方法。該方法適合應用于大規(guī)模的編排過程。在材料的利用方面，證實了本文提出的方法的可行性。