实用下料问题的优化算法

• 作者: 利伟业 陈秋晓 顾梦君
• 来源期刊: 中山大学研究生学刊（自然科学版）
• 关键词: 下料问题(CSP问题) 动态权值 回溯法 二叉树前序遍历
• 年，卷（期）: 2005,（2）
• 所属期刊栏目: 研究报告
• 页码范围: 92-96
• 页数: 5页
• 语种: 中文

摘要

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

作者信息

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