傳統義齒的製程繁複，牙技師養成須有十年以上的專業工作經驗，才可能製作出滿意的假牙。若能有效地建立一套專家系統，並導入自動化加工到牙技產業，便可大量縮短勞力與工時，降低生產成本，提升產量。為了追求義齒如自然牙般的剔透美感，陶瓷氧化鋯材料因其良好的透光性與自然牙相近，已經被大量使用；但由於其價格昂貴，在自動加工時若不能有效率地利用和管理，產生的廢料損失會明顯反應在成本上。
本研究以影像處理做為排版檢測方法，提出了應用在自動加工的最佳化排版演算法，將刀具行進空間納入為排版問題的限制條件，規劃節省材料的齒模排列加工位置。遺傳演算法為本研究求解最佳化的基礎，在嘗試純應用遺傳演算法進行排版後，針對其應用弱點改良，混合啟發式的左下優先(Bottom-left; BL)法控制工件，並提出加速BL位置搜尋的初始位置定義。最大工件數和餘材面積為比較排版能力的依據，顯示以節省材料改良後可排入更多工件量。改良後的方法僅適用矩形材料，但最佳化後的餘材皆可再進行排版；對於非矩形基材亦可以影像處理進行排版模擬。

Traditional process of artificial teeth fabrication is very complicate and time-consuming, so that a professional dental technician must be trained by years to make perfect functional artificial teeth. To reduce intensive labor some and increase the productivity, expert-based design system should be introduced to be integrated with numerical control machine. Nowadays, most of artificial teeth are made by ceramic material because it shows nature color with transparency which is similar to human teeth. However, due to its high cost, how to effectively enhance its usability is an important issue.
In this thesis, optimal nesting algorithms are introduced to integrate into the auto machining system. Image processing technique is used to detect nesting algorithms. Compare to the general nesting problem, residue between artificial teeth models should be taken into account, which allows the smallest cutting tool passing through. Based on genetic algorithm, we may obtain the optimal solution for the nesting problem. First, the approach optimizes the layout by pure genetic algorithm which may be primitive. Therefore, a heuristic algorithm known as bottom-left (BL) algorithm is introduced to improve outcome of the first approach. It preset the initial position of parts in order to efficiently reposition the parts. To investigate the layout performance, we count the maximum number of parts which can be layout in the base material and the maximum residual area that can be reused. Result shows the improved method gains better outcomes than the first approach. Moreover, these two approaches can be continuously applied to the residual layout for nesting. It is notified that the integrated BL and genetic algorithm can only be applied on a rectangle base. A non-rectangle raw material can be represented as a plane image, base on it we simulate the condition and get the layout.

