一种启发式矩形毛坯带排样算法研究

摘要

介绍一种两维矩形毛坯带排样问题的改进启发式递归算法,它基于递归结构和分支定界技术.首先初始化板材作为一个块,考虑目前的块,算法选择一个毛坯,将毛坯放在块的左下角,然后用水平或竖直的剪切线将未使用空间分为两个更小的块,便于进一步递归求解.使用上下界来去除无用的分支,缩短运算时间.将该算法和遗传算法相结合,先通过遗传算法确定所有矩形毛坯较优的排放顺序和排放方式,然后使用递归排样生成排样图,通过比较不同的矩形排放序列对应的板材利用率,最终得到较优的排样方案.测试数据表明了该启发式优化算法的有效性.%Based on a recursive structure and branch-and-bound techniques,the improved heuristic recursive algorithm for the two-dimensional rectangular strip packing problem was introduced.Initially the plate is taken as a block,Considering the block,the algorithm selects an item and puts this item at the bottom-left corner of the block.For the convenience of recursive solution, the unoccupied region is divided into two smaller blocks by a level or plumb guillotine line.Both the lower and upper bounds are used to prune unpromising branches to shorten the running time.The procedure is combined with genetic algorithm.It uses genetic algorithm to have a better packing order and packing mode,and it uses recursion packing to generate the packing result picture.Finally it gets the optimized packing project through comparing with the plate utilization efficiency of different rectangle packing sequences.The test data shows that the heuristic optimal algorithm is effective.