采用離散化處理方式

Vol.16, No.2 .2005 Journal of Software 軟 件 學 報 1000-9825/2005/16(02)0316

皮料優化排樣的有效方法. 張玉萍1,2+, 張春麗1, 蔣壽偉2 1(上海師範大學 機電學院,上海 200234) 2(上海交通大學 機械與動力學院,上海 200030) An Effective Approach for Leather Nesting ZHANG Yu-Ping1,2+, ZHANG Chun-Li1, JIANG Shou-Wei2 1(School of Mechanical & Electrical Engineering, Shanghai Normal University, Shanghai 200234, China) 2(School of Mechanical & Dynamic Engineering, Shanghai Jiaotong University, Shanghai 200030, China) + Corresponding author: Phn: [phone], E-mail: [email protected], http://www.shnu.edu.cn Received 2003-10-24; Accepted 2004-04-01 Zhang YP, Zhang CL, Jiang SW. An effective approach for leather nesting. Journal of Software, 2005,16(2):316.323. http://www.jos.org.cn/1000-9825/16/316.htm Abstract: This paper presents an effective nesting method for leather manufacturing, such as automobile interior decoration, etc. After the profiles of leather sheets and stencils are obtained, they are discretized to make the processing independent of the distinct geometry. The constraints of profiles are thoroughly considered. A heuristic bottom-left placement strategy is employed to sequentially place stencils on sheets. The optimal placement sequence and rotation are deterimined using a simulated annealing based genetic algorithm (SABGA). A natural concise encoding method is developed to satisfy the possible requirements of the leather nesting problem. Experimental results show that the proposed mehtod not only can be applied to the normal two-dimensional nesting problems, but also can be especially suited for the placement of multiple two-dimensionally irregular stencils on multiple two-dimensionally irregular sheets as well. Key words: nesting; genetic algorithm; simulated annealing; irregular leather; two-dimensional geometry 摘 要: 根據汽車内飾等行業需求,對皮制品加工的優化排樣問題進行了研究.創新地采用離散化處理方式,同時引進邊界限制,使排樣過程與皮料和樣片的幾何資訊無關,使用基于順序的啟發式底左布局将樣片順次布置到皮料上,樣片的最優布置順序和角度依靠随機優化算法來實作.設計了簡潔、實用的操作算子,并提出了基于模拟退火技術的遺傳算法(simulated annealing based genetic algorithm,簡稱SABGA),該算法在優化搜尋中能自适應地控制變異率,使得優化高效地逼近全局最優解.實驗及對比結果表明,提出的優化排樣方式特别适用于二維不規則形體在多個二維不規則平面上的優化排樣. 關鍵詞: 優化排樣;遺傳算法;模拟退火;不規則皮料;二維幾何 . Supported by the Science-Technology Development Foundation of Shanghai of China under Grant No.005111081 (上海市科技發展基金) 作者簡介: 張玉萍(1963－),女,浙江甯海人,博士,副教授,主要研究領域為CAD及優化技術;張春麗(1972－),女,博士,副教授,主要研究領域為CAD及優化技術;蔣壽偉(1939－),男,教授,博士生導師,主要研究領域為CAD及優化技術.

張玉萍 等:皮料優化排樣的有效方法 317

