实用下料问题的优化算法

• 作者: 利伟业 陈秋晓 顾梦君
• 来源期刊: 中山大学研究生学刊：自然科学与医学版
• 学科: 工学
• 关键词: 下料问题 优化算法 下料方案 下料方法 下料方式 完成时间 优先次序 搜索过程 状态空间 一维问题 二维问题 原材料 零件 权值 原料 导向 回溯法 长度比 遍历法 二叉树 适应性 初始值 模式 切割 动态 废料 编程
• 年，卷（期）: 2005,（2）
• 页码范围: 92-96
• 页数: 5页
• 分类号: TP30

摘要

本文针对单一原材料下料问题，讨论了如何在合理的时间内求得一维和二维实用下料问题的较优解。我们实现的是一种改进的以模式为导向的下料方案。以模式为导向的下料方法是相对于以需求为导向的下料方法而言的，即把几种零件组合进行下料，一次切割可得到不同规格的零件，以达到节省原材料的目的。我们的改进是引入了动态权值，具体来说，依据各零件的完成时间要求，赋给每种零件一个权值，而且这个权值会随着下料的进行而不断改变，以调整下料时零件的优先次序。引入动态权值后，不仅能解决时限问题，而且能优化搜索过程。在搜索下料方案的过程中，一维主要采用回溯法搜索部分状态空间，从中找出较优解；二维情形，观察到各种零件的长度比原料的宽度大很多，所以只能按原料的长边方向切割零件的长边，我们运用二叉树前序遍历法去寻找较优解。求得一维问题的下料结果是：需要804块原料，61种下料方式，废料总长度为37012mm，能保证任务按时完成。求得二维问题的解答：需要472块原料，52种下料方式，废料总长度为7340880mm^2，能保证任务按时完成。本模型具有操作简便，求解速度快，适应性好等优点，稍稍修改一些初始值就可以适应新的实际情况。算法是用编程来实现的。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	顾梦君	中山大学数学与计算科学学院	3	0	0.0	0.0
2	利伟业	中山大学数学与计算科学学院	2	0	0.0	0.0
3	陈秋晓	中山大学数学与计算科学学院	2	0	0.0	0.0