Approximate Algorithm Applied In Stock Cutting Problems

Stock cutting problem is a kind of general resource allocation problem,in industry we ofen meet stock cutting problems,it is urgent for us to give a highest utilization of the stock .Through modern optimizational algorithm and great computing ability of computer,we can get the optimal layout which satisfies the need of industry producty.Stock cutting problems have three groups :one dimensional stock cutting problems,two dimensional stock cutting problems and three dimensional layout problems .In this paper we discuss the mathmatical model and optimal algorithm of one dimensional stock cutting problems and two dimensional stock cutting problems. In the first chapter we discuss the background and the necessity of the stock cutting problems and the methods which can be used to solve optimal layout problems.Then give some scholars'research work. In the second chapter we discuss the model and algorithm of one dimensiona stock cutting problems.We present two methods. In the first method the best cutting pattern for current situation is studied,this process is repeated until all required stocks have been cut.In the second method we use pack algorithm to compute one dimensional stock cutting problems. In the third chapter ,we discuss the model and algorithm of two dimensional stock cutting problems. The cutting pattern should satisfy the requirement of guillotine, I proposed a new algorithm—the reticle algorithm and an approximate algorithm.Then we present genetric algorithm and simulated annealing algorithm.Numerical examples show these methods are useful to stock cutting problems. In the fourth chapter we discuss the problems of integer programming,we use simulated annealing algorithm and give two numerical examples. At last , we summarized all the works in the thesis and proposed some prospects.