中圖法分類号: TP391 文獻辨別碼: A 二維幾何形狀的排樣問題廣泛存在于重工業、輕工業、微電子等領域,如金屬闆材、木材、玻璃、皮革、布料等的下料.皮制品被廣泛地應用在生活中,除皮質服裝、鞋帽、箱包、家具外,更涉及汽車、豪華遊輪等内飾領域.皮質原料造價高,形狀不規則,品質不均勻,設計限制條件多且無規律,使得在皮料上尤其是在多個皮料上的排樣極具挑戰性.針對汽車内飾等行業需求,本文對皮制品加工的優化排樣問題展開了研究,探讨在多個任意形狀的皮料上如何最優地排列樣片,研究成果可以直接轉化應用到其他行業. 迄今為止,已有許多算法用于解決不同的排樣問題[1].對于二維不規則樣件,Bennell[2]以及Gomes[3]基于臨界多邊形(NFP)采用的處理方法能夠執行高效排樣,但由于受NFP對幾何輪廓處理方式日的局限,不允許樣件在兩維排放平面内轉動,這不符合樣片在皮料上的實際排樣狀況.Heistermann[4]介紹了他們開發的專門針對皮革工業的優化排樣軟體包,他們采用的是貪婪搜尋方法,将皮料的排樣區分成活動區(live region)和死區(dead region),活動區可排樣,死區不可排樣.存在的問題是:1) 樣片方面,因為這裡将不規則幾何形狀用小的直線段來逼近,如果樣片尺寸越大,它的排樣就越困難;2) 皮料方面,如果皮料表面有瑕疵空洞,孔越多需要排樣的時間越長.當有5個以上時,排樣時間急劇增大,使得排樣所花費時間變得不可忍耐,需要采用搭橋特别處理,使各個空洞歸為死區.這種處理有一個限制條件,就是搭橋長度不能長,否則樣件不能被緊密地排在空洞的旁邊,嚴重影響材料使用率. 以上的啟發式算法給出的均為標明算法的布局排樣結果,未涉及不同的排布順序和模式.研究人員試圖采用某些随機逼近算法[5,6],如模拟退火(SA)和遺傳算法(GA)及人工模拟網絡(ANN)來完成.Heckmann[7,8]等人采用模拟退火算法求解,其中考慮了樣件的任意角度旋轉,主要針對紡織品加工行業,在排樣時考慮了花色、條紋的限制,設定的目标函數由兩部分組成,一個是占用面積,另一個是重疊面積的懲罰函數,通過變動參變量來獲得鄰域空間,這種算法的缺陷是有時會陷入局部最優.Hopper[1]以及Jain[9]介紹了他們在解決排樣問題中采用的遺傳算法,但其研究主要是針對幾何形狀為矩形展開的,實驗結果表明,遺傳算法的使用取得了很好的效果.Hopper更重點研究了排樣的布局政策,針對“底左”布局政策對于大面積矩形形體會産生大的未排面積缺陷,提出了“底左填充”布局方案,所給出的實驗結果也進一步證明“底左填充”政策的有效性. 然而,上述算法最大的問題是僅能針對單個原料進行排樣,本文作者提出了二維不規則形體在多個二維不規則平面上的優化排樣算法.為了使裁剪浪費的材料最少,并提高排樣效率,針對樣片與皮料形狀都不規則的難題,采用離散化技術使處理過程與皮料和樣片的幾何輪廓資訊無關化,結合遺傳算法使得多樣性可以用一種更自然的方法實作,同時采用啟發式的底左布局政策,以這種新的處理政策實作多皮料的排樣.系統流程如圖1所示. Output optimal result Discretization of geometricalInformation placement sequenceand encoding design SABGA combination strategyConversion system for data forms CADplatformDigitizer Production User interactionLeathers and stencils Scanning device Fig.1 Flow diagram of the leather nesting system 圖1 皮料優化排樣流程 1 幾何資訊的擷取以及處理 皮料及樣片的幾何形狀都是二維不規則的,首先要擷取原始幾何資訊并對它們進行處理.現有的技術中有許多途徑可以擷取到它們,如:(1) 掃描皮料,根據灰階和色差,使用軟體轉換出皮料的輪廓圖形.(2) 使用數字化儀直接得到皮料輪廓等.根據現有裝置等條件,我們在實驗中使用了第2種方法.

318 Journal of Software 軟體學報 2005,16(2)

