| 题名 |
An Investigation of Paper Cutting Problem by Dynamic Programming and Heuristic Approaches |
| 并列篇名 |
以動態規劃及啓發演算法為基礎解求解紙張裁切問題 |
| DOI |
10.29977/JCIIE.200511.0003 |
| 作者 |
張百棧(Pei-Chann Chang)；謝日章(Jih-Chang Hsieh) |
| 关键词 |
紙張裁切問題 ； 裁切損失 ； 動態規劃 ； 啓發式方發 ； Paper cutting ； Trim loss ； Dynamic programming ； Heuristic approaches |
| 期刊名称 |
工業工程學刊 |
| 卷期/出版年月 |
22卷6期（2005 / 11 / 01） |
| 页次 |
463 - 472 |
| 内容语文 |
英文 |
| 中文摘要 |
本研究主要使用動態規劃法探討紙張裁切問題，此外，也提出兩個啓發法降低裁切的損失。此問題為NP-Hard問題並且屬於組合性問題，若採用最佳化解法之動態規劃演算法，將無法有效求解，因此將此之轉化為包裝問題，並發展兩個啓發式解法提供實務上應用。第一個方法為將原本的問題轉換為對偶形式，而裁切的特徵是依據C(下標 i)/A(下標 i)降冪的順序；第二個方法為藉由顧客的需求將紙張大小可能的組合產生可行解。為了比較動態規劃演算法與兩個啓發式方法之績效，本研究經由廣泛性的模擬測試求得。最後，實驗的結果指出本研究所提出的兩個啓發式方法能有效解決紙張裁切問題，可作為實務上應用之參考。 |
| 英文摘要 |
The major focus of this research is to formulate the paper cutting problem using dynamic programming. Two heuristic approaches are also developed for practical applications in minimizing the trim losses. Paper cutting problems are NP-hard and have the combinatorial explosion characteristic. It is not efficient to generate cutting patterns by dynamic programming. Thus, the problem is transformed into a Knapsack problem and two heuristic approaches are developed to provide alternatives for practical use in manufacturing company. The first heuristic is to transform the original problem into the dual form, then cutting patterns are generated according to the descending order of C(subscript i)/A(subscript i). The second heuristic is to organize the possible combinations of the size of the paper ordered by the customer to form a feasible cutting pattern. The dynamic programming model and heuristic approaches are evaluated through extensive simulation studies. The computational result indicates that the proposed heuristic approaches are quite satisfactory. The result may be of interest to other practical manufacturing companies. |
| 主题分类 |
工程學 >
工程學總論 |
| 参考文献 |
|
