基因演算法與平行處理於原料切割之研究與應用

Genetic and Parallel algorithm for Cutting Stock Problem

劉 彥 宏(Yen-Hung Liu)

指導教授 ： 李錫捷

元智大學/資訊學院/資訊管理學系/碩士(2008年)

摘要

在現今激烈競爭的時代裡，每個企業為了強化本身的競爭力，一直在尋找任何能提高效率及降低生產成本的生產方式，這對許多的製造產業來說特別重要，尤其像在原物料價格越高的產業。原料切割問題（CSP）就是一個攸關生產成本的，屬於NP-Hard的問題，是指在一給定的原料上，把預排列的已知數量與規格的物件擺放於原料上，並尋找最佳的排版位置，充分使用空間讓效用最高，以降低成本的支出。

另外，在資訊科技相當進步的時代裡，必須利用自動化的切割與排版系統才能符合時代的需求，也才能滿足更快速的需求。因此本研究發展一資訊化的切割系統，用基因演算法與平行處理來快速求出最近似最佳解，並且能處理業界常用的圖面交換格式(Drawing Exchange File，DXF)，以供企業在各種組合方案裡，快速判斷出一些有價值的選擇方案，供企業做進一步的分析。最終，本研究與數個文獻上的試例作測試，以驗證其研究的效用與可行性。

關鍵字

原料切割 ； 基因演算法 ； 平行處理

並列摘要

In this intensely competitive era, every business tries to reinforce its competitive strength. Continuously finding a way of produce to increase the efficiency and decrease the cost. This is very important to the manufacturing industry, particularly some industry, whose cost is higher in its raw material. CSP is a problem relevant to the cost, which belongs to NP-Hard. It means on one specific raw material, which will be put on an object, which needs to be arranged by its already known quantity and standards, and to find the best layout position. In order to fully utilize the space and make the highest effectiveness, in order to lower the cost.

Besides, in this highly technology era, it is necessary to use the automatic slice and layout system, to match and to satisfy the fast-speed needs. Therefore, this research develops one information science’s slice system, using GA and PA to look for the most approximation and the best. The system is also able to handle the Drawing Exchange File (Drawing Exchange File，DXF)which often be used in industry. This provides all kinds of combination to the business, which will make decisions on some valuable ones rapidly, in order to for further analysis. Finally, this research will do some tests on some examples from some documents, to prove the effectiveness and feasibility of the research.

並列關鍵字

Cutting Stock Problem ； Genetic Algorithm ； Parallel algorithm

參考文獻

[1]李玉婷，「具錯誤移轉機制之分散式平行運算平台設計與建置」，元智大學資訊管理研究所碩士論文，2001年。

[2]吳宗諭，「結合STL三角網格與DXF公差資訊之電腦輔助檢測技術系統發展」，中央大學機械工程研究所碩士論文，2005年。

[8]Babu, A.R. and Babu, N.R., “Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms” International Journal of Production Research, 37 (7), pp. 1625-1643, (1999).

[9]Beasley, J. E., “Algorithms for unconstrained two-dimensional guillotine cutting” ,Journal of the Operational Research Society,36, 297-306,(1985).

[10]Berkeley Open Infrastructure for Network Computing, http://boinc.berkeley.edu/