1.1 樣片的旋轉角度 樣片在皮料布置上要考慮一些限制條件,皮料自身有正面和反面之分,是以一般樣片在皮料平面上可以在0°~360°内以任意角度排放.如果需要考慮一些樣片外觀對皮制品的光亮要求,有些樣片可能不允許有角度旋轉,或者被允許在小角度内旋轉,對于角度的限制可以在排樣時直接指定每個樣片的排樣角度. 1.2 幾何資訊的離散化 對于二維不規則幾何形狀,從已有的文獻看,大多采用多個短小直線逼近描述曲線的方法來表達,在排樣過程中,主要通過考察每一個被排樣片輪廓的逼近小折線與皮料上要排放處邊緣的逼近小折線的比對情況來選擇優先排樣序列,但是會出現一些排樣結果很差甚至不可采用等情況.由于皮質材料自身輪廓形狀為不規則曲線,是以如果能有一種方法脫離皮料及樣片的幾何形狀來進行排樣處理,将是非常有益的.受像素處理方式啟發[10],我們提出了離散化的處理方式. 根據皮料實際使用的精度,我們采用間距為t的虛拟網格将圖形包圍在最小的虛拟網格矩形中,t由使用者根據實際需要确定,通過檢索各個虛拟網格小區域中是否有皮料或樣片的輪廓,将各個小區域定義為0或非0,以此将皮料和樣片離散化.這裡我們定義這樣的最小包圍矩形網格為虛拟限制網格,對應的矩形網格輪廓框簡稱虛拟限制矩形框.例如,樣片圖形實際離散化處理為如圖2所示,為解釋清晰起見,我們抽象了一些特例放大圖形.對于樣片,在系統中規定:如果在虛拟網格小區域内及小區域上檢索到圖素,則定義為0,表示需要在對應的位置進行排放;其餘為非0,表示非排放處,如圖2(b),圖2(c)表示圖中間有一個空洞.圖中所有非排放處隻要标的數字為非0就可以,但是為了後續檢索定位友善,我們在進行中使用了編号.這樣可以友善地确定被排虛拟限制網格整體沿x方向移動的距離,加快排放速度.圖3表示皮料上排放了樣件1、樣件2以及樣件3的情況,其中樣件3中有空洞,空洞内正好可以放置下樣件1,虛拟網格中的數值表示在這種排放情況下網格值的變化結果. (a) Stencil 1 (b) Stencil 2 (c) Stencil 3 Fig.2 Discrete grids and corresponding pixel values of different stencils 圖2 各類樣片離散化後的虛拟限制網格圖及網格值Fig.3 Discrete grids and the corresponding pixel values after the placement 圖3 皮料的離散虛拟限制網格圖及對應網格值 為了将矢量資料檔案(DXF,IGES等)轉化成排樣檢索使用的虛拟網格形式的網格值,首先需要構造一個資料結構: struct stencil { int spixel int svalue int sdir int snum };

張玉萍 等:皮料優化排樣的有效方法 319

