Abstract: To effectively solve the long board rectangular optimal layout problems which is often
encountered in the actual production of enterprises, rectangular optimal layout algorithms were studied
and a rectangular optimal layout algorithm based on the best sub segments was proposed, which
effectively solve long board rectangular optimal layout problems in actual production. Firstly based on
dynamic programming algorithm all sub optimal layout modes were solved which is less than the shear
blade length. Secondly with the best sub segments as layout parts, these segments were optimized on
the long board and the rectangular optimal layout problems were converted to knapsack problems
completely. Finally the integer programming algorithm based on branch and bound technique was used
to solve the long board rectangular optimal layout problems. Enterprise’s practical application showed
that the algorithm in solving the long board rectangular optimization problems is better than other
algorithms.

Key words: rectangular optimal layout, best sub segment, dynamic programming algorithm, branch and
bound technique