- 上一篇：德语论文中德关系以上海与汉堡的友好关系为例
- 下一篇：对比中德经典城市文化之旅德语论文
When more than one part is manufactured at the same time, within the 3D graphic environment, the operator simulates packing of actual parts by placing them, or their CAD models, inside an envelope on a computer screen and makes sure that parts do not intersect with each other, and that they are totally inside the building volume. Parts in each batch can be used for different applications and for different customers. Thus the shape and size of parts can vary dramatically, which makes it even more difficult for an operator to find an optimal model layout solution manually. Therefore, a computerized system is needed to find the optimal batch configuration layout for the minimum cost of production.
2. Related research work
The model layout problem can be categorized into the well-known bin-packing problem. Applications of the bin-packing problem can be found in VLSI layout design, stock cutting and other fields. The classical 2D and 3D bin-packing problems have been proven to be NP-hard [3]. Since the bin-packing problem is of practical importance, efficient approximation algorithms that produce close-to-optimal solutions have been developed. These approaches include linear programming, heuristic techniques, simulated annealing (SA) and genetic algorithm (GA).
Linear programming methods have been extensively studied and successfully applied to a broad class of stock cutting problems. However, these methods are not appropriate for many real problems due to their structures or sizes. In such cases, heuristic methods are used, such as dynamic programming and tree-search methods. Dynamic programming is a method that converts a problem into a series of single-stage problems. The difficulty is in quickly determining the optimal decisions. The tree-search method enumerates all possible solutions in a tree Dynamic programming is a method that converts a problem into a series of single-stage problems.-like structure. Heuristics start out on one path and terminate when either an optimal solution is believed to have been found or the path is known to result in an unsatisfactory solution. Most of the above approaches either do not give an optimal or near optimal solution or are not applicable to a wide variety of applications, and the formulations of problems are rather complicated [4].
To overcome the limitations of linear programming and heuristic techniques, research efforts have been made using SA and GA to solve packing problems. Rao and Iyengar [5] applied SA to a variety of the bin-packing problems. Extensive simulation experiments demonstrated that the solutions obtained by SA showed a significant improvement over those obtained by any of the well-known heuristic methods. Cagan [6] explored 2D and 3D layout problems using SA. An adaptive annealing schedule, multi-resolution modeling and a dynamic move selection strategy were proposed to improve algorithm performance. Han and Na [7] proposed a nesting approach with two stages: initial layout stage and layout improvement stage. A self organization assisted layout algorithm generates a ‘good’ initial layout; then SA was used to improve the initial layout. Corcoran [8] explored GA in 3D packing problems and showed that GA yielded good solutions for 3D packing problem.
It is worthwhile to mention that Ikonen et al. [9] used GA to solve a 3D model layout problem for an SLS machine.Most of the research mentioned above simplify shapes of the parts. Ikonen’s approach does not require geometry of parts to be simplified before packing. However, the searching process of the packing can be very time-consuming using this method (e.g. 8.5 h for 15 parts).
In short, it has been demonstrated that GA and SA are capable of solving bin-packing problems. However, the performances of GA and SA in terms of efficiency and effectiveness depend greatly on the solution space, the implementation strategies and the objective functions. In this study, SA algorithm was applied to the present packing problem according to the specific objective function and searching strategies for SGC processes.