This paper presents a heuristic algorithm for solving a specific NP-hard2d rectangular packing problem in which a rectangle called central rectangle is required to be placed in the center of the final layout, and the...
详细信息
This paper presents a heuristic algorithm for solving a specific NP-hard2d rectangular packing problem in which a rectangle called central rectangle is required to be placed in the center of the final layout, and the aspect ratio of the container is also required to be in a given range. The key component of the proposed algorithm is a greedy constructive procedure, according to which, the rectangles are packed into the container one by one and each rectangle is packed into the container by an angle-occupying placement with maximum fit degree. The proposed algorithm is evaluated on two groups of 35 well-known benchmark instances. Computational results disclose that the proposed algorithm outperforms the previous algorithm for the packingproblem. For the first group of test instances, solutions with average filling rate 99.31% can be obtained;for the real-world layout problem in the second group, the filling rate of the solution is 94.75%.
暂无评论