The characteristic and shortcoming of the common algorithm of constrained two-dimensional Non-Guillotine Optimal cutting stock problem are analysed. Base of designing a model of cutting stock problem, a new heuristic algorithm applying column generation algorithm and simulated annealing algorithm is shown. The presentation of the processing steps and the data structure prove that the algorithm has fast computing speed and excellent result. An examples by the algorithm are given, which indicates the algorithm is new and effective.