經過離散轉化算法處理,将皮料以及樣片的幾何資訊轉化成最小虛拟網格矩形包羅的一組網格值資訊,這裡僅給出了對樣片的處理. 2 排樣的搜尋政策和算子操作 如果要在皮料上排放各種樣片,首先要解決采用什麼樣的布置順序将樣片一個個地逐次定位,隻有次序确定了,才可以根據使用的算法周遊可能的情況,并且找出其中排放最佳的一種.我們采用的是啟發式底左順次布置樣片到皮料上的方式(見第2.1節),樣片的布置順序和角度依靠SABGA(simulated annealing based genetic algorithm)進行優化控制(見第2.2節). 2.1 啟發式的底左布局方式 把樣片布置到皮料上,主要就是沿x坐标方向順次檢索皮料上各個網格區域的lvalue值,如果為0,就将樣片定位于此,然後順次檢索被定位的樣片區域内的svalue值是否完全與皮料區域的lvalue值完全為0比對,如果成功,則樣片被排放,如果有不為0情形,檢視lvalue值,将樣片整體沿x正方向移動lvalue值距離,然後再檢索,直到滿足條件為止.當一個皮料被排滿後,可換置一張新的皮料,繼續上述過程,直至所有樣片全部被排完,期間對于恰當樣片的選取順序和布放的合理角度由組合優化方法擷取. Begin (L[x][y]:皮料, S[x][y]:樣片) foreach (所有可以具有一定角度的樣件集合) 定位樣件的虛拟限制矩形框左下角S[0][0]到皮料虛拟限制矩形框可排料的最底左下角L[x][y]; While(1) 應用掃描技術(見第2.2節); if (确定這個位置是否接受,如果接收) 排定該樣件,break; else 獲得皮料L[x][y].lvalue值,沿x軸正向将樣件定位點S[0][0]移動到x=x+L[x][y].lvalue; if (要排的樣件沿x方向排時與皮料虛拟限制矩形框相交), 上移一行從頭檢索,即y=y+1,x=0; if (要排的樣片與皮料虛拟限制矩形框的上邊界相交) 檢查皮料庫是否為空,若是,終止整個排樣程式;否則順序提取下一個皮料并定位樣件S[0][0]到該可排料的最底左下角L[x][y]; endif endif endif endwhile endfor End 2.2 掃描技術 掃描技術就是将樣片區域的像素值與皮料上定位對應區域的像素值逐一進行比較,如果滿足要求都為0,就接收,表示該位置可以排放,如果不為0,采用第2.1節的啟發式算法,移動樣件或做其他的調整,然後再使用掃描技術進行檢索. 3 優化方法 經過上面處理,可以将各種不同的樣片排放到多個皮料上,但是否最省材料,需要采用一個實用的優化算法.為此,我們提出了一種新的組合優化方法,是一種改進了的GA算法,能夠有效地搜尋最優的排放順序和樣片的旋轉角度. 3.1 皮料和樣片的編碼表示 我們提出了一種簡潔、抽象處理的編碼方式,它含括了對多個皮料的處理.首先将各種皮料編上1,2,3等順

320 Journal of Software 軟體學報 2005,16(2)

序代号,樣片也同樣編号.排樣時皮料固定不動,而樣片可以根據需要在平面360°内任意旋轉,此時使用如圖4所示的編碼方式可以表達出在數件皮料上需不同角度排放的多個樣件的排放形式.例如,要在1,2,3皮料上排放6個形狀不同的樣件,每個樣件可以有不同的旋轉角度.具體排放順序見圖4的編碼表,首先是樣件2,旋轉80°排放,然後依次是3,1,4,6和5,以及它們各自要求的角度. Fig.4 Placement sequence and orientation encoding 圖4 皮料和樣件排放順序和角度編碼 Sheet numbersPart number Rotation angle 3.2 交叉和變異算子 定義個體的适應度函數如下: F=1/(A1+A2+…+Ai+…+An.1+Pn) (1) 上式中Ai(i=1,2,3,...,n.1)表示第i個皮料的面積,Pn表示第n個皮料上被排樣區域的面積.對于一組被排樣片,如果排樣結果A越小,這組樣片對應的适應度值越高. 一般地,交叉變異操作是優選具有高的或者較高的适應度值的個體來進行的.交叉過程如圖5所示,對選中的具有較高适應度值的Parent 1和Parent 2進行交叉操作,随機選取兩個位置數,一個指定在皮料編碼區,一個指定在樣片編碼區,如圖指定在Parent 1的編碼序列上,将指定位置右邊的編碼對應各區拷貝到新構造的代碼串中,如Intermediate,Intermediate中的空缺代碼按照Parent 2的編碼順序将沒有出現的皮料和樣片順序填入,這樣就完成了交叉操作,實作了子代的構造. 圖6表示了變異過程,因為代碼分成兩個區域,并且在樣片區域代碼又存在一個變動參數——旋轉角度,是以變異操作分成兩個部分,其一是皮料和樣片的順序編碼,因為各自的序号對應了各個不同的個體,是以産生變化時是在各自不同的區域取兩個随機位置,然後交換它們所對應的代碼,即完成了變異操作,如圖6(a)所示.其二為樣片排放時旋轉角度的可能變化,如圖6(b)所示,它是以一定的機率指定某幾個樣片,對應的樣片角度可以從0°~360°發生變化. Fig.5 Process of crossover operation 圖5 交叉操作過程 Fig.6 Process of the mutation operation 圖6 變異操作過程 交叉以及變異操作都是以一定的機率進行的,交叉機率記為pc ,變異機率記為pm,其值的選取是比較敏感的問題.實驗表明,交叉率pc應該比較大,一般取一個固定值即可,我們使用正交實驗的方法研究了交叉率的取值,最後确定為0.4.相對交叉率,變異率的确定要困難得多,對排樣結果的影響更大、更直接.為此,我們進行了較深入的研究和實驗,找到了一種有效的解決方式,由此提出了一種新的組合優化方法.實驗結果表明,這樣的處理方法非常有效. 3.3 基于模拟退火技術的遺傳算法 在使用普通遺傳算法進行優化排樣過程中,到後期會出現算法不能高效運作,優化過程發生早熟收斂的現象.究其原因是由于後期種群缺乏多樣性,導緻早期收斂.另一方面,确定敏感的固定變異率是一個複雜的問題.模拟退火技術是一種普遍的方法,而不是一種特用算法[11],是以,我們創新地開發了基于模拟退火技術的遺傳算法SABGA,算法中變異率由一個滿足特定冷卻曲線的溫度來控制,由于僅使用了一個參數,Cauchy冷卻方法被采用[12],詳細的算法如下.

