菜单
  

        Meta-heuristic optimization methods have also been applied to the strip layout problem, both simulated annealing [11, 12] and genetic programming [13]. While capable of solving layout problems of great complexity (i.e. many different parts nested together, general 2-D nesting of sheets), they are not guaranteed to reach optimal solutions, and may take significant computational effort to converge to a good solution.
        Exact optimization algorithms have been developed for fitting a single part on a strip where the strip width is predetermined [14] and where it is determined during the layout process [15]. These algorithms are based on a geometric construction in which one shape is ‘grown’ by another shape. Similar versions of this construction are found under the names ‘no-fit polygon’, ‘obstacle space’ and ‘Minkowski sum’. Fundamentally, they simplify the process of determining relative positions of shapes such that the shapes touch but do not overlap. Through the use of this construction (in this paper, the particular version used is the Minkowski sum), efficient algorithms can be created that find the globally optimal strip layout.

        For the particular problem of strip layout for pairs of parts, results have been reported using the incremental rotation algorithm [7, 16] and simulated annealing [11], but so far no exact algorithm has been available. In what follows, the Minkowski sum and its application to strip layout is briefly introduced, and its extension to nesting pairs of parts is described.

    The Minkowski Sum
        The shape of blanks to be nested is approximated as a polygon with n vertices, numbered consecutively in the CCW direction. As the number of vertices increases, curved edges on the blank can be approximated to any desired accuracy. Given two polygons, A and B, the Minkowski sum is defined as the summation of each point in A with each point in B,
                                                         (1)
    Intuitively, one can think of this process as ‘growing’ shape A by shape B, or by sliding shape –B (i.e., B rotated 180º) around A and following the trace of some reference point on B. For example, Fig.1 shows an example blank A. If a reference vertex is chosen at (0, 0), and a copy of the blank rotated 180º (i.e., –A) is slid around A, the reference vertex on –A will trace out the path shown as the heavy line in Fig.2. This path is the Minkowski sum  . Methods for calculating the Minkowski sum can be found in computational geometry texts such as [17, 18].
     Sample Part A to be Nested.
    Minkowski Sum  (heavy line) of sample Part (light line).
        The significance of this is that if the reference vertex on –A is on the perimeter of  , A and –A will touch but not overlap. The two blanks are as close as they can be. Thus, for a layout of a pair of blanks with one rotated 180º relative to the other,   defines all feasible relative positions between the pair of blanks.

        A corollary of this property is that if the Minkowski sum of a single part is calculated. With its negative, i.e., . (A complete explanation of these properties of the Minkowski sum is given in [15].) These observations were the basis for the algorithm for optimally nesting a single part on a strip.

        The situation when nesting pairs of parts is more complex, since not only do the optimal orientations of the blanks and the strip width need to be determined, but the optimal relative position of the two blanks needs to be determined as well. To solve this problem, an iterative algorithm is suggested:
  1. 上一篇:电机物理计算英文文献和中文翻译
  2. 下一篇:制造工程与技术英文文献和中文翻译
  1. 汽车乘员舱的声振耦合英文文献和中文翻译

  2. 立体光照成型的注塑模具...

  3. 数控机床英文文献和中文翻译

  4. 工业机械手英文文献和中文翻译

  5. 低频振动的铁路车轴的状...

  6. 接头的形状对沥青塞接头...

  7. 数控加工技术英文文献和中文翻译

  8. java+mysql车辆管理系统的设计+源代码

  9. 当代大学生慈善意识研究+文献综述

  10. 十二层带中心支撑钢结构...

  11. 大众媒体对公共政策制定的影响

  12. 乳业同业并购式全产业链...

  13. 酸性水汽提装置总汽提塔设计+CAD图纸

  14. 杂拟谷盗体内共生菌沃尔...

  15. 中考体育项目与体育教学合理结合的研究

  16. 河岸冲刷和泥沙淤积的监测国内外研究现状

  17. 电站锅炉暖风器设计任务书

  

About

751论文网手机版...

主页:http://www.751com.cn

关闭返回