.png){kind=icon}
.png){kind=icon}
Return
A heuristic algorithm for cube packing with time schedule
.png){kind=icon}
PRE
AI
DOI：10.1007/s11432-010-0022-z.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Packing problem has been proved to be an NP-hard problem. Many algorithms such as simulation annealing algorithm, genetic algorithm and other heuristic algorithms have been proposed to solve two-dimensional and three-dimensional packing problem. To solve the cube packing problem with time schedule, this paper first introduces some concepts such as packing level, space distance and average neighbor birth order and then proposes a greedy algorithm. The algorithm tries every feasible corner greedily to calculate the space utilization, packing level, space distance, average neighbor birth order of this placement, and chooses the best placement according to these criteria. Theoretical analysis indicates that the time complexity of this algorithm is O(A(2)B(2)C(2)T(2)n(5)). The experiments show that the average space utilization of non-guillotine cutting test cases is 98.81%, and the average space utilization of guillotine cutting test cases achieves 99.87%. Furthermore, optimal solutions of more than half cases are achieved by this algorithm. The experimental results show that this algorithm can solve the problem of cube packing with time schedule effectively and efficiently.
Keywords:
cube packing problem
time schedule
packing level
space distance
average neighbor birth order
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
7.6
Papers:
4.9K
Citations:
8.9K