A Heuristic Algorithm For Two-Dimensional Rectangle Cutting Optimization

The Two-Dimensional Rectangular Cutting Optimization Problem is a combinatorial optimization problems and it has been proved to be an NP-hard problem in computational complexity theory.In the chemical industry production,processes such as cutting of raw materials or semi-finished products are often involved.The Two-Dimensional Rectangular Cutting Problem is the most widely used in industry compared to single-dimensional and multi-dimensional cutting problems,and it has considerable development prospects.Therefore,studying this problem has great importance and significance to improve the economic effect of enterprises and promote theoretical research in academia.The Two-Dimensional Rectangular Cutting Optimization Problem is to cut a standard size raw material into a specific size through the Guillotine cut,in which process the waste is generated.The objective of the problem is to minimize the given ordered raw materials and the geometrical loss of the cutting patters applied on materials.The Iterative Perturbation mechanism and a branch and bound Heuristic Tree Search algorithm(IHTS-P)for solving this problem has been proposed.The depth-first search is used to explore the solution space,and the branch strategy is added to subdivide the solution space.In addition,the pruning strategy is to speed up the algorithm.In order to enhance the quality and efficiency of the solution,an iterative optimization strategy and a tabu-based perturbation one have been employed.The technique has achieved the balance of determination and diversification.In order to evaluate the performance of IHTS-P,a set of real-world instances are tested.From the empirical experimental evaluation,it is shown that this method is able to gain significant better solution than the two mixed integer programming models proposed in this paper: Complete Model(CM)and Iterative Model(IM).Furthermore,the experiments not only illustrate that the proposed method performs remarkable with regard to the current best solutions,but also analyze the solutions of each algorithm on different running times.