咖啡粉枕式包裝機總體設(shè)計及計量裝置設(shè)計含開題、Proe三維及13張CAD圖,咖啡,粉枕式包,裝機,總體,設(shè)計,計量,裝置,開題,Proe,三維,13,CAD 布局優(yōu)化的掩模固化快速成型工藝 X. Zhang， B. Zhou，Y. Zeng，P.Gu* 唐佳紅 譯 機械制造工程系、卡爾加里大學，大學路2500，卡爾加里，加拿大艾伯塔省T2n1n4 摘要 快速成型制造技術(shù)，可直接用于CAD模型的產(chǎn)品開發(fā)，制造工具和制造模具以及功能部件。掩模固化(SGC)技術(shù)中的快速成型技術(shù)， 適合建立多種不同零部件的快速成型樣機幾何尺寸的批量生產(chǎn)，其成本降至最低。 然而，平面CAD模型環(huán)境的布局是費時的。 由于樹脂的成本高， 一批SGC的業(yè)務在任何工業(yè)環(huán)境中的布局模式是成功的關(guān)鍵。 本文利用模擬退火布局優(yōu)化技術(shù)。開發(fā)一個軟件系統(tǒng)是為了協(xié)助前部分進行各種型號的CAD幾何形狀的布置。 STL系統(tǒng)接受來自任何實體造型環(huán)境的信息。下面提供幾個例子來說明技術(shù)的有效性。 1. 引言 全球的主導產(chǎn)品競爭日益需要廠商更加靈活地適應瞬息萬變的市場需求。 大幅削減產(chǎn)品開發(fā)時間將改善企業(yè)對市場的需求，因此贏得競爭優(yōu)勢。 快速成型制造技術(shù)也不斷提高了廠商建立三維模型和原型等幾方面快速反應能力; 而具有成本效益的生產(chǎn)模式和復雜模具曲面[1]的快速成型技術(shù)可直接從CAD模型生成原型。 各種快速成型技術(shù)的出現(xiàn)，包括固化、選擇性激光燒結(jié)(SLS)、熔融沉積制造、疊層實體制造、三維印刷和掩模固化(SGC)。它們有一個共同特點:成型制作是加入材料而不是像傳統(tǒng)的去除材料或變形工序[2]。 這些技術(shù)可以填補空間不確定具體部分的概念設(shè)計。該技術(shù)也可大大提高工作效率和模具制作工藝格局。 SGC的過程能在單一格局內(nèi)生產(chǎn)多種不同形狀和尺寸的零件，因此適合批量生產(chǎn)。 在SGC的制造過程中(圖1)，使負截面的一部分產(chǎn)生靜電收取玻璃板。這就像平時使用的激光打印機。 在此期間，一層液態(tài)固化樹脂是一種分布式的到位工作。 然后放在工作空間的燈和表面之間用玻璃板擋起來，不是用激光束或者是紫外線燈注滿空間和照亮整個層。剩余的液態(tài)樹脂是用吸塵器抹去。 向后移動的樣盤上曝露在紫外線燈下第二次凝固的液態(tài)樹脂沒有被吸塵器完全清理干凈。 在這層充滿熱蠟液的空間，蠟被一個冷態(tài)金屬碟子冷卻到固體之后，這個樹脂蠟層被刀具快速的粉碎成指定的大小。樣盤從磨床回到曝光廳后，樹脂的新層被應用。SGC程序能同時由一個限制簡單的CAD 模型形成多個復雜部件的玻璃裝料碟子。 因此，可以用來生產(chǎn)機器前部分分批多型號。 然而，在SGC的建立過程中， 樹脂不能被重復使用，因為它已經(jīng)部分被恢復。 如果我們要建立一個單一的部分，并且沒有其它任何地方共享區(qū)段，這部分可以很昂貴，除非占有大多數(shù)的托盤模式。 此外， 大多數(shù)其它快速成型機必須依次編織每個過渡部分。 雖然這些時間可由機器同時生產(chǎn)多種零部件而減少，生產(chǎn)時間的長短取決零件的數(shù)量和零部件的幾何形狀。 在SGC的過程中，每一層曝露在具有相同時間紫外線燈下的跨度為預設(shè)操作。 因此消費和制造樹脂的每一層時間都是固定的， 一批獨立的幾何形狀和數(shù)量的零部件。 因此， 當一批零部件的生產(chǎn)成本單純依靠被生產(chǎn)層的數(shù)字時，為了最大限度地減少成本和生產(chǎn)率， 各地應在每一批'封裝'時給予盡可能低的示范區(qū)，使托盤制作的一批零部件成本降到最小。 當兩個或兩個以上的部分是在在三維圖形環(huán)境中同一時間制造時，具體操作模擬包裝件應放置在它們或它們的CAD模型上。在計算機屏幕上的一個封袋內(nèi)，可保證部件不相互干涉， 而且它們完全在限制的體積之內(nèi)。 每批零件可用于不同的程序和不同客戶。 因此零件形狀和大小可以相差很大， 使得很難找到用手動解決的最佳經(jīng)營模式的布局。 因此，需要找到一個電腦系統(tǒng)的優(yōu)化，配置一批生產(chǎn)成本最低的布局。 圖1 描述SGC的制造過程 2. 相關(guān)研究工作 布局問題的模型可歸納為典型裝箱問題。 應用裝箱問題可用在集成電路設(shè)計、切割和股票等其它領(lǐng)域。典型的二維和三維裝箱問題已被證明是疑難問題[3]。生產(chǎn)效率最優(yōu)解的密切近似算法的開發(fā)對裝箱問題具有重要現(xiàn)實意義是。 這些方法包括:線性規(guī)劃、啟發(fā)式技術(shù)，模擬退火(SA)和遺傳分析(GA)。 線性規(guī)劃方法已成功地廣泛應用于學習、普通切割的問題中。 然而，由于它們的結(jié)構(gòu)或大小，這些方法對許多真正的問題是不適當?shù)摹?在這種情況下，應用啟發(fā)式手段，如動態(tài)規(guī)劃搜索方法。 動態(tài)規(guī)劃法是一種把單個問題轉(zhuǎn)換成一系列單階段問題的算法其難度是如何迅速確定最優(yōu)決策。樹-搜索的方法是將所有可能的解決方法羅列成樹狀結(jié)構(gòu)，在同一條路徑上開始和結(jié)束，當其被認為是已經(jīng)找到的最佳答案或者是已經(jīng)知道會造成令人不滿意的解決方案。上述大部分辦法要么不給最佳或接近最佳的解決方案要么不適用多種應用而且比較復雜形式的問題[4]。 為克服線性規(guī)劃、啟發(fā)式方法的局限， 研究成果已使用SA和GA解決封裝問題。 rao及Iyengar[5]適用于多樣化的裝箱問題。 大量仿真實驗表明典型的啟發(fā)式方法已經(jīng)顯著的改進。 cagan[6]摸索SA用二維和三維解決問題。適應退火時間表，多分辨率建模與動態(tài)步驟提出改進策略選擇算法性能。 Han和Na [7]嵌套方法提出了兩個階段:初級布局階段，改善布局階段。 自組織算法輔助設(shè)計制造了一種'優(yōu)的'初步布局; 然后用SA布局作初步改善。 Corcoran [8]探索GA問題在三維封裝中的應用以便GA更好的解決三維封裝問題。 值得一提的是，ikonen等[9]用GA來為機器解決三維模型的規(guī)劃問題。 上述的研究大多簡化了零部件的形狀。 ikonen幾何方法的零件不需要在封裝前簡化。 不過用這個方法搜索的封裝過程可能非常費時 (例如15個部件需要8.5小時)。 總之，已證明它有解決GA和SA裝箱問題能力。不過，GA和SA在效率和效益上很大程度取決于空間解來實施策略和目標功能。 在這項研究中， SA算法目前應用于封裝的具體問題，根據(jù)客觀戰(zhàn)略SGC的搜索功能和過程。 3. 制定示范布局問題 在這項工作中，SGC的模盤代表容器的上限。 這個問題的布局模式研究一批堪稱封裝大小不同零件的容器(集裝箱)。 封裝任務具有以下三個目標: *裝修進入指定型號集裝箱; *避免模型重疊; *實現(xiàn)高密度封裝，換句話說，實現(xiàn)最低整體水平。 在目前的應用中， 每一部分CAD模型用STL格式來表示。它由三角面坐標數(shù)據(jù)及其相應三維空間表面組成。 相對于其它格式的CAD模型，STL格式非常簡單。 然而，如果STL模型是一個完整的信息編碼算法，搜索會很費時，這是因為很平常的機械部分有成千上萬的三角面的STL模型，一個簡單操作如'旋轉(zhuǎn)'或'移動'就是重新定位每一個三角面的新模式。 此外，這些動作都是用數(shù)千'迭代'在SA搜索過程，因此簡化是必要的。 大多數(shù)的研究者只是包抄一部分，因為它是一個長方形盒子容易執(zhí)行，使包裝算法變得過于復雜 [4]。 這種方法還用于這項研究。 不同之處在于制定具體的搜索功能和戰(zhàn)略目標。 三維模型圖可以描述以下步驟(圖二): 1.解析STL文件的零件制造、每一個封閉部分產(chǎn)生示范。 2. 據(jù)具體算法封裝。箱體批量的大小相同，機器的最大體積相同。 3. 計算每一部分更新STL文件。 4. 最后結(jié)果顯示布局。 步驟1，3，4涉及計算機圖形學、可視化技術(shù)、 所不明確的問題，涉及到包裝、較易執(zhí)行現(xiàn)有圖形工具。 我們的重點是在第2步。 制定這一問題的關(guān)鍵是樹立正確的算法。 裝箱問題可以作為最優(yōu)化問題是方程。 (1): CAD文件包括所有生產(chǎn)包裝信息的部件 圖2 典型包裝的程序 其中n是模型的數(shù)量、pi是封裝狀態(tài)模型、p是布局、 P是一批規(guī)劃布局、B是輪廓邊界Pi∩Pj兩模型之間的交接、 Pi∩B箱體邊界和模型之間的交接、h總體規(guī)劃高度與f高度目標函數(shù)映射成為集P實數(shù)。 目前這個問題，是一個單批零件的布局滿足限制方程(1)的界定。 目標函數(shù)定義為整體的布局高度。 典型的封裝狀態(tài)是由封袋的位置和方向決定的。 每一個部分的坐標是由封袋的幾何中心定義的。集裝箱的左下角定義為整體的坐標原點。 封袋的幾何中心確定封袋在箱中的位置。 典型的方位有六個如圖(3)所示。 一個狀態(tài)對另一個狀態(tài)的轉(zhuǎn)變可通過一個或兩個旋轉(zhuǎn)操作實現(xiàn)。旋轉(zhuǎn)操作是局部調(diào)整旋轉(zhuǎn)軸附近的封袋。 例如，圖(3)把封袋的一種狀態(tài)換成另一種狀態(tài)，它可以繞X軸旋轉(zhuǎn)也可以繞Y軸旋轉(zhuǎn)。 每個封裝袋表面總是平行或垂直于正交軸。所以每個封袋的形式pi表示為: 其中xi、 yi 、zi 相對應的表示第i個封袋的頂點。 θi 表示它的方向，n是用來記數(shù)的;Xi 、Yi、 Zi 表示第i個封袋沿x、 y、 z 方向的長度。 目標函數(shù)f 定義為在有效方向上搜索到的合適的點。在這項研究中，目的是盡量減少總體布局的高度可以由下列公式: 圖3 自由度導向示范 在搜查過程中， 通過已知的模型結(jié)果搜索更加準確的解決方法。 在最后目標函數(shù)的設(shè)計中應該避免重疊。 因此目標函數(shù)有兩個條件f2: 當兩個平行長方形箱子重疊，重疊部分也是一個長方形。 在方程(4)中Oij(x)、 Oij(y)和Oij(z) 表示第i個箱子和第j個箱子重疊部分沿x 、y 、z 方向的長度。Oij 表示重疊部分三個方向長度的總和。 重疊量化方程(4)的線性疊加最常用于多目標函數(shù)優(yōu)化[7，9]: 不過，這個功能很少能夠成功的優(yōu)化這個封裝的問題。 在搜索過程中， 解答f值方法是搜索目標函數(shù)值。 不同的重量物品的比較結(jié)果，可以不同。 因此這兩個重量相對價值是至關(guān)重要的。f2變化范圍是由各部分的數(shù)量和大小決定的，一對'重量'不同包裝情況找不到一個比較好的方法。 即使有重疊和客觀高度的值也很難找到數(shù)學方法決定自己價值。如果w2遠大于W1;目標函數(shù)將更為敏感變更重疊量f2: 該模型將放置在搜索過程初期消除重疊。最后，將模型在集裝箱里堆高，如果高度比意義更是值得考慮，較為敏感的全局高度和重疊量的目標函數(shù)將變化，因為目標函數(shù)值將因為高度下降而減少。 避免難以確定的重量值、 非線性目標函數(shù)和定義使用于這項研究。 下面的目標函數(shù): 重疊高度上限是由集裝箱高度決定的。當f2=1時因為f2<1無法成立函數(shù)值使f等于0， 否則會引起沖突。換句話說，當目標函數(shù)值不再減少，就不會得到改善。 在方程(4)重疊兩個封袋重疊長度的計算總結(jié)三個方面。用數(shù)學給這兩個封袋重疊部分定義合適的目標函數(shù)方程(7): 在搜查過程中利用非線性目標函數(shù)搜索重疊的客觀職能是好的， 假設(shè)移動不可行組態(tài)(布局)可以導致上級可行配置(布局)[4]。 以此為目標函數(shù)， 算法引導搜索的走向會降低，布局重疊高度后已經(jīng)很小。雖然還存在小小的重疊的型號，最后的總體布局的高度普遍較低。 SA辦法來解決上述問題的最優(yōu)解比較試驗都是封裝重疊量化使用重疊方程(4)確定。SA辦法在使用第一種方法時表現(xiàn)較差或沒有更好的表現(xiàn)。測試結(jié)果將在后文表明。 這里指的封裝算法不能保證找到一個可接受的解決方案。 消除重疊解決小SA所得的補償算法是一個簡單的程序。 SA搜索過程完成后，如果存在重疊， 補償程序可以找出重疊模型和解決措施，顯示他們最低重疊量。 由于可能產(chǎn)生新的重復動作，再次檢查所有型號； 是否出現(xiàn)新的重疊，直到程序沒有繼續(xù)存在的重疊模式。重疊在大多數(shù)情況下，可以輕松地解決后執(zhí)行這項補償計劃。在測試的情況下，整體水平SA提高不明顯。 4. 模擬退火方法 4.1 觀念SA SA是基于物理概念金屬熱處理為了找到最低能量金屬狀態(tài)。數(shù)學方法是用退火冷卻時間表，這是一個使功能下降的方法。SA是一個統(tǒng)計力學隨機計算技術(shù)尋找附近所有最低成本所得的解決大型優(yōu)化問題的方法。 在許多情況下， 尋找一個客觀的取小價值與功能的自由度受到許多限制，是一種矛盾的疑難問題。由于有許多客觀的功能將趨于局部極小。優(yōu)化程序解決這類問題，應尋找樣本空間，如此才能使尋找最優(yōu)或接近最優(yōu)解在合理時間有一個高的概率。 SA是由Kirkpatrick et al [10]決定的。 這一構(gòu)想源自Metropolis[11]。 最初的起始溫度T; 給予最大值，并假設(shè)系統(tǒng)處于初始狀態(tài)開始計算目標函數(shù)值f。國家規(guī)定用p表示; 然后測試六個點的轉(zhuǎn)變職能。 如果此舉導致目標函數(shù)有所改善， 用新的函數(shù)代替原函數(shù)。其目標函數(shù)值也用這個新解。這可以大概計算目標函數(shù)值。 共認的概率決定如下: 溫度值開始隨時間下降。 每個溫度系統(tǒng)都有幾次不穩(wěn)定。這反復進行溫度迭代計算稱為Markov鏈。迭代連環(huán)次數(shù)稱為鏈長。最初，動作通過空間狀態(tài)幾乎隨機的，造成了廣泛的探索空間的客觀功能。由于概率接受劣質(zhì)動作下跌，它們往往很難使算法收斂到最優(yōu)。 5. 封裝策略 5．1. 運動裝置 SA從解(s)開始搜索的一個或多個進程，然后選擇認定其預先的解。 此過程用“φ”表示; 這是一種新穎的操作辦法p’可以從舊的中得到， 移動裝置是由各個動作依據(jù)模型布局組成。 當新布局由舊產(chǎn)生，一個動作是有移動裝置中幾個可能的動作中選出的。 在運動裝置中定義六個動作的問題如下: *轉(zhuǎn)動。 改變封袋方向一個模式不改變中心位置封袋。 共有6個方向可以選擇。 然而，可能性最小的方向給予更多的高度封套。 *漫步。 隨意改變的中心位置在封袋正負x 正負y 正負z方向，貨廂的運動方向和移動距離取決于當前的溫度。 在更高溫度較長距離的運動，企圖將選擇一個更大的變化，實現(xiàn)功能的成本，并避免局部極小。 *交換。 改變兩個封袋地點; 兩個封袋是隨機抽選調(diào)換。 *回到起點(0，0，0)。 隨機挑選封袋提出一個方向，使沿線的X; Y和Z座標，封袋溫度減少的那一刻將減少移動距離。 *'消除'重疊。 計算向量之間重疊每個封袋沿線移動相應載體。 這一行動旨在減少整體重疊、 其實并不能消除重疊，因為以后排除一切可能產(chǎn)生重疊的新舉措。 *靠墻移動。 在提出抽樣封袋x-y平面(不改變其Z坐標位置)，直到它觸及墻往就近封袋或其它容器壁、 然后向下直到它觸及封袋或其它容器底部。 實際上有兩個在移動裝置中的基本操作旋轉(zhuǎn)、漫步中， 其它被視為一個特殊的操作或動作順序。 后者的主要目的是提高四個業(yè)務的算法效率。 5．2． 重疊計算檢測 重疊計算評價兩個或兩個以上封袋重疊的程度。封袋預計二維平面坐標，這使計算方便。 一旦有重疊的兩個封袋，就有重疊每個二維平面(X-Z、X-Y、Y-Z平面)。 如果任何兩個平面之間沒有重疊，這兩個封袋之間就沒有重疊 如圖(4)。 圖4 模型布局優(yōu)化算法SA 6.結(jié)論 快速成型制造技術(shù)可大幅度降低產(chǎn)品開發(fā)時間，迅速適應市場需求。作為一個普通的快速成型技術(shù)工藝，能生產(chǎn)多種零部件SGC的同步進程。不過，需要做研究，以減少生產(chǎn)成本，提高機械效率。 SGC的SA過程用于解決在模型中布局優(yōu)化、發(fā)現(xiàn)問題，提高了生產(chǎn)效率和降低成本。新的目標函數(shù)功能將于傳統(tǒng)線性函數(shù)相比較。有效的比較辦法是SA。 軟件開發(fā)工具包可以從機器上減少繁瑣且未必有效的工作部分。它也可以由工程師接收STL格式。封袋自動生成和更新的STL文件的封袋型號以及相應布置的辦法。 最后的布置可轉(zhuǎn)為VRML的格式和可視VRML。 最新日志檔案可直接裝入機床制造一批多種零部件。 致謝 這項研究得到了加拿大自然科學及工程研究理事會 (NSERC)戰(zhàn)略性str192769補助。 參考資料 [1] Yan X， Gu P. A review of rapid prototyping technologies and systems. Computer-Aided Des 1996;28(4):307–18. [2] Kruth JP. Material increases manufacturing by rapid prototyping techniques. Ann CIRP 1991;40/2:603–13. [3] Garey MR， Johnson DS. Computers and intractability: a guide to the theory of NP-completeness. San Fransisco: W.H. Freeman and Co.， 1979. [4] Szykman S， Cagan J. A simulated annealing-based approach to three-dimensional component packing. J Mech Des 1995;117: 308–14. [5] Rao RL， Iyengar SS. Bin-packing by simulated annealing. Comput Math Appl 1994;27(5):71–89. [6] Cagan J. A shape annealing solution to the constrained geometric Knapsack problem. Computer-Aided Des 1994;28(10):763–9. [7] Han G-C， Na S-J. Two-stage approach for nesting in twodimensional cutting problems using neural network and simulated annealing. J Eng Manuf 1996:509–19. [8] Corcoran III AL， Wainwright Roger L. A genetic algorithm for packing in three dimensions. Symposium on Applied Computing(SAC 92)， Kansas City， March 1–3， 1992， p. 1021–30. [9] Ikonen I， Biles WE. A genetic algorithm for optimal object packing in a selective laser sintering rapid prototyping machine. Seventh International Conference on Flexible Automation and Intelligent Manufacturing， Middlesbrough UK， 1997， p. 751–9. [10] Kirschman S， Gelatt II CD， et al. Optimization by simulated annealing. Science 1983;220:671–80. [11] Metropolis M， Rosenbluth A， et al. Equation of state calculations by fast computing machines. J Chem Phys 1953;21:1087–92. Model layout optimization for solid ground curing rapid prototyping processes X. Zhang, B. Zhou，Y. Zeng，P. Gu* Department of Mechanical and Manufacturing Engineering, The University of Calgary, 2500 University Drive, Calgary, Alberta, Canada T2N 1N4 Abstract Rapid prototyping technologies are capable of directly manufacturing physical objects from CAD models and have been increasingly used in product development, tool and die making and fabrication of functional parts. Solid ground curing (SGC) technology, one of the rapid prototyping technologies, is suitable of building multiple parts with different geometry and dimensions in batch production of rapid prototypes to minimize the cost of prototypes. However, the layout of CAD models in a graphic environment is time-consuming. Because of high cost of the resin, the layout of models in a batch is critical for the success of the SGC operations in any industrial environment. This paper presents the layout optimization using simulated annealing techniques. A software system was developed to assist Cubital operators to layout CAD models with various geometric shapes. The system accepts STL files from any solid modeling environment. Several examples are provided to illustrate the techniques and effectiveness of the approach. 1. Introduction Increasing global competition requires product oriented manufacturing firms to become more flexible and responsive to the ever-changing market. Substantial reduction of product development time will improve firms’ response to market demands and therefore gain competitive advantages. Rapid prototyping and manufacturing technologies have been improving manufacturers’ responsiveness in several aspects such as rapid creation of 3D models and prototypes; and cost-effective production of patterns and moulds with complex surfaces [1]. Rapid prototyping technologies are capable of directly generating physical objects from CAD models. A variety of rapid prototyping technologies have emerged including stereolithography, selective laser sintering (SLS), fused deposition manufacturing, laminated object manufacturing, 3D printing and solid ground curing (SGC). They have a common feature: the prototype is produced by adding materials, rather than removing or deforming materials as in traditional manufacturing processes [2]. These technologies can fill the uncertainty void between the conceptual design and an actual part. The technologies can also significantly improve the efficiency of pattern and mould making processes. SGC processes can produce multiple parts with different geometries and dimensions in a single setup and therefore are suitable for batch production. In the building process of SGC (Fig. 1), a mask is generated by electrostatically charging a glass plate with a negative image of the cross-section of the part, which is similar to the process used in the laser printer. In the meantime, a thin layer of liquid photo-curable resin is spread across the surface of the work place. Then, the glass plate with the mask is placed between the lamp and the surface of the workspace. Instead of using a laser beam, an UV lamp is used to flood the chamber and expose and solidify the entire layer. After the residual liquid resin is wiped off by a vacuum cleaner, the model tray moves back under the UV lamp for a second exposure that solidifies the liquid resin that is not totally cleaned by the vacuum. The voids in this layer are filled with hot liquid wax, which acts as support for overhangs and isolated parts. After the wax is cooled down to solid by a cold metal plate, this resin/wax layer is milled with a fly cutter to a specified thickness. The new layer of resin is applied when the model tray moves from the milling station back to the exposure chamber. The SGC process can produce multiple parts at the same time by simply slicing a batch of CAD models and charging the glass plate with a negative image of multiple cross-sections. Thus, Cubital machines can be used for production of multiple models in batches. However, in the building process of SGC, the resin that does not contribute to the part and is wiped off cannot be reused because it has been partially cured during the initial exposure. If one needs to build a single part and there are no other parts to share the block, this part can be very expensive unless it occupies most of the model tray. Moreover, most of the other rapid prototyping machines have to weave the cross-sections of each part in a batch one by one. Although the lead time on these machines can be reduced by producing multiple parts, the production time does depend on the number of parts and the parts geometry. In the SGC process, the UV lamp exposes every layer with the same time span as predetermined by the operator. Thus the resin consumption and fabrication time per layer are constant, independent of the parts’ geometry and the number of the parts in the batch. Consequently, the time and the cost of producing a batch of parts simply depend on the number of layers produced in the fabrication. In order to maximize productivity and minimize cost, parts in every batch should be ‘packed’ as low as possible within the given area of the model tray so that the fabrication layers for the batch of parts can be minimized. When more than one part is manufactured at the same time, within the 3D graphic environment, the operator simulates packing of actual parts by placing them, or their CAD models, inside an envelope on a computer screen and makes sure that parts do not intersect with each other, and that they are totally inside the building volume. Parts in each batch can be used for different applications and for different customers. Thus the shape and size of parts can vary dramatically, which makes it even more difficult for an operator to find an optimal model layout solution manually. Therefore, a computerized system is needed to find the optimal batch configuration layout for the minimum cost of production. 2. Related research work The model layout problem can be categorized into the well-known bin-packing problem. Applications of the bin-packing problem can be found in VLSI layout design, stock cutting and other fields. The classical 2D and 3D bin-packing problems have been proven to be NP-hard [3]. Since the bin-packing problem is of practical importance, efficient approximation algorithms that produce close-to-optimal solutions have been developed. These approaches include linear programming, heuristic techniques, simulated annealing (SA) and genetic algorithm (GA). Linear programming methods have been extensively studied and successfully applied to a broad class of stock cutting problems. However, these methods are not appropriate for many real problems due to their structures or sizes. In such cases, heuristic methods are used, such as dynamic programming and tree-search methods. Dynamic programming is a method that converts a problem into a series of single-stage problems. The difficulty is in quickly determining the optimal decisions. The tree-search method enumerates all possible solutions in a tree Dynamic programming is a method that converts a problem into a series of single-stage problems.-like structure. Heuristics start out on one path and terminate when either an optimal solution is believed to have been found or the path is known to result in an unsatisfactory solution. Most of the above approaches either do not give an optimal or near optimal solution or are not applicable to a wide variety of applications, and the formulations of problems are rather complicated [4]. To overcome the limitations of linear programming and heuristic techniques, research efforts have been made using SA and GA to solve packing problems. Rao and Iyengar [5] applied SA to a variety of the bin-packing problems. Extensive simulation experiments demonstrated that the solutions obtained by SA showed a significant improvement over those obtained by any of the well-known heuristic methods. Cagan [6] explored 2D and 3D layout problems using SA. An adaptive annealing schedule, multi-resolution modeling and a dynamic move selection strategy were proposed to improve algorithm performance. Han and Na [7] proposed a nesting approach with two stages: initial layout stage and layout improvement stage. A self organization assisted layout algorithm generates a ‘good’ initial layout; then SA was used to improve the initial layout. Corcoran [8] explored GA in 3D packing problems and showed that GA yielded good solutions for 3D packing problem. It is worthwhile to mention that Ikonen et al. [9] used GA to solve a 3D model layout problem for an SLS machine.Most of the research mentioned above simplify shapes of the parts. Ikonen’s approach does not require geometry of parts to be simplified before packing. However, the searching process of the packing can be very time-consuming using this method (e.g. 8.5 h for 15 parts). In short, it has been demonstrated that GA and SA are capable of solving bin-packing problems. However, the performances of GA and SA in terms of efficiency and effectiveness depend greatly on the solution space, the implementation strategies and the objective functions. In this study, SA algorithm was applied to the present packing problem according to the specific objective function and searching strategies for SGC processes. 3. Formulation of model layout problem In this work, the SGC model tray is represented as a container with an upper limit. The model layout problem in this research can be described as packing a batch of parts of different sizes into the container (bin). Packing tasks are characterized by the following three objectives: * fitting models into the specified container; * avoiding any overlap between models; * achieving high packing density, in other words, achieving the minimum overall height. In the present application, the CAD model of each part is represented in STL format. It consists of coordinate information of facet triangles and their corresponding outward pointing normal in a 3D space. Compared to other formats of CAD models, STL format is very straightforward. However, the search would be very time-consuming if the complete information of an STL model is encoded in the algorithm. This is because one simple operation such as ‘rotate’ or ‘move’ means recalculation of the new location of every triangle facet of a model, and it is very common for a mechanical part to have hundreds and thousands of triangle facets in an STL model. Moreover, these operations are used in thousands of ‘iterations’ during the searching process of SA. Thus the simplification is necessary. Most of the researchers simply envelop a part with a rectangular box because it is easy to implement and keeps the packing algorithm from becoming too complicated [4]. This method was also used in this research. The difference lies in the formulation of objective functions and specific search strategies. The 3D model layout can then be described in the following steps (Fig. 2): 1. Parse STL files of the parts to be manufactured and generate an envelope for each part model. 2. Pack envelopes in a bin according to a specific algorithm. The bin has the same size as that of the maximum manufacturing volume of the Cubital machine. 3. Calculate the updated STL file for each part. 4. Demonstrate the final result of the layout. Steps 1, 3, and 4 involve techniques in computer graphics and visualization, which are not specifically related to the packing problem and are relatively easier to implement with existing graphic tools. Our focus is on Step 2. The formulation of this problem is critical to establish a proper algorithm. The bin-packing problem can be represented as an optimization problem in Eq. (1): where n is the number of models, pi the packing state of a model, p the layout, P the set of all layouts, B the boundary of bin, pi∩pj the overlap between any two models, pi∩B the overlap betwe