張玉萍 等:皮料優化排樣的有效方法 321

SABGA組合算法. (N:種群大小.α,β:變量用來表示種群中的個體.T0:初始溫度.T:溫度.) 開始 1 輸入樣片以及皮料幾何尺寸和角度等限制條件; 2 随機地初始化第1代并采樣建立T0; 3 對第1代中的個體估價适應度; 4 while not (stopCriterion( )) 5 while (innerLoopCriterion( )) 6 foreach (N * 交叉率) 7 基于等級式選擇方法選中第1個雙親; 8 随機地選擇第2個雙親; 9 進行交叉操作産生一個子代; 10 endfor 11 從父代和子代中選出适應度最大的N個個體并作為新的一代; 12 foreach (N/2) 13 對于一個個體成員α的克隆體β進行變異操作; 14 .C=Cost(β)–Cost(α); 15 if (.C<0) 16 α=β; 17 else if (U(0,1)≤e..C/T) 18 α=β; 19 endif 20 endfor 21 endwhile 22 更新T和變異率; 23 endwhile 24 輸出最佳排樣結果; 結束 在輸入了皮料和樣件幾何資訊和限制條件後,随機産生第1代,初始溫度T0與具體問題的規模有關,它為5次随機布局狀态的面積平均值,stopCriterion( )确定了進化過程終止的條件,即在某一代内平均适應度不小于最佳适應度,或者在一個預定義的連續繁衍代内沒有進步發生,或者已完成一組預先指定的繁衍代數.innerLoopCriterion( )在整個進化過程中控制着一個特定的局部平衡過程,10代作為一個局部循環,其中溫度和變異率保持穩定.在複制過程中,交叉操作執行完畢後,就建立一個新的衍生代.變異操作基于新的衍生代中一半的個體成員,這樣不僅加強了随機擾動的效果,而且改善了運作時間上的不足.變異操作是作用在一個成員個體的克隆體上,如果變異後的克隆體的價值小于原始個體或滿足Metropolis公式,原始成員個體被變異後的克隆體取代,否則放棄變異後的克隆體.内部循環體嵌套在外部循環體内,溫度和變異率在内部循環體外被更新,最後輸出搜尋得到的最優個體. 4 實驗結果 我們進行了大量實驗來驗證提出算法的有效性,主要分成兩類,一類是對于各類不規則幾何形狀的樣片在一個或多個皮料上的排樣結果,主要考察該方法的實用結果.另外一類就是擴充使用,對布料、金屬闆材等其他材料的排樣,我們實驗了各種線性多邊形樣件在矩形或線性多邊形平面内的排樣結果,并與Gomes[3],Heistermann[4]和Jain[9]的方法進行了比較.我們所有的工作是用C++程式語言實作的,使用的計算機微處理器是Pentium II,主頻333MHz,記憶體128 MB,作業系統為Windows. 圖7為標明10,20,30,65和100五種不同種群規模的實驗,它顯示了種群規模與獲得優化結果運作代數的關系,結果表明,算法是逐漸收斂的.對于種群數在30~100的規模,具有相似性,經過約650代運作後,物種新的變化特征已經喪失,收斂結果之前已經産生.為減小計算時間,我們設定種群數為30. 圖8為在3個不規則皮料上排放64個不規則樣片的實驗,皮料1上有9個瑕疵,排放了26個樣片,材料利

