二维不规则样片自动排料算法的优化研究

Study on Optimization Algorithm for Automatic Discharging of Two-Dimensional Irregular Sample

为了实现工业生产中多种类二维不规则样片排料过程的自动化和版面的高效率利用,提出了一种新算法,即将矩形法和基于面积集的动态规划法相结合来解决样片的优化排料。在排版前的预处理中,计算出每种样片的单独排版最优角度和样片方正度,并且产生包络矩形组,通过面积比较决定矩形组是否可用。正式排版过程中,先从矩形组中选出面积最大的矩形件作为第一个样片排版,该行剩余空间的排版则运用动态规划法,从矩形组中挑选出不同的矩形组合进行模拟排版,并记录面积,待矩形组合模拟排版完毕后,从面积集中选出面积最小的作为该行剩余空间的排版方式。若矩形组已排版完毕,则运用动态规划法排版单个样片,根据样片的方正度和排版占据面积最小这两个因素确定单个样片的排版。

In order to realize discharging automation of various two-dimensional irregular samples in industrial production and efficient utilization of layout, a new algorithm is proposed, i.e. combine rectangle method and dynamic programming method based on area set to solve optimized discharging of samples. In pretreatment before typesetting, it is required to calculate optimal angle of each sample in single typesetting and upright and foursquare degree of the samples, generate envelope rectangle group and decide whether the rectangle group is usable through area comparison. In the formal process of typesetting, the largest rectangle piece should be selected from the rectangle group as the layout of the first sample. The layout for the remaining space in this row adopts dynamic programming method. Different rectangle combinations are selected from the rectangle group for simulated layout and the area should be recorded. After the completion of simulated layout of rectangle combinations, the smallest one from the area set is selected as the layout mode of the remaining space. If the rectangle group has been finished, dynamic programming method is adopted for single sample layout. Single sample layout is confirmed according to upright and foursquare degree of the samples and smallest layout area.