在工業用紙製造工業中，原料裁切是製造流程的一個重要步驟，原料裁切會直接影響企業的收益。為了解決此問題，現今有許多的研究探討原料裁切問題，但這些研究主要關注於投入原料的裁切數和生產剩料(trim loss)的最佳化。但只關注這些因素，同時也會產生其他問題，如只將生產剩料最佳化，則易導致存貨過多，也因為難以面面俱到的情形下，上述之最佳化難以被企業所採用。為了讓整個結果能更符合實際的需求，本研究使用Wang and Liu [20] 於2014年所提出之最佳收益模型來處理上述的問題，此模型是求取生產時的最大收益，能有效關注到生產線的整個面向，因此可以解決上述的問題。
但在使用最佳收益模型時，會遇到原料裁切問題中的可行的樣式過多的問題，此問題在現今產品多樣化、客製化的趨勢下，越趨複雜，若直接使用所有可行的樣式來進行求解，極度耗費時間。本研究利用分群與分類的方法來降低選取的可行的樣式數量，在維持收益的情形下，降低求解所需的時間，最後模擬五個產線案例來對此方法進行評估，可得到使用此方法來降低選取的可行的樣式數量，可有效降低求取的時間，並保持收益的一定品質。

In industrial-use paper industry, cutting stock is a crucial procedure of production scheduling, and will directly affect business income. To solve this problem, there has been a lot of research for cutting stock problem nowadays; however, most of the research put attention and efforts into optimization of cutting quantity and trim-loss merely. If only caring about these factors, it might lead to other problems. Such as optimization of trim-loss, it tends to cause excess inventory. Seeing these considerations, they’re the reasons why enterprises may not adopt the optimizations mentioned above. Therefore, to make the results meet the practical demands, this study uses scheduling revenue maximizing problem by Wang and Liu [20], which is presented in 2014, to deal with the problems we mentioned above. By using this model, it can provide an efficient production plan at maximum revenue, and efficiently cares about all the production plans.
On the other hand, when using scheduling revenue maximizing problem (SRMP), will occur excess existence of a product in a given pattern. The problem becomes more complicated in various products nowadays, and it will take times if we use all exist patterns to optimize the SRMP. This study uses clustering and classification to reduce the number of exist patterns chosen. Evaluating this method by using 5 simulated cases at last, we can find out that the result can efficiently reduce the time we waste and retain acceptable revenue.

[1] Ali, M., C.W. Ahn and M. Pant, “Trim loss optimization by an improved differential evolution,” Mathematical Problems in Engineering, 2013, Article ID 706350 (2013).
[2] Chauhan, S.S., A. Martel and S. D’Amour, “Roll assortment optimization in a paper mill: An integer programming approach,” Computers and Operations Rsearch, 35, 614-627 (2008).
[3] Cherri, A.C., M.N. Arenales and H.H. Yanasse, “The one dimensional cutting stock problem with usable leftover – a heuristic approach,” European Journal of Operational Research, 196, 897–908 (2009).
[4] Cabena, P., P. Hadjinian, R. Stadler, J. Verhees and A. Zanasi, “Discovering Data Mining: from Concept to Implementation,” Prentice Hall, USA (1997).
[5] Dyckhoff, H., “A typology of cutting and packing problems,” European Journal of Operational Research, 44, 145−159 (1990).
[6] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Pub. Com. Inc., USA (1989).
[7] Gilmore, P.C. and R.E. Gomory, “A linear programming approach to the cutting stock problem,” Operations Research, 9, 849–859 (1961).
[8] Gilmore, P.C. and R.E. Gomory, “A linear programming approach to the cutting stock problem, Part II,” Operations Research, 11, 863–888 (1963).
[9] Gradisar, M., G. Resinovič and M. Kljajić, “Evaluation of algorithms for one-dimensional cutting,” Computers and Operations Research, 29, 1207–1220 (2000).
[10] Holland, J. H., Adaptation in Natural and Artificial Systems, The University of Michigan Press, USA (1975).
[11] Haessler, R.W., “A note on computational modifications to the Gilmore-Gomory cutting stock algorithm,” Operations Research, 28, 1001-1005 (1980).
[12] Kohonen, T., “The Self-Organizing Map,” Proceedings of the IEEE, 78, 1464-1480 (1990).
[13] Keskinocak, P., F. Wu, R. Goodwin, S. Murthy, R. Akkiraju, S. Kumaran and A. Derebail, “Scheduling solutions for the paper industry,” Operations Research, 50, 249–259 (2002).
[14] Liu, F.T., A New Decision Model for Controlling Trim Loss and Inventory in the Paper Industry, PhD thesis, Nation Taiwan University Science of Technology, Taiwan (2014).
[15] MacQueenet, J., In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, University of California, USA (1967).
[16] Menon, S. and L. Schrage, “Order allocation for stock cutting in the paper industry,” Operations Research, 50, 324-332 (2002).
[17] Poltroniere, S.C., K.C. Poldi, F.M.B. Toledo and M.N. Arenales, “A coupling cutting stock-lot sizing problem in the paper industry,” Annuals of Operations Research, 157, 91-104 (2008).
[18] Quinlan, J.R., “C4.5 Programs for Machine Learning,” Machine Learning, 16, 235-240 (1994).
[19] Scheithauer, G., J. Terno, A. Muller and G. Belov, “Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm,” Journal of the Operational Research Society, 52, 1390-1401 (2001).
[20] Wang, F. K. and F. T. Liu, “Maximizing Revenue for Cutting Problems in the Industrial-Use Paper Production,” Working Paper, (2014).
[21] Tharmmaphornphilas, W., P. Sukonthip and P. Siripongwutikorn, “A MILP model to select cutting machines and cutting patterns to minimize paper loss,” Proceedings of the International MultiConference of Engineers and Computer Scientists, 2, 1155-1160 (2013).
[22] Vanderbeck, F., “Computational study of a column generation algorithm for bin packing and cutting stock problems,” Mathematical Programming, 86, 565-594 (1999).