322 Journal of Software 軟體學報 2005,16(2)

用率為78.80%,皮料2上有2個瑕疵,排放了26個樣片,材料使用率為80.02%,皮料3上有一個瑕疵,将12個樣片排放其上,未排滿,它的有效材料使用率是73.6%.一共運作了760代,耗費的CPU時間是43′22″.使用我們這種幾何處理方法,在排樣中能夠很好地識别孔洞,獲得的排樣效率能夠達到要求.從排樣結果來看,并非都是較大面積的樣片先排就能獲得較高的排樣效率,這需要根據樣片和皮料的具體形狀全局确定. 60657075808525125225325425525625725GenerationMaterial Usage Rate(%)10203065100 (a) 9 flaws (b) 2 flaws (c) 1 flaw Fig.7 The efficiencise and generations for different population sizes 圖7 不同種群規模運作的效率 Fig.8 Nesting results in three sheets 圖8 非規則樣片在3個皮料上排樣的情況 Our approach Our approach Our approach Heistermann[4] approach Gomes[3] approach Jain[9] approach (a) (b) (c) Fig. 9 Comparsion between our apporoach and the approaches from Heistermann[4], Gomes[3] and Jain[9] 圖9 我們的方法及Heistermann[4],Gomes[3]和Jain[9]方法對線性多邊形樣片在單個矩形平面中的排樣執行個體 19818526425712944510020030040081.9%71.2%79.8%62.5%100%100%60%70%80%90%100%our approach GomesHeistermannJainabc(d) Comparison of material usage rates abc (e) Comparison of runtimes 相對于文獻所介紹的Heistermann[6]和Gomes[8]排樣方法,這裡進行了3組比較實驗,如圖9所示.圖9(a)為在單個給定皮料上排放15~20個給定樣片,用我們的方法,15個樣片經過427代進化得到排樣優化結果,與Heistermann方法相比,不但所用時間少,而且材料使用率提高約10%.圖9(b)為在一個長度界限不定的平面内排放4類共計43個多邊形樣件,我們的方法因采用左底政策,是以需先對排樣平面旋轉預處理,成為高度可變平面,經過601代進化後,獲得優化結果,将其反轉90°回原位.與Gomes方法結果比較,排樣效率提高12.49%. 圖9(c)為3種14個線性多邊形樣件在40mm×60mm矩形平面上的排樣.通過表1的數字可以看出,我們提出方法的有效性.3組實驗的效率和CPU運作時間的比較如圖9(d),圖9(e)所示. 以上兩類實驗表明,我們提出的優化方法能快速、有效地将各類樣片排放到各類型單個或多個平面中,尤其突出的是,它能夠靈活地完成非規則形狀的樣片在多個非規則平面上排樣的功能,并且材料使用率能夠達到70%以上,排樣時間在使用者接納範圍内,對于50個樣片在10個平面内的排樣規模,通常1小時内可以完成,這對于皮革加工業是可以接受的.

