摘要

　　原料裁切問題（Cutting Stock Problems, CSP）探討由已知尺寸的原料中，以最佳方式裁切出符合需求尺寸的物件。經過裁切的原料經常會產生多餘不用的剩料，若剩料尺寸無法再被使用，則以廢料的方式捨棄或僅殘餘相對於原料甚低的價值。最佳化原料裁切模式及求解技術可應用於型鋼構件或鋼筋裁切問題，而其規劃目標經常為原料使用量最小化或廢料最小化。本研究以鋼筋裁切問題為例，探討一維鋼材原料裁切模式之構建以及演算流程。目標函數考慮使用原料成本最小化，以及留存長剩料以供後續利用。
　　本研究依一維原料裁切問題特性建構數學模式。在模式求解方面，由於一維原料裁切問題如同大多數組合最佳化問題，當問題規模增長同時變數量亦急遽增加，因此難以將直接對模式求解的方式應用在實務上的問題規模。本研究採用鄰近搜尋法（neighborhood search methods）與整數規畫法組合之三階段啟發式演算流程，有效率地找到一維原料裁切問題的良好解。
　　鄰近搜尋法的演算方式為逐步小幅變動一個起始可行解，以改善目標函數值而達到理想可行解之目的。鄰近搜尋法由於其小幅變動現有解的方式，使其有極高的演算效率。由於組合最佳化問題之目標函數有許多局部最佳解，使得搜尋鄰近解的演算過程很容易陷於局部最佳解，因此在搜尋過程中必須加入接受劣化解的機制以免陷於局部最佳解。本研究使用門檻接受法（Threshold Accepting, TA）的技巧並穿插整數規畫法，以將現行解帶出局部最佳解。本研究撰寫演算程式並以不同的測試例進行演算流程之測試。測試結果得知經由兩種演算策略的交互使用，並搭配三階段啟發式演算流程，可以同時獲得良好的演算效率及求解品質。

Abstract

　This thesis examines a three-phase heuristic approach for solving one-dimensional cutting stock problems (1D-CSP).The proposed approach combines two themes of solving method：a neighborhood search algorithm with threshold accepting techniques, and an IP-based method.
　Cutting stock problems deal with the optimal cutting of raw materials to satisfy the given demand of different order lengths. Techniques of modeling and solving cutting stock problems have many applications including structural steel cutting. Standard CSP usually consider the objective of minimizing the using of raw materials or cutting loss.
　This thesis presents a model for the one-dimensional cutting stock problem as used for cutting structural steel bars and a sequence of solving procedures is proposed. The objective function minimizes the cost of raw steel materials as well as maximizes the lengths of remainder bars. The solving process consists of Threshold Accepting （TA） heuristic and Integer Programming （IP） proceeding in iterative computing. Case study indicates that the proposed solving process can effectively search the feasible region and avoid being trapped in local optimal by properly combining TA and IP algorithm. Computational testing on different instances shows that the three-phase solving process yields good results on both efficiency and quality.

