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