Research On Rectangle Packing Problems With Guillotine Constraint

Cutting-stock is an important link in the assembly line of production logistics.The most critical work in this process is to formulate the layout plan.This paper studies rectangle packing problem,the optimized rectangle packing problem means that the rectangular pieces are arranged on the board according to certain process constraints,so as to maximize the utilization of board.Rectangle packing problem is not only concerned by many scholars,but also an important issue for enterprises to improve resource utilization.The rationality of rectangle packing not only directly affects the utilization rate of boards,but also reduce the transport of materials,improve processing efficiency,reduce production costs and so on,so it is urgent to optimize the problem.Considering the process constraints of fiber direction,guillotine and knife gap in board cutting,a mathematical model was established with the goal of maximizing the average utilization of board.Due to the high time complexity in solving process,it belongs to NP problem.Using enumeration method,knapsack algorithm and linear programming method in operations research will be effective only when the scale of the problem is small,in order to solve the problem generally,heuristic algorithm is chosen to solve the problem.Four basic rectangle packing algorithms are introduced in this paper,they are Bottom-Left algorithm,downstairs algorithm,lowest horizontal line algorithm and filling algorithm,by comparing the characteristics of the algorithm,the filling algorithm which can both satisfy the guillotine constraint,knife gap and fiber direction is selected as the method in this paper.Although the algorithm can satisfy the above constraints,it has the problems of small test range and single arrangement,which indirectly causes the low utilization rate of the layout.Considering the above shortcomings,the paper proposes an improved filling algoritlun,which increased the arrangement of rectangular pieces,not only for the vertical layout of rectangular pieces,but also for the horizontal layout of rectangular pieces;enlarged the test range of rectangular pieces,and realized the diversity of layout by means of untried rectangular pieces being tested on all the remaining materials.In addition,both the filling algorithm and the improved filling algorithm are only for sequential layout,the high-quality layout scheme can not be obtained by layout rules alone,so the optimization of the single layout sequence is made,by adding the horizontal layout of rectangular pieces to the basis of filling algorithm and introducing genetic algorithm,using the character of global search ability to optimize the order of rectangular pieces.The local optimization ability of the rectangular filling algorithm for the layout effect and the global search ability of the genetic algorithm for the order of rectangular pieces are fully utilized in the hybrid algorithm.Finally,examples of different scales shows that the improved algorithm can effectively improve the utilization of board,it can also provide technical support for practical operation.In summary,the innovations of this paper are mainly embodied in three aspects.Firstly,an improved filling algorithm is proposed,and the layout rules are optimized,which proves the effectiveness of the improved algorithm.Secondly,considering both the guillotine constraint and knife gap in layout,it is more suitable in actual cutting operation.Finally,for the complex layout problem,a hybrid algorithm combining genetic algorithm and improved filling algorithm is proposed,which realizes the further improvement of boards efficiency in complex layout.