| 基于两段排样方式的矩形件优化下料算法 |
| |
| 作者姓名： | 扈少华 武书彦 潘立武 |
| |
| 作者单位： | 河南牧业经济学院软件学院，河南 郑州 450011 |
| |
| 基金项目： | 河南省科技厅科技攻关项目(152102210320)；河南省高等学校重点科研项目(15B52000) |
| |
| 摘 要： | 针对矩形件下料问题，提出一种基于两段排样方式的优化下料算法。首先构造一
种约束排样算法，生成矩形件在板材上的两段排样方式。然后采用列生成算法依据矩形件剩余
需求量迭代调用上述约束排样算法生成一个虚拟下料方案，按照不产生多余矩形件原则选取虚
拟下料方案中的部分排样方式加入到实际下料方案中，更新矩形件剩余需求量；重复上述步骤
直到矩形件剩余需求量为零。采用文献中基准例题将该算法与2 种文献算法进行比较，数值实
验结果表明该算法下料利用率比2 种文献算法分别高1.61%和0.78%。
|
| 关 键 词： | 下料问题 两段排样方式 列生成算法 约束排样 矩形件 |
An Optimization Algorithm for Rectangular Items Cutting Stock Problem Based on Two-Segment Patterns |
| |
| Authors: | HU Shaohua WU Shuyan PAN Liwu |
| |
| Affiliation: | Software College, Henan University of Animal Husbandry & Economy, Zhengzhou Henan 450011, China |
| |
| Abstract: | For on the rectangular items cutting stock problem, an optimization algorithm based on
two-segment patterns is proposed. Firstly, a constrained packing algorithm is constructed to generate
the two-segment patterns of rectangular items on the plate. Then, column generation algorithm is used
to generate a virtual cutting plan according to the current remaining demand of rectangular items,
several patterns are added into actual cutting plan according to the rule that no redundant rectangular
item is generated, and the current remaining demand of rectangular items is updated. The above steps
are repeated until the remaining demand of rectangular items is zero. Compared the proposed
algorithm with two algorithms in the literature through benchmark instances, results of numerical
experiments show that material utilization of the proposed algorithm is higher than two literature
algorithms about 1.61% and 0.78%, respectively. |
| |
| Keywords: | cutting stock problem two-segment patterns column generation algorithm constrained packing rectangular items |
|
| 点击此处可从《》浏览原始摘要信息 |
|
点击此处可从《》下载全文 |
