BH型鋼被廣泛地應用於各種鋼結構工程中。鋼構廠由煉鋼廠取得鋼板後，裁切成為適當尺寸後焊接組合成為BH型鋼。原料成本為鋼結構工程最主要的成本項目之一，而裁切計畫之良窳影響裁切餘料比例，直接影響工程成本。由於裁切計畫之擬定需要考慮相當複雜的因素，現今實務上仍以人工為之，缺乏自動化之軟體工具。本研究之目的即在分析BH型鋼裁切問題後，提出一套啟發式演算法來擬定裁切計畫，以最小化裁切時產生的餘料。
本演算法配合實務經驗與需求，將裁切計畫之求解過程分解為長度合併與寬度合併兩大部分。前者使用混合整數規畫模式以求解將較短型鋼合併成為較長型鋼的方式，而後者則以配對問題為數學模型，求解鋼板利用的有利方式，並納入優先使用庫存鋼板之考量。演算法先以簡單的方式產生可行初始解之後，經由反覆運算逐步改善其品質。其中並使用擾動機制避免現行解陷入局部最佳解。真實案例測試結果顯示，本演算法可求得與實務相同品質的裁切計畫。此外本研究並以600組隨機測試案例，以探討本演算法在不同情況下之求解能力。這些案例的型鋼數量介於60與120之間，求解時間均在一小時以內。求解所得餘料比例受型鋼長度組合以及優先使用庫存鋼板與否之影響，大都在10%上下。

Steel H-beams are widely used in steel constructions. Factories acquire plates from still mills, cut them into components of appropriate sizes and shapes, and weld the components together to form H-beams. Cutting plans determine the loss ratio, which impact the overall cost directly, due to the fact that material cost is one of the major cost items in steel construction projects. Despite its importance, cutting plans are still developed manually in practice with little help from computers, mostly due to its high complexity. The purpose of this research is to analyze the H-beam cutting problem and propose a heuristic algorithm that yields high-quality cutting plans. The optimization goal is to minimize the loss ratio.
Taking demand and experience into consideration, our heuristic decomposes the solution process into two parts, namely the length-wise combination part, and the width-wise combination part. The former uses a mixed-iteger program to solve for promising ways to combine shorter H-beams into longer ones, and the latter uses an assignment problem model to discover good methods to highly utilize the plates. After generating an initial feasible solution with a simple rule, the heuristic iterates between these two parts, and utilizes a purturbing mechanism to avoid being trapped in the vicinity of local optimal solutions. Testing with real instances indicate that the heuristic is able to generate cutting plans that are identical to real ones. When tested with 600 randomly generated instances with the number of H-beams ranging from 60 to 120, and all of them are solved under one hour CPU time. Depending on the combination of beam lengths as well as consideration of in-stock plates, the resulting loss ratio are generally in the vicinity of 10%.

[1] Gilmore, P. C. and R. E. Gomory (1961). "A Linear Programming Approach to the Cutting-Stock Problem." Operations Research 9(6): 849-859.
[2] Cui, Y. (2005). "A cutting stock problem and its solution in the manufacturing industry of large electric generators." Computers & Operations Research 32(7): 1709-1721.
[3] Morabito, R. and L. Belluzzo (2007). "Optimising the cutting of wood fibre plates in the hardboard industry." European Journal of Operational Research 183(3): 1405-1420.
[4] Cui, Y., T. Gu and W. Hu (2009). "A cutting-and-inventory control problem in the manufacturing industry of stainless steel wares." Omega 37(4): 864-875.
[5] Lodi, A., S. Martello and M. Monaci (2002). "Two-dimensional packing problems: A survey." European Journal of Operational Research 141(2): 241-252.
[6] Martello, S. and P. Toth (1990). Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Chichester.
[7] Scholl, A., R. Klein and C. rgens (1997). "Bison: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem." Computers & Operations Research 24(7): 627-645.
[8] Martello, S. and D. Vigo (1998). "Exact Solution of the Two-Dimensional Finite Bin Packing Problem." Management Science 44(3): 388-399.
[9] George, J. A., J. M. George and B. W. Lamar (1995). "Packing different-sized circles into a rectangular container." European Journal of Operational Research 84(3): 693-712.
[10] Binkley, K. J. and M. Hagiwara (2007). "Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners' heuristic." European Journal of Operational Research 183(3): 1230-1248.
[11] Lodi, A., S. Martello and D. Vigo (1999). "Heuristic and Metaheuristic Approaches for a Class of Two-Dimensional Bin Packing Problems." INFORMS Journal on Computing 11(4): 345.
[12] Lodi, A., S. Martello and D. Vigo (2002). "Recent advances on two-dimensional bin packing problems." Discrete Applied Mathematics 123(1-3): 379-396.
[13] Friesen, D. K. and M. A. Langston (1986). "Variable Sized Bin Packing." SIAM Journal on Computing 15(1): 222-230.
[14] Chu, C. and R. La (2001). "Variable-Sized Bin Packing: Tight Absolute Worst-Case Performance Ratios for Four Approximation Algorithms." SIAM Journal on Computing 30(6): 2069-2083.
[15] Kos, L. and J. e. Duhovnik (2002). "Cutting optimization with variable-sized stock and inventory status data." International Journal of Production Research 40(10): 2289 - 2301.
[16] Kang, J. and S. Park (2003). "Algorithms for the variable sized bin packing problem." European Journal of Operational Research 147(2): 365-372.
[17] Chen, C. S., S. M. Lee and Q. S. Shen (1995). "An analytical model for the container loading problem." European Journal of Operational Research 80(1): 68-76.
[18] Wäscher, G., H. Haußner and H. Schumann (2007). "An improved typology of cutting and packing problems." European Journal of Operational Research 183(3): 1109-1130.
[19] Ahuja, R., T. Magnanti and J. Orlin (1993). Network flows theory, algorithms, and applications. Englewood Cliffs, N.J, Prentice Hall.