咖啡粉枕式包裝機(jī)總體設(shè)計(jì)及計(jì)量裝置設(shè)計(jì)含開題、Proe三維及13張CAD圖
咖啡粉枕式包裝機(jī)總體設(shè)計(jì)及計(jì)量裝置設(shè)計(jì)含開題、Proe三維及13張CAD圖,咖啡,粉枕式包,裝機(jī),總體,設(shè)計(jì),計(jì)量,裝置,開題,Proe,三維,13,CAD
布局優(yōu)化的掩模固化快速成型工藝
X. Zhang， B. Zhou，Y. Zeng，P.Gu*
唐佳紅 譯
機(jī)械制造工程系、卡爾加里大學(xué)，大學(xué)路2500，卡爾加里，加拿大艾伯塔省T2n1n4
摘要
快速成型制造技術(shù)，可直接用于CAD模型的產(chǎn)品開發(fā)，制造工具和制造模具以及功能部件。掩模固化(SGC)技術(shù)中的快速成型技術(shù)， 適合建立多種不同零部件的快速成型樣機(jī)幾何尺寸的批量生產(chǎn)，其成本降至最低。 然而，平面CAD模型環(huán)境的布局是費(fèi)時(shí)的。 由于樹脂的成本高， 一批SGC的業(yè)務(wù)在任何工業(yè)環(huán)境中的布局模式是成功的關(guān)鍵。 本文利用模擬退火布局優(yōu)化技術(shù)。開發(fā)一個(gè)軟件系統(tǒng)是為了協(xié)助前部分進(jìn)行各種型號(hào)的CAD幾何形狀的布置。 STL系統(tǒng)接受來自任何實(shí)體造型環(huán)境的信息。下面提供幾個(gè)例子來說明技術(shù)的有效性。
1. 引言
全球的主導(dǎo)產(chǎn)品競爭日益需要廠商更加靈活地適應(yīng)瞬息萬變的市場需求。 大幅削減產(chǎn)品開發(fā)時(shí)間將改善企業(yè)對市場的需求，因此贏得競爭優(yōu)勢。
快速成型制造技術(shù)也不斷提高了廠商建立三維模型和原型等幾方面快速反應(yīng)能力; 而具有成本效益的生產(chǎn)模式和復(fù)雜模具曲面[1]的快速成型技術(shù)可直接從CAD模型生成原型。 各種快速成型技術(shù)的出現(xiàn)，包括固化、選擇性激光燒結(jié)(SLS)、熔融沉積制造、疊層實(shí)體制造、三維印刷和掩模固化(SGC)。它們有一個(gè)共同特點(diǎn):成型制作是加入材料而不是像傳統(tǒng)的去除材料或變形工序[2]。 這些技術(shù)可以填補(bǔ)空間不確定具體部分的概念設(shè)計(jì)。該技術(shù)也可大大提高工作效率和模具制作工藝格局。
SGC的過程能在單一格局內(nèi)生產(chǎn)多種不同形狀和尺寸的零件，因此適合批量生產(chǎn)。 在SGC的制造過程中(圖1)，使負(fù)截面的一部分產(chǎn)生靜電收取玻璃板。這就像平時(shí)使用的激光打印機(jī)。 在此期間，一層液態(tài)固化樹脂是一種分布式的到位工作。 然后放在工作空間的燈和表面之間用玻璃板擋起來，不是用激光束或者是紫外線燈注滿空間和照亮整個(gè)層。剩余的液態(tài)樹脂是用吸塵器抹去。 向后移動(dòng)的樣盤上曝露在紫外線燈下第二次凝固的液態(tài)樹脂沒有被吸塵器完全清理干凈。 在這層充滿熱蠟液的空間，蠟被一個(gè)冷態(tài)金屬碟子冷卻到固體之后，這個(gè)樹脂蠟層被刀具快速的粉碎成指定的大小。樣盤從磨床回到曝光廳后，樹脂的新層被應(yīng)用。SGC程序能同時(shí)由一個(gè)限制簡單的CAD 模型形成多個(gè)復(fù)雜部件的玻璃裝料碟子。 因此，可以用來生產(chǎn)機(jī)器前部分分批多型號(hào)。
然而，在SGC的建立過程中， 樹脂不能被重復(fù)使用，因?yàn)樗呀?jīng)部分被恢復(fù)。 如果我們要建立一個(gè)單一的部分，并且沒有其它任何地方共享區(qū)段，這部分可以很昂貴，除非占有大多數(shù)的托盤模式。 此外， 大多數(shù)其它快速成型機(jī)必須依次編織每個(gè)過渡部分。 雖然這些時(shí)間可由機(jī)器同時(shí)生產(chǎn)多種零部件而減少，生產(chǎn)時(shí)間的長短取決零件的數(shù)量和零部件的幾何形狀。 在SGC的過程中，每一層曝露在具有相同時(shí)間紫外線燈下的跨度為預(yù)設(shè)操作。 因此消費(fèi)和制造樹脂的每一層時(shí)間都是固定的， 一批獨(dú)立的幾何形狀和數(shù)量的零部件。 因此， 當(dāng)一批零部件的生產(chǎn)成本單純依靠被生產(chǎn)層的數(shù)字時(shí)，為了最大限度地減少成本和生產(chǎn)率， 各地應(yīng)在每一批'封裝'時(shí)給予盡可能低的示范區(qū)，使托盤制作的一批零部件成本降到最小。
當(dāng)兩個(gè)或兩個(gè)以上的部分是在在三維圖形環(huán)境中同一時(shí)間制造時(shí)，具體操作模擬包裝件應(yīng)放置在它們或它們的CAD模型上。在計(jì)算機(jī)屏幕上的一個(gè)封袋內(nèi)，可保證部件不相互干涉， 而且它們完全在限制的體積之內(nèi)。 每批零件可用于不同的程序和不同客戶。 因此零件形狀和大小可以相差很大， 使得很難找到用手動(dòng)解決的最佳經(jīng)營模式的布局。 因此，需要找到一個(gè)電腦系統(tǒng)的優(yōu)化，配置一批生產(chǎn)成本最低的布局。
圖1 描述SGC的制造過程
2. 相關(guān)研究工作
布局問題的模型可歸納為典型裝箱問題。 應(yīng)用裝箱問題可用在集成電路設(shè)計(jì)、切割和股票等其它領(lǐng)域。典型的二維和三維裝箱問題已被證明是疑難問題[3]。生產(chǎn)效率最優(yōu)解的密切近似算法的開發(fā)對裝箱問題具有重要現(xiàn)實(shí)意義是。 這些方法包括:線性規(guī)劃、啟發(fā)式技術(shù)，模擬退火(SA)和遺傳分析(GA)。
線性規(guī)劃方法已成功地廣泛應(yīng)用于學(xué)習(xí)、普通切割的問題中。 然而，由于它們的結(jié)構(gòu)或大小，這些方法對許多真正的問題是不適當(dāng)?shù)摹?在這種情況下，應(yīng)用啟發(fā)式手段，如動(dòng)態(tài)規(guī)劃搜索方法。 動(dòng)態(tài)規(guī)劃法是一種把單個(gè)問題轉(zhuǎn)換成一系列單階段問題的算法其難度是如何迅速確定最優(yōu)決策。樹-搜索的方法是將所有可能的解決方法羅列成樹狀結(jié)構(gòu)，在同一條路徑上開始和結(jié)束，當(dāng)其被認(rèn)為是已經(jīng)找到的最佳答案或者是已經(jīng)知道會(huì)造成令人不滿意的解決方案。上述大部分辦法要么不給最佳或接近最佳的解決方案要么不適用多種應(yīng)用而且比較復(fù)雜形式的問題[4]。
為克服線性規(guī)劃、啟發(fā)式方法的局限， 研究成果已使用SA和GA解決封裝問題。 rao及Iyengar[5]適用于多樣化的裝箱問題。 大量仿真實(shí)驗(yàn)表明典型的啟發(fā)式方法已經(jīng)顯著的改進(jìn)。 cagan[6]摸索SA用二維和三維解決問題。適應(yīng)退火時(shí)間表，多分辨率建模與動(dòng)態(tài)步驟提出改進(jìn)策略選擇算法性能。 Han和Na [7]嵌套方法提出了兩個(gè)階段:初級布局階段，改善布局階段。 自組織算法輔助設(shè)計(jì)制造了一種'優(yōu)的'初步布局; 然后用SA布局作初步改善。 Corcoran [8]探索GA問題在三維封裝中的應(yīng)用以便GA更好的解決三維封裝問題。
值得一提的是，ikonen等[9]用GA來為機(jī)器解決三維模型的規(guī)劃問題。 上述的研究大多簡化了零部件的形狀。 ikonen幾何方法的零件不需要在封裝前簡化。 不過用這個(gè)方法搜索的封裝過程可能非常費(fèi)時(shí) (例如15個(gè)部件需要8.5小時(shí))。
總之，已證明它有解決GA和SA裝箱問題能力。不過，GA和SA在效率和效益上很大程度取決于空間解來實(shí)施策略和目標(biāo)功能。 在這項(xiàng)研究中， SA算法目前應(yīng)用于封裝的具體問題，根據(jù)客觀戰(zhàn)略SGC的搜索功能和過程。
3. 制定示范布局問題
在這項(xiàng)工作中，SGC的模盤代表容器的上限。 這個(gè)問題的布局模式研究一批堪稱封裝大小不同零件的容器(集裝箱)。 封裝任務(wù)具有以下三個(gè)目標(biāo):
*裝修進(jìn)入指定型號(hào)集裝箱;
*避免模型重疊;
*實(shí)現(xiàn)高密度封裝，換句話說，實(shí)現(xiàn)最低整體水平。
在目前的應(yīng)用中， 每一部分CAD模型用STL格式來表示。它由三角面坐標(biāo)數(shù)據(jù)及其相應(yīng)三維空間表面組成。 相對于其它格式的CAD模型，STL格式非常簡單。 然而，如果STL模型是一個(gè)完整的信息編碼算法，搜索會(huì)很費(fèi)時(shí)，這是因?yàn)楹芷匠５臋C(jī)械部分有成千上萬的三角面的STL模型，一個(gè)簡單操作如'旋轉(zhuǎn)'或'移動(dòng)'就是重新定位每一個(gè)三角面的新模式。 此外，這些動(dòng)作都是用數(shù)千'迭代'在SA搜索過程，因此簡化是必要的。 大多數(shù)的研究者只是包抄一部分，因?yàn)樗且粋€(gè)長方形盒子容易執(zhí)行，使包裝算法變得過于復(fù)雜 [4]。 這種方法還用于這項(xiàng)研究。 不同之處在于制定具體的搜索功能和戰(zhàn)略目標(biāo)。 三維模型圖可以描述以下步驟(圖二):
1.解析STL文件的零件制造、每一個(gè)封閉部分產(chǎn)生示范。
2. 據(jù)具體算法封裝。箱體批量的大小相同，機(jī)器的最大體積相同。
3. 計(jì)算每一部分更新STL文件。
4. 最后結(jié)果顯示布局。
步驟1，3，4涉及計(jì)算機(jī)圖形學(xué)、可視化技術(shù)、 所不明確的問題，涉及到包裝、較易執(zhí)行現(xiàn)有圖形工具。 我們的重點(diǎ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高度目標(biāo)函數(shù)映射成為集P實(shí)數(shù)。
目前這個(gè)問題，是一個(gè)單批零件的布局滿足限制方程(1)的界定。 目標(biāo)函數(shù)定義為整體的布局高度。
典型的封裝狀態(tài)是由封袋的位置和方向決定的。 每一個(gè)部分的坐標(biāo)是由封袋的幾何中心定義的。集裝箱的左下角定義為整體的坐標(biāo)原點(diǎn)。 封袋的幾何中心確定封袋在箱中的位置。 典型的方位有六個(gè)如圖(3)所示。
一個(gè)狀態(tài)對另一個(gè)狀態(tài)的轉(zhuǎn)變可通過一個(gè)或兩個(gè)旋轉(zhuǎn)操作實(shí)現(xiàn)。旋轉(zhuǎn)操作是局部調(diào)整旋轉(zhuǎn)軸附近的封袋。 例如，圖(3)把封袋的一種狀態(tài)換成另一種狀態(tài)，它可以繞X軸旋轉(zhuǎn)也可以繞Y軸旋轉(zhuǎn)。 每個(gè)封裝袋表面總是平行或垂直于正交軸。所以每個(gè)封袋的形式pi表示為:
其中xi、 yi 、zi 相對應(yīng)的表示第i個(gè)封袋的頂點(diǎn)。 θi 表示它的方向，n是用來記數(shù)的;Xi 、Yi、 Zi 表示第i個(gè)封袋沿x、 y、 z 方向的長度。
目標(biāo)函數(shù)f 定義為在有效方向上搜索到的合適的點(diǎn)。在這項(xiàng)研究中，目的是盡量減少總體布局的高度可以由下列公式:
圖3 自由度導(dǎo)向示范
在搜查過程中， 通過已知的模型結(jié)果搜索更加準(zhǔn)確的解決方法。 在最后目標(biāo)函數(shù)的設(shè)計(jì)中應(yīng)該避免重疊。 因此目標(biāo)函數(shù)有兩個(gè)條件f2:
當(dāng)兩個(gè)平行長方形箱子重疊，重疊部分也是一個(gè)長方形。 在方程(4)中Oij(x)、 Oij(y)和Oij(z) 表示第i個(gè)箱子和第j個(gè)箱子重疊部分沿x 、y 、z 方向的長度。Oij 表示重疊部分三個(gè)方向長度的總和。
重疊量化方程(4)的線性疊加最常用于多目標(biāo)函數(shù)優(yōu)化[7，9]:
不過，這個(gè)功能很少能夠成功的優(yōu)化這個(gè)封裝的問題。 在搜索過程中， 解答f值方法是搜索目標(biāo)函數(shù)值。 不同的重量物品的比較結(jié)果，可以不同。 因此這兩個(gè)重量相對價(jià)值是至關(guān)重要的。f2變化范圍是由各部分的數(shù)量和大小決定的，一對'重量'不同包裝情況找不到一個(gè)比較好的方法。 即使有重疊和客觀高度的值也很難找到數(shù)學(xué)方法決定自己價(jià)值。如果w2遠(yuǎn)大于W1;目標(biāo)函數(shù)將更為敏感變更重疊量f2: 該模型將放置在搜索過程初期消除重疊。最后，將模型在集裝箱里堆高，如果高度比意義更是值得考慮，較為敏感的全局高度和重疊量的目標(biāo)函數(shù)將變化，因?yàn)槟繕?biāo)函數(shù)值將因?yàn)楦叨认陆刀鴾p少。
避免難以確定的重量值、 非線性目標(biāo)函數(shù)和定義使用于這項(xiàng)研究。 下面的目標(biāo)函數(shù):
重疊高度上限是由集裝箱高度決定的。當(dāng)f2=1時(shí)因?yàn)閒2<1無法成立函數(shù)值使f等于0， 否則會(huì)引起沖突。換句話說，當(dāng)目標(biāo)函數(shù)值不再減少，就不會(huì)得到改善。
在方程(4)重疊兩個(gè)封袋重疊長度的計(jì)算總結(jié)三個(gè)方面。用數(shù)學(xué)給這兩個(gè)封袋重疊部分定義合適的目標(biāo)函數(shù)方程(7):
在搜查過程中利用非線性目標(biāo)函數(shù)搜索重疊的客觀職能是好的， 假設(shè)移動(dòng)不可行組態(tài)(布局)可以導(dǎo)致上級可行配置(布局)[4]。 以此為目標(biāo)函數(shù)， 算法引導(dǎo)搜索的走向會(huì)降低，布局重疊高度后已經(jīng)很小。雖然還存在小小的重疊的型號(hào)，最后的總體布局的高度普遍較低。
SA辦法來解決上述問題的最優(yōu)解比較試驗(yàn)都是封裝重疊量化使用重疊方程(4)確定。SA辦法在使用第一種方法時(shí)表現(xiàn)較差或沒有更好的表現(xiàn)。測試結(jié)果將在后文表明。
這里指的封裝算法不能保證找到一個(gè)可接受的解決方案。 消除重疊解決小SA所得的補(bǔ)償算法是一個(gè)簡單的程序。 SA搜索過程完成后，如果存在重疊， 補(bǔ)償程序可以找出重疊模型和解決措施，顯示他們最低重疊量。 由于可能產(chǎn)生新的重復(fù)動(dòng)作，再次檢查所有型號(hào)； 是否出現(xiàn)新的重疊，直到程序沒有繼續(xù)存在的重疊模式。重疊在大多數(shù)情況下，可以輕松地解決后執(zhí)行這項(xiàng)補(bǔ)償計(jì)劃。在測試的情況下，整體水平SA提高不明顯。
4. 模擬退火方法
4.1 觀念SA
SA是基于物理概念金屬熱處理為了找到最低能量金屬狀態(tài)。數(shù)學(xué)方法是用退火冷卻時(shí)間表，這是一個(gè)使功能下降的方法。SA是一個(gè)統(tǒng)計(jì)力學(xué)隨機(jī)計(jì)算技術(shù)尋找附近所有最低成本所得的解決大型優(yōu)化問題的方法。 在許多情況下， 尋找一個(gè)客觀的取小價(jià)值與功能的自由度受到許多限制，是一種矛盾的疑難問題。由于有許多客觀的功能將趨于局部極小。優(yōu)化程序解決這類問題，應(yīng)尋找樣本空間，如此才能使尋找最優(yōu)或接近最優(yōu)解在合理時(shí)間有一個(gè)高的概率。
SA是由Kirkpatrick et al [10]決定的。 這一構(gòu)想源自Metropolis[11]。 最初的起始溫度T; 給予最大值，并假設(shè)系統(tǒng)處于初始狀態(tài)開始計(jì)算目標(biāo)函數(shù)值f。國家規(guī)定用p表示; 然后測試六個(gè)點(diǎn)的轉(zhuǎn)變職能。 如果此舉導(dǎo)致目標(biāo)函數(shù)有所改善， 用新的函數(shù)代替原函數(shù)。其目標(biāo)函數(shù)值也用這個(gè)新解。這可以大概計(jì)算目標(biāo)函數(shù)值。 共認(rèn)的概率決定如下:
溫度值開始隨時(shí)間下降。 每個(gè)溫度系統(tǒng)都有幾次不穩(wěn)定。這反復(fù)進(jìn)行溫度迭代計(jì)算稱為Markov鏈。迭代連環(huán)次數(shù)稱為鏈長。最初，動(dòng)作通過空間狀態(tài)幾乎隨機(jī)的，造成了廣泛的探索空間的客觀功能。由于概率接受劣質(zhì)動(dòng)作下跌，它們往往很難使算法收斂到最優(yōu)。
5. 封裝策略
5．1. 運(yùn)動(dòng)裝置
SA從解(s)開始搜索的一個(gè)或多個(gè)進(jìn)程，然后選擇認(rèn)定其預(yù)先的解。 此過程用“φ”表示; 這是一種新穎的操作辦法p’可以從舊的中得到， 移動(dòng)裝置是由各個(gè)動(dòng)作依據(jù)模型布局組成。 當(dāng)新布局由舊產(chǎn)生，一個(gè)動(dòng)作是有移動(dòng)裝置中幾個(gè)可能的動(dòng)作中選出的。 在運(yùn)動(dòng)裝置中定義六個(gè)動(dòng)作的問題如下:
*轉(zhuǎn)動(dòng)。 改變封袋方向一個(gè)模式不改變中心位置封袋。 共有6個(gè)方向可以選擇。 然而，可能性最小的方向給予更多的高度封套。
*漫步。 隨意改變的中心位置在封袋正負(fù)x 正負(fù)y 正負(fù)z方向，貨廂的運(yùn)動(dòng)方向和移動(dòng)距離取決于當(dāng)前的溫度。 在更高溫度較長距離的運(yùn)動(dòng)，企圖將選擇一個(gè)更大的變化，實(shí)現(xiàn)功能的成本，并避免局部極小。
*交換。 改變兩個(gè)封袋地點(diǎn); 兩個(gè)封袋是隨機(jī)抽選調(diào)換。
*回到起點(diǎn)(0，0，0)。 隨機(jī)挑選封袋提出一個(gè)方向，使沿線的X; Y和Z座標(biāo)，封袋溫度減少的那一刻將減少移動(dòng)距離。
*'消除'重疊。 計(jì)算向量之間重疊每個(gè)封袋沿線移動(dòng)相應(yīng)載體。 這一行動(dòng)旨在減少整體重疊、 其實(shí)并不能消除重疊，因?yàn)橐院笈懦磺锌赡墚a(chǎn)生重疊的新舉措。
*靠墻移動(dòng)。 在提出抽樣封袋x-y平面(不改變其Z坐標(biāo)位置)，直到它觸及墻往就近封袋或其它容器壁、 然后向下直到它觸及封袋或其它容器底部。
實(shí)際上有兩個(gè)在移動(dòng)裝置中的基本操作旋轉(zhuǎn)、漫步中， 其它被視為一個(gè)特殊的操作或動(dòng)作順序。 后者的主要目的是提高四個(gè)業(yè)務(wù)的算法效率。
5．2． 重疊計(jì)算檢測
重疊計(jì)算評價(jià)兩個(gè)或兩個(gè)以上封袋重疊的程度。封袋預(yù)計(jì)二維平面坐標(biāo)，這使計(jì)算方便。 一旦有重疊的兩個(gè)封袋，就有重疊每個(gè)二維平面(X-Z、X-Y、Y-Z平面)。 如果任何兩個(gè)平面之間沒有重疊，這兩個(gè)封袋之間就沒有重疊 如圖(4)。
圖4 模型布局優(yōu)化算法SA
6.結(jié)論
快速成型制造技術(shù)可大幅度降低產(chǎn)品開發(fā)時(shí)間，迅速適應(yīng)市場需求。作為一個(gè)普通的快速成型技術(shù)工藝，能生產(chǎn)多種零部件SGC的同步進(jìn)程。不過，需要做研究，以減少生產(chǎn)成本，提高機(jī)械效率。 SGC的SA過程用于解決在模型中布局優(yōu)化、發(fā)現(xiàn)問題，提高了生產(chǎn)效率和降低成本。新的目標(biāo)函數(shù)功能將于傳統(tǒng)線性函數(shù)相比較。有效的比較辦法是SA。 軟件開發(fā)工具包可以從機(jī)器上減少繁瑣且未必有效的工作部分。它也可以由工程師接收STL格式。封袋自動(dòng)生成和更新的STL文件的封袋型號(hào)以及相應(yīng)布置的辦法。 最后的布置可轉(zhuǎn)為VRML的格式和可視VRML。 最新日志檔案可直接裝入機(jī)床制造一批多種零部件。
致謝
這項(xiàng)研究得到了加拿大自然科學(xué)及工程研究理事會(huì) (NSERC)戰(zhàn)略性str192769補(bǔ)助。
參考資料
[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
收藏