A novel heuristic algorithm for two-dimensional rectangle packing area minimization problem with central rectangle

The rectangle packing area minimization problem (RPAMP) has a wide range of applications in the industrial production. A special RPAMP with central rectangles that must be located in the center of the final layout is proposed and named CR-RPAMP in which the length-width ratio of the final layout can be changed legitimately within a reasonable scope. In this paper, for the purpose of solving the CR-RPAMP, a novel heuristic algorithm called HACR is presented. In HACR, by constraining the aspect ratio of enveloping rectangle, the length-width ratio of the final rectangular frame can meet the requirements. Besides, by constraining the betweenness centrality of central rectangle, the central rectangle can be located in the center of the final layout. In order to minimize the area of the enveloping rectangle, the solution procedure of HACR has been projected based on defining the priority of candidate rectangle. Strategies of padding inner space are put forward to improve the filling rate of the final layout. Comprehensive experiments were conducted on 34 international instances reported in the literature. Simulation results show that the proposed novel heuristic algorithm was effective and practicable. At last, the proposed HACR is applied to research the layout of drilling equipment in deep water semi-submersible platforms.