Heuristic algorithm for a cutting stock problem in the steel bridge construction

A rectangular two-dimensional cutting stock problem in the steel bridge construction is discussed. It is the problem of cutting a set of rectangular items from plates with arbitrary sizes that lie in the supplier specified ranges, such that the necessary plate area is minimized. Several types of cutting patterns are used to compose the cutting plan. All of them are easy to generate and cut except the last one. The algorithm uses both recursive and dynamic programming techniques to generate patterns of the last type. The computational results of 22 practical instances indicate that the algorithm can produce solutions close to optimal, and the computation time is reasonable for practical use.