| 二维矩形条带装箱问题的底部左齐择优匹配算法 |
| |
| 引用本文： | 蒋兴波,吕肖庆,刘成城. 二维矩形条带装箱问题的底部左齐择优匹配算法[J]. 软件学报, 2009, 20(6): 1528-1538. DOI: 10.3724/SP.J.1001.2009.03395 |
| |
| 作者姓名： | 蒋兴波 吕肖庆 刘成城 |
| |
| 作者单位： | 北京大学,计算机科学技术研究所,北京,100871;第二军医大学,卫生勤务学系,上海,200433;北京大学,计算机科学技术研究所,北京,100871;北京大学,电子出版新技术国家工程研究中心,北京,100871;北京大学,计算机科学技术研究所,北京,100871 |
| |
| 摘 要： | 针对二维矩形条带装箱问题提出了一种启发式布局算法,即底部左齐择优匹配算法(lowest-level left align best fit,简称LLABF). LLABF算法遵循最佳匹配优先原则,该原则综合考虑完全匹配优先、宽度匹配优先、高度匹配优先、组合宽度匹配优先及可装入优先等启发式规则.与BL(bottom-left),IBL(improved-bottom-left)与BLF(bottom-left-fill)等启发算法不同的是,LLABF能够在矩形装入过程中自动选择与可装区域匹配的下一个待装矩形
|
| 关 键 词： | 最低左对齐最佳匹配(LLABF)算法 遗传算法 二维矩形条带装箱问题 启发式布局算法 |
| 收稿时间： | 2008-02-29 |
| 修稿时间： | 2008-06-03 |
Lowest-Level Left Align Best-Fit Algorithm for the 2D Rectangular Strip Packing Problem |
| |
| JIANG Xing-Bo,L Xiao-Qing,LIU Cheng-Cheng. Lowest-Level Left Align Best-Fit Algorithm for the 2D Rectangular Strip Packing Problem[J]. Journal of Software, 2009, 20(6): 1528-1538. DOI: 10.3724/SP.J.1001.2009.03395 |
| |
| Authors: | JIANG Xing-Bo L Xiao-Qing LIU Cheng-Cheng |
| |
| Affiliation: | Institute of Computer Science and Technology;Peking University;Beijing 100871;China;Faculty of Health Services;Second Military Medical University;Shanghai 200433;China;National Engineering Research Center of New Technology in Electronic Publishing;China |
| |
| Abstract: | In this paper, a heuristic placement algorithm for the two-dimensional rectangular strip packing problem, lowest-level left align best fit (LLABF) algorithm, is presented. The LLABF algorithm is based on the best-fit priority principle with overall consideration of several heuristic rules, such as full-fit first rule, width-fit first rule, height-fit first rule, joint-width-fit first rule and placeable first rule. Unlike the bottom-left (BL), the improved-bottom-left (IBL) and the bottom-left-fill (BLF) heuristic placement algorithms, LLABF algorithm dynamically selects the best-fit rectangle for packing. The computation result shows that 2DR-SPP can be solved more effectively by combining the LLABF algorithm with the genetic algorithm (GA). |
| |
| Keywords: | lowest-level left align best fit (LLABF) algorithm genetic algorithm 2D rectangular strip packing problem heuristic placement algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