參考文獻
1. 楊秉蒼，「營建鋼筋裁切規劃系統實作與應用」，詹氏書局，2002年。
2. 宗大建設，公司訪談，2004年。
3. Yang, G. H.，D營造公司，個人討論，2004年。
4. 林蔚菁，「系統模擬於鋼筋供應鏈管理之研究」，私立朝陽科技大學營建工程研究所碩士論文，2003年。
5. 楊世清，「營建管理技術手冊」，地景出版社，1998年。
6. Faggioli, E., and Bentivoglio, C.A., “Heuristic and Exact Methods for the Cutting Sequencing Problem,” European Journal of Operational Research, Vol. 110, No. 3, pp. 564-575 (1998) .
7. Armbruster, M., “A Solution Procedure for a Pattern Sequencing Problem as Part of a One-Dimensional Cutting Stock Problem in the Steel Industry,” European Journal of Operational Research, Vol. 141, No. 2, pp. 328-340 (2002) .
8. Dyckhoff, H., “A Typology of Cutting and Packing Problems,” European Journal of Operational Research , Vol. 44, pp. 145–159 (1990) .
9. Gilmore, P.C., and Gomory, R.E., “A Linear Programming Approach to the Cutting Stock Problem,” Operations Research, Vol. 9, pp. 849–859 (1961) .
10. Gilmore, P.C., and Gomory, R.E., “A Linear Programming Approach to the Cutting Stock Problem – Part II,” Operations Research, Vol. 11, pp. 863–888 (1963) .
11. Nash, Stephen G., Sofer, Ariela, Linear and Nonlinear Programming, pp. 200–204, McGraw-Hill (1996) .
12. Yuen, B.J., and Richardson, K.V., “Establishing the Optimality of Sequencing Heuristics for Cutting Stock Problems,” European Journal of Operational Research, Vol. 84, No. 3, pp. 590-598 (1995) .
13. Johnston, R.E., and Khan, L.R., “Bounds for Nested Knapsack Problems,” European Journal of Operational Research, Vol. 81, No. 1, pp. 154-165 (1995) .
14. Belov, G., and Scheithauer, G., “A Cutting Plane Algorithm for the One-Dimensional Cutting Stock Problem with Multiple Stock Lengths,” European Journal of Operational Research, Vol. 141, No. 2, pp. 274-294 (2002) .
15. Valério de Carvalho, J.M., “LP Models for Bin Packing and Cutting Stock Problems,” European Journal of Operational Research, Vol. 141, No. 2, pp. 253-273 (2002) .
16. Scheithauer, G., and Terno, J., “The Modified Integer Round-Up Property of the One-Dimensional Cutting Stock Problem,” European Journal of Operational Research, Vol. 84, No. 3, pp. 562-571 (1995) .
17. Rietz, G., Scheithauer, G., and Terno, J., “Families of non-IRUP instances of the one-dimensional cutting stock problem,” Discrete Applied Mathematics, Vol. 121, pp. 229-245 (2002) .
18. Nitsche, C., Scheithauer, G., and Terno, J., “Tighter relaxations for the cutting stock problem,” European Journal of Operational Research, Vol. 112, No. 3, pp. 654-663 (1999) .
19. Vanderbeck, F., and Wolsey, L.A., “An Exact Algorithm for IP Column Generation,” Operations Research Letters, Vol. 19, No. 4, pp. 151-159 (1996) .
20. Schilling, G., and Georgiadis, M.C., “An Algorithm for the Determination of Optimal Cutting Patterns,” Computers and Operations Research, Vol. 29, No. 8, pp. 1041-1058 (2002) .
21. Valério de Carvalho, J. M., “Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound,” International Transactions in Operational Research, Vol. 5, No. 1, pp. 35-44 (1998) .
22. Riehme, J., Scheithauer, G., and Terno, J., “The Solution of Two-Stage Guillotine Cutting Stock Problems Having Extremely Varying Order Demands,” European Journal of Operational Research, Vol. 91, No. 3, pp. 543-552 (1996) .
23. Valério de Carvalho, J.M., and Guimarães Rodrigues, A.J., “An LP-based Approach to a Two-Stage Cutting Stock Problem,” European Journal of Operational Research, Vol. 84, No. 3, pp. 580-589 (1995) .
24. Holthaus, O., “Decomposition Approaches for Solving the Integer One-Dimensional Cutting Stock Problem with Different Types of Standard Lengths,” European Journal of Operational Research, Vol. 141, No. 2, pp. 295-312 (2002) .
25. Zak, E.J., “Modeling Multistage Cutting Stock Problems,” European Journal of Operational Research, Vol. 141, No. 2, pp. 313-327 (2002) .
26. Antonio, J., Chauvet, F., Chu, C., and Proth, J-M, “The Cutting Stock Problem with Mixed Objectives: Two Heuristics Based on Dynamic Programming,” European Journal of Operational Research, Vol. 114, No. 2, pp. 395-402 (1999) .
27. Caprara, A., Kellerer, H., Pferschy, U., and Pisinger, D., “Approximation Algorithms for Knapsack Problems with Cardinality Constraints,” European Journal of Operational Research, Vol. 123, No. 2, pp. 333-345 (2000) .
28. Harjunkoski, I., Westerlund, T., Pörn, R., and Skrifvars, H., “Different Transformations for Solving Non-Convex Trim-Loss Problems by MINLP,” European Journal of Operational Research, Vol. 105, No. 3, pp. 594-603 (1998) .
29. Gradišar, M., Resinovic, G., and Kljajic, M., “A Hybrid Approach for Optimization of One-Dimensional Cutting,” European Journal of Operational Research, Vol. 119, No. 3, pp. 719-728 (1999) .
30. Vasko, F.J., Newhart, D.D., Stott, J., and Kenneth L., “A Hierarchical Approach for One-Dimensional Cutting Stock Problems in the Steel Industry that Maximizes Yield and Minimizes Overgrading,” European Journal of Operational Research, Vol. 114, No. 1, pp. 72-82 (1999) .
31. Gradišar, M., Kljajic, M., Resinovic, G., and Jesenko, J., “A Sequential Heuristic Procedure for One-Dimensional Cutting,” European Journal of Operational Research, Vol. 114, No. 3, pp. 557-568 (1999) .
32. Vahrenkamp, R., “Random Search in the One-Dimensional Cutting Stock Problem,” European Journal of Operational Research, Vol. 95, No. 1, pp. 191-200 (1996) .
33. Chen, C-L, Hart, S.M., and Wai, M-T, “A Simulated Annealing Heuristic for the One-Dimensional Cutting Stock Problem,” European Journal of Operational Research, Vol. 93, No. 3, pp. 522-535 (1996) .
34. Wagner, B.J., “A Genetic Algorithm Solution for One-Dimensional Bundled Stock Cutting,” European Journal of Operational Research, Vol. 117, No. 2, pp. 368-381 (1999)
35. Liang, K-H, Yao, X., Newton, C., and Hoffman, D., “A New Evolutionary Approach to Cutting Stock Problems With and Without Contiguity,” Computers and Operations Research, Vol. 29, No. 12, pp. 1641-1659 (2002) .
36. Faina, L., “An application of simulated annealing to the cutting stock problem,” European Journal of Operational Research, Vol. 114, pp. 542-556 (1999) .
37. Umetani, S., Yagiura, M., and Ibaraki, T., “One-Dimensional Cutting Stock Problem to Minimize the Number of Different Patterns,” European Journal of Operational Research, Vol. 146, No. 2, pp. 388-402 (2003) .
38. Gau, T., and Wäscher, G., “CUTGEN1: A Problem Generator for the Standard One Dimensional Cutting Stock Problem,” European Journal of Operational Research, Vol. 84, No. 3, pp. 572-579 (1995) .
39. Gradišar, M., Resinovic, G., and Kljajic, M., “Evaluation of Algorithms for One-Dimensional Cutting,” Computers and Operations Research, Vol. 29, No. 9, pp. 1207-1220 (2002) .
40. Deck, G. and Scheuer, T., “Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing”, Journal of Computational Physics, Vol. 90, pp. 161–175 (1990) .
41. Glover, F., “Tabu Search , PartⅠ”, ORSA Journal on Computing, Vol. 1, No. 3, pp. 190 - 206 (1989) .
42. Glover, F., “Tabu Search , PartⅡ”, ORSA Journal on Computing, Vol. 2, No. 1, pp. 4 - 32 (1990) .
43. Glover, F., and Laguna, M., Tabu Search, Kluwer Academic Publishers, Norwell, Massachusetts, USA (1997) .
44. Kirkpatrick, S., Gelatt, C. D. Jr., and Vecchi, M. P., “Optimization by Simulated Annealing”, Science, Vol 220, pp. 671-680 (1983) .
45. Ravindra K. Ahuja, Ozlem Ergun, James B. Orlin, Abraham P. Punnen, “A survey of very large-scale neighborhood search techniques”, Discrete Applied Mathematics, Vol. 123, pp. 75-102 (2002)
46. S. Lin, B. Kernighan, “An effective heuristic algorithm for the traveling salesman problem”, Operations Research, Vol. 21, pp. 498-516 (1973)
47. E. Pesch, F. Glover, “TSP ejection chains”, Discrete Applied Mathematics, Vol. 76, pp. 165–181 (1997)
48. F. Glover, “Ejection chains, reference structures, and alternating path algorithms for the traveling salesman problem”, Discrete Applied Mathematics, Vol. 65, pp. 223–253 (1996)
49. C. Rego, “Relaxed tours and path ejections for the traveling salesman problem”, European Journal of Operation Research, Vol. 106, pp. 522–538 (1998)
50. M.L. Fredman, D.S. Johnson, L.A. McGeoch, “Data structures for traveling salesman”, Journal of Algorithms, Vol. 16, pp. 432–479 (1995)
51. M Laguna, J. Kelly, J.L. Gonzales-Velarde, F. Glover, “Tabu search for multilevel generalized assignment problem”, European Journal of Operation Research, Vol. 82, pp. 176–189 (1995)
52. M. Duque-Anton, “Constructing efficient simulated annealing algorithms”, Discrete Applied Mathematics, Vol. 77, pp. 139–159 (1997)
53. K.A. Dowsland, “Nurse scheduling with tabu search and strategic oscillation”, European Journal of Operation Research, Vol. 106, pp. 393–407 (1998)
54. J. Levine, F. Ducatelle, “Ant colony optimization and local search for bin packing and cutting stock problem”, Journal of Operation Research Society, Vol. 55, pp. 705–716 (2004)