A real-time one-dimensional cutting stock algorithm for balanced cutting patterns

In the steel industry when a finished structural shape, exits the mill upon which it was produced, it is cut into customer order lengths. The actual length of the finished I-beam bar may not be known precisely until immediately before cutting. Also if the mill can produce bars faster than they can be cut, then trying to generate cutting patterns with the number of cuts per bar close to the average number of cuts per bar (balanced cutting patterns) will maximize primary saw (hotsaw) cutting and reduce the number of (more costly) cuts that have to be made at the secondary saw (coldsaw). In this paper, a PC-based branch-and-bound algorithm, DYNACUT, is discussed that generates high-yield, balanced cutting patterns in real-time (maximum three seconds/bar pattern generation time on a 486 machine) based on the precise length of the bar determined as it leaves the mill and arrives at the hotsaw for primary cutting. Examples based on actual orders will illustrate both the efficiency and effectiveness of this algorithm.