張玉萍 等:皮料優化排樣的有效方法 323

Tabel 1 Comparison between our apporoach and the approach from Jain[9] on an example of nesting multiple polygon parts in a single rectangle 表1 兩種方法排樣的資料對比 Method Our approach Jain[9] approach Pattern size (mm×mm) 40×20 25×45 25×40 20×45 20×40 Number of generations 302 1 10 20 100 Utilization (%) 100 71.1 80 88.8 100 CPU time 2′9″ 21″ 1′32″ 2′49″ 7′25″ 5 結 論 文中創造性地将皮料和樣片進行離散化處理,同時引進邊界限制,使得後續算法的處理對象統一化,因而提出的優化排樣方式特别适用于形狀不規則的二維形體.采用幾何資訊離散化的處理方式,徹底解決了輪廓幾何限制的困擾,基于順序的底左排放政策使得優化排樣順利進行,樣片順序和旋轉角度的選擇依靠SABGA算法來搜尋完成.SABGA算法集中了GA和SA的優點,它在完成排序搜尋過程中,還很好地處理了變異率的選取,利用模拟退火算法的特長對變異操作施加自适應控制,由一個滿足特定冷卻曲線的溫度來控制,使得遺傳算法的随機染色體變化在優化的初始階段比較大,然後越來越小,直到最後搜尋收斂為止,這樣抑制了優化過程的早熟收斂.我們提出的這種優化方法不但适用于不規則形體在單個或多個不規則表面的排樣,也适用于規則形體在單個或多個規則平面上的排樣,實驗結果表明,我們的處理方法是具有廣泛使用意義的. References: [1] Hopper E, Turton BCH. A review of the application of mete-heuristic algorithms to 2D regular and irregular strip packing problems. Artificial Intelligence Review, 2001,16:257.300. [2] Bennell JA, Dowsland KA, Dowsland WB. The irregular cutting-stock problem—A new procedure for deriving the no-fit polygon. Computers and Operations Research, 2001,28(3):271.287. [3] Gomes AM, Oliveira JF. A 2-exchange heuristic for nesting problems. European Journal of Operational Research, 2002,141(3):359 .370. [4] Heistermann J, Lengauer T. The nesting problem in the leather manufacturing industry. Annals of Operational Research, 1995,57: 147.173. [5] Xing WX, Xie JX. Modern Optimization Calculation Methods. Beijing: Tshinghua University Press, 2000 (in Chinese). [6] Reeves CR. Modern Heuristic Techniques for Combinational Problems. Oxford: Blackwell Scientific Publications, 1993. [7] Heckmann R, Lengauer T. A simulated annealing approach to the nesting problem in the textile manufacturing industry. Annals of Operational Research, 1995,57:103.133. [8] Heckmann R, Lengauer T. Computing closely mathing upper and lower bounds on textile nesting problems. European Journal of Operational Research, 1999,108(3):473.489. [9] Jain S, Chang HG. Two-Dimensional packing problems using genetic algorithms. Engineering with Copmuters, 1998,14(3): 206.213. [10] Cui Y. The Processing and Analysis for Images. Beijing: The Science and Technique Publisher, 2000. 65.86 (in Chinese). [11] Babu AR, Babu NR. Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms. Int’l Journal Produce Research, 1999,37(7):1625.1643. [12] Liu Y. Simulated Annealing with a Potential Function with Discontinuous Gradient and an Adaptive Simulated. Beijing: Peking University Press, 1999. 15.80. 附中文參考文獻: [5] 邢文訓,謝金星.現代優化計算方法.北京:清華大學出版社,2000. [10] 崔屹.圖像處理與分析.北京:科學技術出版社,2000.