| 一种启发式矩形毛坯带排样算法研究 |
| |
| 引用本文： | 李霞,陈弦. 一种启发式矩形毛坯带排样算法研究[J]. 山西大学学报(自然科学版), 2011, 34(2): 215-218 |
| |
| 作者姓名： | 李霞 陈弦 |
| |
| 作者单位： | 1. 运城学院,公共计算机教学部,山西,运城,044000
2. 广西区电信,广西,南宁,530028 |
| |
| 基金项目： | 山西省教育厅科研基金(20091151) |
| |
| 摘 要： | 介绍一种两维矩形毛坯带排样问题的改进启发式递归算法,它基于递归结构和分支定界技术.首先初始化板材作为一个块,考虑目前的块,算法选择一个毛坯,将毛坯放在块的左下角,然后用水平或竖直的剪切线将未使用空间分为两个更小的块,便于进一步递归求解.使用上下界来去除无用的分支,缩短运算时间.将该算法和遗传算法相结合,先通过遗传算法确定所有矩形毛坯较优的排放顺序和排放方式,然后使用递归排样生成排样图,通过比较不同的矩形排放序列对应的板材利用率,最终得到较优的排样方案.测试数据表明了该启发式优化算法的有效性.
|
| 关 键 词： | 排样问题 遗传算法 递归 |
Heuristic Algorithm for the Rectangular Strip Packing Problem |
| |
| LI Xia,CHEN Xian. Heuristic Algorithm for the Rectangular Strip Packing Problem[J]. Journal of Shanxi University (Natural Science Edit, 2011, 34(2): 215-218 |
| |
| Authors: | LI Xia CHEN Xian |
| |
| Affiliation: | LI Xia1,CHEN Xian2(1.Department of Public Computer Teaching,Yuncheng University,Yuncheng 044000,China,2.Guangxi Telecom Sector,Nanning 530028,China) |
| |
| Abstract: | 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 prun... |
| |
| Keywords: | packing problem genetic algorithm recursion |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