[1] Hopper, E. and Turton, B., "A genetic algorithm for a 2D industrial packing problem," Computers & Industrial Engineering, Vol.37, No.1-2, pp.375-378, 1999.
[2] Liu, D. and Teng, H., "An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles," European Journal of Operational Research, Vol.112, No.2, pp.413-420, 1999.
[3] Soke, A. and Bingul, Z., "Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems," Engineering Applications of Artificial Intelligence, Vol.19, No.5, pp.557-567, 2006.
[4] Gonçalves, J. F., "A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem," European Journal of Operational Research, Vol.183, No.3, pp.1212-1229, 2007.
[5] Dowsland, K. A. and Dowsland, W. B., "Solution approaches to irregular nesting problems," European Journal of Operational Research, Vol.84, No.3, pp.506-521, 1995.
[6] Jakobs, S., "On genetic algorithms for the packing of polygons," European Journal of Operational Research, Vol.88, No.1, pp.165-181, 1996.
[7] Lamousin, H. and Waggenspack, W. N., "Nesting of two-dimensional irregular parts using a shape reasoning heuristic," Computer-Aided Design, Vol.29, No.3, pp.221-238, 1997.
[8] Heckmann, R. and Lengauer, T., "Computing closely matching upper and lower bounds on textile nesting problems," European Journal of Operational Research, Vol.108, No.3, pp.473-489, 1998.
[9] Anand, S., McCord, C., Sharma, R., and Balachander, T., "An integrated machine vision based system for solving the nonconvex cutting stock problem using genetic algorithms," Journal of Manufacturing Systems, Vol.18, No.6, pp.396-415, 1999.
[10] Burke, E. and Kendall, G., Applying Ant Algorithms and the No Fit Polygon to the Nesting Problem, in Advanced Topics in Artificial Intelligence, Foo, N., Editor. 1999, Springer Berlin / Heidelberg. p. 453-464.
[11] Cheng, S. K. and Rao, K. P., "Large-scale nesting of irregular patterns using compact neighborhood algorithm," Journal of Materials Processing Technology, Vol.103, No.1, pp.135-140, 2000.
[12] Nye, T. J., "Optimal nesting of irregular convex blanks in strips via an exact algorithm," International Journal of Machine Tools and Manufacture, Vol.41, No.7, pp.991-1002, 2001.
[13] Ramesh Babu, A. and Ramesh Babu, N., "A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms," Computer-Aided Design, Vol.33, No.12, pp.879-891, 2001.
[14] Dowsland, K. A., Vaid, S., and Dowsland, W. B., "An algorithm for polygon placement using a bottom-left strategy," European Journal of Operational Research, Vol.141, No.2, pp.371-381, 2002.
[15] Gomes, A. M. and Oliveira, J. F., "A 2-exchange heuristic for nesting problems," European Journal of Operational Research, Vol.141, No.2, pp.359-370, 2002.
[16] Tay, F. E. H., Chong, T. Y., and Lee, F. C., "Pattern nesting on irregular-shaped stock using Genetic Algorithms," Engineering Applications of Artificial Intelligence, Vol.15, No.6, pp.551-558, 2002.
[17] Yu, C. and Manoochehri, S., "Nesting Arbitrary Shapes Using Geometric Mating," Journal of Computing and Information Science in Engineering, Vol.2, No.3, pp.171-178, 2002.
[18] Carravilla, M. A., Ribeiro, C., and Oliveira, J. F., "Solving nesting problems with non-convex polygons by constraint logic programming," International Transactions in Operational Research, Vol.10, No.6, pp.651-663, 2003.
[19] Yu, C. and Manoochehri, S., "Optimal packing using the multiple mating method," Engineering with Computers, Vol.19, No.1, pp.56-65, 2003.
[20] Gomes, A. M. and Oliveira, J. F., "Solving Irregular Strip Packing problems by hybridising simulated annealing and linear programming," European Journal of Operational Research, Vol.171, No.3, pp.811-829, 2006.
[21] Egeblad, J., Nielsen, B. K., and Odgaard, A., "Fast neighborhood search for two- and three-dimensional nesting problems," European Journal of Operational Research, Vol.183, No.3, pp.1249-1266, 2007.
[22] Lee, W.-C., Ma, H., and Cheng, B.-W., "A heuristic for nesting problems of irregular shapes," Computer-Aided Design, Vol.40, No.5, pp.625-633, 2008.
[23] Costa, M. T., Gomes, A. M., and Oliveira, J. F., "Heuristic approaches to large-scale periodic packing of irregular shapes on a rectangular sheet," European Journal of Operational Research, Vol.192, No.1, pp.29-40, 2009.
[24] Imamichi, T., Yagiura, M., and Nagamochi, H., "An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem," Discrete Optimization, Vol.6, No.4, pp.345-361, 2009.
[25] Wong, W. K., Wang, X. X., Mok, P. Y., Leung, S. Y. S., and Kwong, C. K., "Solving the two-dimensional irregular objects allocation problems by using a two-stage packing approach," Expert Systems with Applications, Vol.36, No.2, Part 2, pp.3489-3496, 2009.
[26] Yu, M. T., Lin, T. Y., and Hung, C., "Active-set sequential quadratic programming method with compact neighbourhood algorithm for the multi-polygon mass production cutting-stock problem with rotatable polygons," International Journal of Production Economics, Vol.121, No.1, pp.148-161, 2009.
[27] Martins, T. C. and Tsuzuki, M. S. G., "Simulated annealing applied to the irregular rotational placement of shapes over containers with fixed dimensions," Expert Systems with Applications, Vol.37, No.3, pp.1955-1972, 2010.
[28] 沈泓翰，"以多邊形之階梯形在平行邊界片材上拼排的方法"，國立臺灣大學機械工程學研究所碩士論文，2003。
[29] 李文成，"直線逼近與快速定位法之不規則圖形自動排版系統"，中華大學科技管理研究所碩士論文，2004。
[30] 王誌謙，"AutoCAD系統於二維排版問題最佳化之研究"，國立臺灣海洋大學系統工程暨造船學系碩士論文，2005。
[31] Bennell, J. A. and Song, X., "A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums," Computers & Operations Research, Vol.35, No.1, pp.267-281, 2008.
[32] Bennell, J. A., Dowsland, K. A., and Dowsland, W. B., "The irregular cutting-stock problem -- a new procedure for deriving the no-fit polygon," Computers & Operations Research, Vol.28, No.3, pp.271-287, 2001.
[33] "啟發式搜索," 2011, wikipedia, <http://zh.wikipedia.org/wiki/%E5%90%AF%E5%8F%91%E5%BC%8F%E6%90%9C%E7%B4%A2>, April 5th 2011.
[34] 陳建聲，"結合啟發式與基因演算法解決不規則形船體內構件排版問題之研究"，國立成功大學造船及船舶機械工程學系碩士論文，2001。
[35] 李季昌，"排版之可旋轉式排列演算法則"，大葉大學機械工程研究所碩士論文，2008。
[36] Dorigo, M., "Optimization, Learning and Natural Algorithms," Doctorial Dissertation, Politecnico di Milano, Milan, Italy, 1992.
[37] Colorni, A., Dorigo, M., and Maniezzo, V., "An investigation of some properties of an Ant algorithm," in Proceedings of the Parallel Problem Solving from Nature Conference, Brussels, Belgium, pp.509-520, 1992.
[38] Colorni, A., Dorigo, M., and Maniezzo, V., "Distributed Optimization by Ant Colonies," in Proceedings of the First European Conference on Artificial Life, Paris, France, pp.134-142, 1992.
[39] Dorigo, M., Maniezzo, V., and Colorni, A., "The Ant System: Optimization by a colony of cooperating agents," IEEE Transactions on Systems, Man, and Cybernetics, Vol.26, No.1, pp.29-41, 1996.
[40] Dorigo, M. and Gambardella, L. M., "Ant colonies for the traveling salesman problem," BioSystems, Vol.43, No.2, pp.73-81, 1997.
[41] Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P., "Optimization by Simulated Annealing," Science, Vol.220, No.4598, pp.671-680, May 13, 1983, 1983.
[42] "模擬退火," 1997, 科學月刊, <http://210.60.226.25/science/content/1997/00030327/0017.htm>, April 26th 2011.
[43] 徐德興，"利用模擬退火演算法求解不規則物件排列及切割問題"，大葉大學工業工程研究所碩士論文，2000。
[44] Holland, J. H., "Outline for a Logical Theory of Adaptive Systems," J. ACM, Vol.9, No.3, pp.297-314, 1962.
[45] Bagley, J. D., "The Behavior of Adaptive Systems which Employ Genetic and Correlation Algorithms," Doctorial Dissertation, University of Michigan, Ann Arbor, Michigan, 1967.
[46] Holland, J. H., Adaptation in Natural and Artificial Systems, The University of Michigan Press, 1975.
[47] "Digital Materials and CAD/CAM Equipment," 2011, 3M Company, <http://solutions.3m.com/wps/portal/3M/en_US/3M-ESPE-NA/dental-professionals/products/category/digital-materials/>, July 5th 2011.
[48] Gottschalk, S., Lin, M. C., and Manocha, D., "OBBTree: A Hierarchical Structure for Rapid Interference Detection," Computer Graphics, Vol.30, No.Annual Conference Series, pp.171-180, 1996.
[49] 林昇甫、徐永吉, 遺傳演算法及其應用, 五南圖書出版股份有限公司, 2009.