规则图形之自动排版系统

《规则图形之自动排版系统》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、不規則圖形之自動排版系統馬恆，李文成，中華大學科技管理研究所摘要切割與排版的問題對於原物料昂貴的製衣業、皮革業與鈑金業來說是常見且重要的問題，其中排版是以原物料使用率最高或浪費為最少為目標，如果以傳統的人工的方式來排版的話，是困難且耗費時間的，另外原料使用率不見得高，所以一套自動且有效的排版系統對於這些產業來說是非常重要的。先前的文獻大都是僅限於特定形狀之型材，如均為直線的多邊形，但當型材是有包含有曲線的不規則形時，不但計算過程非常繁雜而冗長，而且難以找到較佳的排列結果。在本研究中，我們對於在原物料板材上排列包含曲線之不規則型材的排版問題提出一套演算法，其包含兩個

2、主要部份，第一是利用一連串的直線線段來逼近原先圖形的曲線部份，如此便可以以多邊形來代替原先較難計算的不規則形。第二，將型材由大到小一塊一塊依序以研究中所提出之一連串啟發式法則來排列出最終所決定的位置。並將此演算法延伸為一自動排版系統，可讀取由CAD所繪製圖形之檔案，經系統演算後，再將最後的排版結果輸出成可由CAD所讀取之圖形檔案，最後證明可以有效且快速的解決此類問題，而後還可作後續的各項應用。關鍵字：不規則型材、最佳化排版、材料利用率、啟發式演算法1.緒論每個行業所需的排版物件形狀也都不大相同，大致1.1.動機與目的上我們可以分為幾類：(1)相同大小矩形型材的排科

3、技不斷的進步，產業也不斷的在升級，從以版問題(2)不同大小矩形型材的排版問題(3)不同大往的勞力密集產業，逐漸轉型為自動化、科技化的小圓形型材的排版問題(4)不同大小多邊形生產方式，因此產業界莫不一直在思考如何在這競(Polygons)及不規則形(Irregularshapes)型材的排版爭的環境中精簡人力、提高效率及降低生產成本，問題。以獲致更多的利潤和提高產業的核心競爭力。上述的這幾種種類其維度皆限定為二維，由於對某些產業來說，切割／排版問題是其生產的其形狀的種類變化便知其問題的複雜及困難度。由一大課題且佔成本支出重要的一部份，如皮革業、於實際產業上的曲線部分

4、，由於設計之緣故，多為製衣業、鈑金業、家具業及建築業等。所謂的切割圓弧而少不規則或二次式以上之曲線，故本研究只／排版問題，是在一已知大小的原物料版材上，將針對二維由圓弧及直線線段所組成的不規則形材要排列之特定數量的幾何圖形擺放上去，調整擺放作考量，預期所提出來的演算法能有效解決大部分位置，使得切割後，原物料浪費最少，即版材的使業界所面臨的排版問題。用率最高為目標。而目前仍有些業界仍是利用人力來完成切割／排版等相關作業，以鈑金業來說，他2.文獻探討們傳統的排版過程仍是以有經驗的相關人員，依照大部分實際業界所遇到的排版問題都是不同經驗及目視法則來進行，將要切割的形狀試

5、著排出大小多邊形(Polygons)及不規則形(Irregularshapes)一較令人滿意的排版結果，由於此法麻煩、缺乏科型材的，再加上這部分的物件都非常的複雜，困難學分析，不但耗費時間且缺乏效率，極可能造成原度增加，故所提出的文獻也較多。物料使用率低及浪費的情形發生，所以發展出一套在此類問題有些學者，如Adamouicz與Albano有效的排版系統，利用電腦代替人工來進行自動排【1】，Ismail與Sanders【10】皆是針對要排列的版，實是一個非常迫切的需求，尤其對於單位價格圖形進行群聚分析(groupingorclustering)，期望排較高之原料，如

6、特殊金屬、塑材及皮革等，更顯得出方形或接近方形之形狀，然後以方形來替代不規重要，另外更可以降低成本，且縮短產品設計與加則形，因此大大的簡化了問題的困難性，有利於排工之週期時間。版問題的求解。故本研究針對現實中所會遇到的不規則形排Jacobs【12】為解決一群矩形排入一矩形紙版版方式來考量，希望利用科學的方式，發展出一套的排列組合問題，發展出一遺傳基因演算法(GA)自動排版系統，可有效解決排版此類之問題。來求解，最後將此演算法延伸至多邊形圖形最佳排列組合之中，在文中，作者採取左下優先法(Bottom1.2.研究範圍及假設Left，BL)，即欲排入之圖形皆從左下方開始

7、擺放排版這樣的問題普遍存在於各行各業之中，而，並對這些圖形之優先順序及座標進行編碼，然後輸入基因演算法，經過數千次的迭代的演算，最後求得最佳解。A.RameshBabu與N.RameshBabu【18】利用遺資料輸入（不規則之幾何形狀）傳基因演算法與左下優先法相互作用，依其物件擺放角度為0度及90度，所得之八個主要位置，其中有四個是由鏡射得來，然後將基板分割成許多小方利用直線線段來逼近不規則形材格，依左下優先法依序給予數字，如完全被型材覆蓋的基板小方格則定義為0，而部份涵蓋的小方格基板上訂出等分點則由左至右分別定義為1，2，3，...，如此便可得知型材是否有重疊(

8、Overl