二维切割与装填布局问题的前瞻自适应算法研究

项目名称： 二维切割与装填布局问题的前瞻自适应算法研究

项目编号： No.61363026

项目类型： 地区科学基金项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 崔耀东

作者单位： 广西大学

项目金额： 45万元

中文摘要： 研究二维布局问题，包括下料问题和装箱问题。前者涉及制造业的金属板材和带材、家具制造业的木板、建筑与装饰业的平板玻璃等二维下料问题；后者涉及运输与仓储业的二维装箱问题。二维布局问题具有NP难度，其解是一个排样方案，其中包括多个排样方式（排样图）。通过优化排样方案，可降低材料成本或运输仓储成本。以二维下料为例，本项目具体解决如下问题：使用n种库存板材制作m种矩形毛坯，已知每种板材的尺寸和供应量、每种毛坯的尺寸和需求量，确定排样方案使材料成本最低。采用前瞻自适应方法，由排样方式生成算法和排样方案生成算法组成；前者生成各个排样方式，后者组合各个排样方式形成排样方案。在当前排样方式生成过程中，用前瞻法预测每个分支的效果，优选当前要放置的毛坯与位置；根据当前排样方式的信息，对排样参数进行自适应调整，指导后续排样方式的生成；生成大量排样方案以充分进行自适应调整和方案优选，达到有效降低材料成本的目的。

中文关键词： 切割与装填；二维下料问题；二维装箱问题；二维带排样问题；前瞻自适应技术

英文摘要： This project focuses on the 2D cutting & packing problem, which includes the cutting stock problem and bin packing problem. The former is concerned with the cutting stock of metal plates and strips in the manufacturing industry, wood boards in the furnitu

英文关键词： Cutting & packing；Two-dimensional cutting stock；Two-dimensional bin packing；Two-dimensional strip packing；Lookahead and adaptive techniques