We propose a new constructive algorithm, called HAPE3 D, which is a heuristic algorithm based on the principle of minimum total potential energy for the 3D irregular packing problem, involving packing a set of irregul...We propose a new constructive algorithm, called HAPE3 D, which is a heuristic algorithm based on the principle of minimum total potential energy for the 3D irregular packing problem, involving packing a set of irregularly shaped polyhedrons into a box-shaped container with fixed width and length but unconstrained height. The objective is to allocate all the polyhedrons in the container, and thus minimize the waste or maximize profit. HAPE3 D can deal with arbitrarily shaped polyhedrons, which can be rotated around each coordinate axis at different angles. The most outstanding merit is that HAPE3 D does not need to calculate no-fit polyhedron(NFP), which is a huge obstacle for the 3D packing problem. HAPE3 D can also be hybridized with a meta-heuristic algorithm such as simulated annealing. Two groups of computational experiments demonstrate the good performance of HAPE3 D and prove that it can be hybridized quite well with a meta-heuristic algorithm to further improve the packing quality.展开更多
We excavate the wisdom from an old Chinese proverb "gold corner, silver side and strawy void", and further improve it into "maximum value in diamond cave" for solving the NP-hard cuboid packing problem. We extract...We excavate the wisdom from an old Chinese proverb "gold corner, silver side and strawy void", and further improve it into "maximum value in diamond cave" for solving the NP-hard cuboid packing problem. We extract, integrate and formalize the idea by west modern mathematical tools, and propose a pure quasi-human algorithm. The performance of the algorithm is evaluated on two sets of public benchmarks. For 100 strongly heterogeneous difficult benchmarks, experiments show an average packing utilization of 87.31%, which surpasses current best record reported in the literature by 1.83%. For 47 difficult benchmarks without orientation constraint, experiments show an average volume utilization of 92.05%, which improves current best record reported in the literature by 1.05%.展开更多
The three-dimensional packing problem is generally on how to pack a set of models into a given bounding box using the smallest packaging volume. It is known as an NP-hard problem. When discussing the packing problem i...The three-dimensional packing problem is generally on how to pack a set of models into a given bounding box using the smallest packaging volume. It is known as an NP-hard problem. When discussing the packing problem in mechanical field, the space utilization of a mechanism is low due to the constraint of mechanical joints between different mechanical parts. Although such a situation can be improved by breaking the mechanism into components at every joint, it burdens the user when reassembling the mechanism and may also reduce the service life of mechanical parts. In this paper, we propose a novel mechanism packing algorithm that deliberately considers the DOFs (degrees of freedom) of mechanical joints. With this algorithm, we construct the solution space according to each joint. While building the search tree of the splitting scheme, we do not break the joint, but move the joint. Therefore, the algorithm proposed in this paper just requires the minimal number of splits to meet the goal of space utilization. Numerical examples show that the proposed method is convenient and efficient to pack three-dimensional models into a given bounding box with high space utilization.展开更多
Since the raising of the cloud computing, the applications of web service have been extended rapidly. However, the data centers of cloud computing also cause the problem of power consumption and the resources usually ...Since the raising of the cloud computing, the applications of web service have been extended rapidly. However, the data centers of cloud computing also cause the problem of power consumption and the resources usually have not been used effectively. Decreasing the power consumption and enhancing resource utilization become main issues in cloud computing environment. In this paper, we propose a method, called MBFDP (modified best fit decreasing packing), to decrease power consumption and enhance resource utilization of cloud computing servers. From the results of experiments, the proposed solution can reduce power consumption effectively and enhance the utilization of resources of servers.展开更多
In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties...In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties are explored,then an optimal algorithm OPFIV with time complexity O(log(n+m))is developed and its correctness and optimization are proved rigorously.展开更多
基金supported by the Natural Science Foundation of Guangdong Province,China(No.S2013040016594)the Natural Science Foundation of Liaoning Province,China(No.201102164)the Fundamental Research Funds for the Central Universities,China(No.2013ZM0124)
文摘We propose a new constructive algorithm, called HAPE3 D, which is a heuristic algorithm based on the principle of minimum total potential energy for the 3D irregular packing problem, involving packing a set of irregularly shaped polyhedrons into a box-shaped container with fixed width and length but unconstrained height. The objective is to allocate all the polyhedrons in the container, and thus minimize the waste or maximize profit. HAPE3 D can deal with arbitrarily shaped polyhedrons, which can be rotated around each coordinate axis at different angles. The most outstanding merit is that HAPE3 D does not need to calculate no-fit polyhedron(NFP), which is a huge obstacle for the 3D packing problem. HAPE3 D can also be hybridized with a meta-heuristic algorithm such as simulated annealing. Two groups of computational experiments demonstrate the good performance of HAPE3 D and prove that it can be hybridized quite well with a meta-heuristic algorithm to further improve the packing quality.
基金Supported by the National Natural Science Foundation of China (Grant No. 60773194)the National Basic Research Program of China (GrantNo. 2004CB318000)Postdoctoral Science Foundation of China (Grant No. 20070420174)
文摘We excavate the wisdom from an old Chinese proverb "gold corner, silver side and strawy void", and further improve it into "maximum value in diamond cave" for solving the NP-hard cuboid packing problem. We extract, integrate and formalize the idea by west modern mathematical tools, and propose a pure quasi-human algorithm. The performance of the algorithm is evaluated on two sets of public benchmarks. For 100 strongly heterogeneous difficult benchmarks, experiments show an average packing utilization of 87.31%, which surpasses current best record reported in the literature by 1.83%. For 47 difficult benchmarks without orientation constraint, experiments show an average volume utilization of 92.05%, which improves current best record reported in the literature by 1.05%.
基金The work was supported by the National Key Research and Development Program of China under Grant No. 2017YFC0804401, the National Natural Science Foundation of China under Grant Nos. 61472370, 61672469, 61379079, 61322204, and 61502433, the Natural Science Foundation of Henan Province of China under Grant No. 162300410262, and the Key Research Projects of Henan Higher Education Institutions of China under Grant No. 18A413002.
文摘The three-dimensional packing problem is generally on how to pack a set of models into a given bounding box using the smallest packaging volume. It is known as an NP-hard problem. When discussing the packing problem in mechanical field, the space utilization of a mechanism is low due to the constraint of mechanical joints between different mechanical parts. Although such a situation can be improved by breaking the mechanism into components at every joint, it burdens the user when reassembling the mechanism and may also reduce the service life of mechanical parts. In this paper, we propose a novel mechanism packing algorithm that deliberately considers the DOFs (degrees of freedom) of mechanical joints. With this algorithm, we construct the solution space according to each joint. While building the search tree of the splitting scheme, we do not break the joint, but move the joint. Therefore, the algorithm proposed in this paper just requires the minimal number of splits to meet the goal of space utilization. Numerical examples show that the proposed method is convenient and efficient to pack three-dimensional models into a given bounding box with high space utilization.
文摘Since the raising of the cloud computing, the applications of web service have been extended rapidly. However, the data centers of cloud computing also cause the problem of power consumption and the resources usually have not been used effectively. Decreasing the power consumption and enhancing resource utilization become main issues in cloud computing environment. In this paper, we propose a method, called MBFDP (modified best fit decreasing packing), to decrease power consumption and enhance resource utilization of cloud computing servers. From the results of experiments, the proposed solution can reduce power consumption effectively and enhance the utilization of resources of servers.
文摘In this paper,we study the problem,of calculating the minimum collision distance between two planar convex polygons when one of them moves to another along a given direction.First,several novel concepts and properties are explored,then an optimal algorithm OPFIV with time complexity O(log(n+m))is developed and its correctness and optimization are proved rigorously.