棒材下料优化新算法及网格钢窗CAD.pdf

第 2 2卷 第 3期 2 0 0 3年 9 月 大 连 轻 工 业 学 院 学 报 J o u r n a l o f Da l i a n I n s t i t u t e o f Li g h t I n d u s t r y Vo l 2 2 No 3 Se p t 2 0 0 3 文章编号 1 0 0 5 4 0 1 4 2 0 0 3 0 3 0 2 0 6 0 5 棒材下料优化新算法及 网格钢窗 C AD 李 刚 韩 锋2 欧 宗瑛 王 小 东 1 大连 理工大 学 C A D C G研 究所 辽 宁 大连1 1 6 0 2 3 2 长 春轨道客 车股份 有 限公 司 工艺处 吉林 长 春1 3 0 0 6 2 关 键词 下料优化 序列线性规划 启发式算法 网格设计 摘 要 介绍了一种网格钢窗 C A D软件 其中关键技术是棒材的下料优化 虽然 这是一个老课题 研究者提 出过各 种算法 但是 效果还 不十分满 意 针对这类 问题 的特点 本 文提 出启 发式 序列 线 性优化算 法 此算法 与 目前 常用的 规整数 线性 规划 或遗传算 法相 比较 有 简化程 序 计 算速度 快 节材效 果好 的优 点 中图分类号 T H 1 2 2 T P 3 9 文献标识码 A No v e l a l g o r i t h m f o r o pt i m i z a t i o n o f o ne d i m e ns i o n a l c u t t i ng s t o c k p r o b l e m a nd s t e e l wi nd o w g r i d CAD LI Gan g HA N Fe n g OU Zo n g一 3 r i n g W ANG Xi a o do n g 1 CAD CG I n s t Da l i a n Un i v o f Te c h n o l Da l i a n 1 1 6 0 2 3 Ch i n a 2 Off i c e o f P r o c e s s i n g C h a n g c h u n R a i l w a y V e h i c l e s C o L t d J i l i n 1 3 0 0 6 2 C h i n a Ke y wo r ds c u t t i ng s t o c k o p t i mi z a t i on s e qu e nt i a l l i n e a r p r og r a mmi n g h e u ris t i c a l g o r i t h m gr i d de s i g n Ab s t r a c t Th i s p a p e r d e s c r i b e s t h e d e v e l o p me n t o f t he s o f t wa r e f 0 r s t e e l wi n d o w d C AD The k e y p o i n t o f whic h i s c u t t i n g s t o c k o pt i mi z a ti o n Th i s i s a l o ng s t a nd i ng p ro b l e m o f o n e d i me n s i o n a l o pti mi z a t i o n wi t h a s u b s t a n tia l b o d y o f p a p e r p u b l i s h e d Ye t n 髑 t o f t h e a l g o r i t h ms c u r r e n t l y i n u s e a r e n o t e f f e c t i v e e n o u g h B a s e d o n the b e s t fi r s t p ri n c i p l e a h e u ri s ti c alg o ri t h m o f s e q u e n t i al l i n e a r p r o g r a mmi ng i s p r o p o s e d Nu me ri c a l e x a mp l e s d e mo n s t r a t e t h a t i t i s a d v a n t a g e o u s i n s i mp l i f y i ng t h e p r o g r a m a n d e l e v a t i ng c o mp u t a t i o n s pee d s i g n i f i c a n t l y comp l t h t he con v e n t i o n a l me tho d s of i n t e g e r li n e a r p r o g r a mmi n g o r g e n e t i c alg o ri t h m 网格形式的产 品在建筑 装潢 机械等领域的 应用非常广泛 网格格 子的设计 要求布局均匀 美观合理 且构成 网格 的棒 材下料利用 率应 尽量 高 以降低成本 和增 强市场竞争力 在 大批 量生 产中 棒材下料 的优化更 是降低生产成本 的一个 重要环节 因此我们根据 网格产品设计 的特点 开发 了一套浴室网格钢窗 C AD系统 其中 关键技术是构成网格 的棒材下料优化 棒材下料优化 是优化设计 中最早 课题之一 经过 世世代代研究者 的努力 提出各种算法 还不能说 已经获得 了满意的解答 当前广为应用的是常规 整数线性 规划算法 或遗传算 法 等 但 这 些算法仍然有计算量 大 计算速 度慢 的缺点 因 此 本文提 出一种启发式 多级序列线性优化 的棒 收稿 日期 2 0 0 3 0 7 1 5 作者简介 李 刚 1 9 7 8 4 男 硕士研 究生 材下料优化新算法 本文先介绍网格钢窗 C AD系统 的组 成及其 应用 然后阐述启发式多级序列线性优化算法 并 通过算例与常用方法 比较 结果表明在保证优化 效果 的同时 可以使计算速度显著提高 1 网格钢 窗 C A D 参数 化模 型 网格钢窗 C AD采用参 数化设计 技术 参数 化设计 是指设计 对象 的拓扑 结构相似 可以通过 一 组参数来约束 尺寸关 系 由参数 尺寸 驱动获 得设计结果 通过参数驱 动机 制 可 以对 图形的 几何数据进行参数化修 改 但是在修改的同时 还 要满足图形的约束条件 需要约束 问关联性的驱 动手段来 约束联 动 维普资讯 第3 期 李 刚等 棒材下料优 化新算法及 网格钢 窗 C AD 2 0 7 1 1 常 见 网格 拓 扑 结构 矩 形 模 式 M 0 图 1 网格 拓 扑 结构 示 意 图 1 2表 征 网格 主 要 结构 的 特性 参 数 1 网格模式代码 M 常见 网格拓扑结构模 式为矩形和菱形 分 别用 代号 0和 1表示 2 网 格的高度 H 3 网格 的宽度 W 4 网格格子 的 水平间距 当 无 穷大 时 网格 演变 成单 一 垂直 网格 结构模式 5 网格 格子 的垂直 间 距 g 当 无穷大 时 网格 演变成单一水平 网格 结构模式 6 水 平方 向端 间隔 o 7 垂直方 向端 间隔 g 网格高度 H 和宽度 w 由设计任务给定 拓扑 模式 M 和间距 g w g h g wo g h o由设计者选定 1 3 端 间 隔 g w o 的确 定 在矩形模式即 M 0时 端间隔 o g h o 可 近似取等于 和 g 在菱形模式 即 M 1时 o g h o 可近似取为 和 g 的一半 以菱形模式水平方 向为例 端 间隔具 体确定 计算如图 2所示 菱形模 式 M 1 mo d为 求 余 计 算 Hn u m 为 网 格 格 子 同 隔 效 量 g x v 为 格 子 修正 间隔 当窗宽度 不是 g w 的整数倍 时 需对端 间隔做 调整修 正 图 2 菱形 网格端间隔计算框 图 1 4 网格棒材长度和数量计算 在模式代码 M 0时 网格棒材 的长度 为两 种 分别等于网格的长度和宽度 在模式代码 M 1 时 网格棒材长度需根据 网格结构布置几何关系 计算得到 例 菱形 网格 宽度为 9 0 c m 高度 为 6 0 c r n 横向间隔和纵 向间隔均为 1 0 c r n时 根据几何 计算需要 7种长度棒材 计算结果如表 1 所示 表 1 菱形 网格结算结果 棒材序号 1 2 3 4 5 6 7 长度 c m 8 4 8 0 7 7 7 0 6 3 6 0 4 9 4 0 3 5 3 0 2 1 2 0 7 0 0 数量 6 4 4 4 4 4 4 2 网格钢 窗 C AD 系统组成 出网格布局 系统包含 5个模块 即 人机界 面模块 几何 计算模块 结构设计模块 下料优化模块和打印输 出模块 见图 3 1 人机界面模块接受用户输入设计参数 显 示 网格布局 下料棒材长度等设计中间结果 2 几何计算模块根据 设计者输入 的设计参 数 M w H g w g 计算 出各种下 料棒材长度 及每种棒材的数量 3 结构设计模块负责完成网格结构设计 输 图 3 软件 系统工作流程图 维普资讯 大 连 轻 工 业 学 院 学 报 第2 2 卷 4 优化下 料模块应用本 文提 出的棒材下料 优化新算法 计算 出下料配置模式 5 打印输出模块负责预览和打印设计图纸和 生产图纸 用于实际生产 本文考虑到软件成本和 实用性 自主开发了一个打印输出模块 不需另外其 它 C A D软件支持 实现打印预览及控制打印输出 3 钢 窗 网格设 计过程和运 行 图例 设计者根据设计要求 输入钢 窗网格设计数 据 系统 即进行几何计算 求得下料棒材长度 数 量及 网格结构 结果在屏幕上显示 如 图 4所示 图中窗 口左侧上 方为数据输入 区 左侧下方列 出 待下料棒材长度及其需 要量 窗 口右侧显示 网格 结构及各种待下料棒材长度示意 图 图4 钢窗网格数据输入及下料棒材长度计算 若对几何计算结果满意 可进行结构设计 预 览及打印设计 图纸 然后进行棒材下料优化计算 如图 5所示 图 棒 材 下 料配 置 eH 口 i TH哪糕 t t牲口 强 砷 d 简 I l i 6 t O T 置 I 埘 l j l l j l 碰 卸 焉 神 溺璐曼 熬 洲 8 蚋 甄J i i 喊 i 图5棒材下料配置输 出 中窗 口左侧上方输入母 材长度 窗 口左 侧下方显 示计算得到的棒材下料优化配置方式类型和每种 类型的重复次数以及材料总利用率 设计者可根 据原材料供应情 况 选取 不同长度 的母材 进行 多 方案对比 窗 口右侧显示要查看的各种配置方式 的棒材下料示意 图 并可 由此输 出棒材下料 配置 生产图纸 指导下料切断操作 4 棒材下料启发式序列线性优化新算法 棒材下 料 优化 问题 是 一 个 L P L i n e a r P r o g r a mmi n g 问题 引 当前 解决 这类 L P问题 的方 法 主要 是 采 用 常 规线 性 整 数 规 划 优 化 求 解 方 法 4 1 常规线性整数规划优化求解方法及其存在问题 其基本思想 是通过穷举法列出所有可能的下 料方式 以所需原材料最少为优化 目标 以每种下 料方式 的重复次 数为优化变量 按整数线性 规划 原 理 求解 4 1 1 计算模型 给定 种长度 的待 下料 棒材 1 2 所需的数量分别为 b 1 b 2 b 母 材长度为 L 设有 z 种可能下料方式 每种 下料方式的重 复次数为 1 2 3 z 在方式 中 第 件待下料棒材的重 复次数为 口 从而建立数学模 型 目标 函数 mi n Z X1 X 2 X f al l Xl a1 2 X2 al X b l I 口 2 1 x 1 口 z z z z 口 z b z 约束条件 I 口 l 1 X 1 口 l 2 X 2 口 m z b m X1 X2 X 0 优化变量 l 2 均为非负整数 4 1 2 所有可能的下料方式的计算确定 在上述模型 中 所 有下料方 式的确定是决策 下料方案 的前提 如果所取 的下 料方式选择 了所 有可能下料方式 则 所求得 的最 优解就是严格全 局最 优 解 经 常 采 用 的 是 应 用 搜 索 树 s e a r c h t r e e 法 J 来求解所有可能的下料方式 设初始方式 每种 待下料棒材 的下料数 目分 别为 K1 K 一 K 则 K 1 L l 1 Ki L 一 K i 对 K 各项逐次减 1 经循环赋 值给 口 即可 得到全部 的下料方式 4 1 3 常规求解方法存在的问题 上述下料优化问题 数学模型是一个整数线性 规划问题 经典 的求解这 类问题 的方法 是采用 分枝定界法 但 在实用 中只适 于处理求解变量 数 目较少的情况 下料方式 z 较少 当待下料棒材 维普资讯 第3 期 李 刚等 棒材下料优化新算法及 网格钢 窗 C AD 2 0 9 种类 增大时 下料 方式 z 按 z 规律增大 计 算工作量也迅速增大 求解速度缓慢 难以在实用 中应用 最 近又 出现 了基 于遗传算 法 的求 解方 法 4 但其求解速度仍然较慢 为此 本文提 出 了一种 多级序列优化分次的新方法 4 2启发 式 多级序 列线 性优 化 方 法 基本思想 为缓解待下料棒 材种类增多及母 材有多种长度种类引起 的计算工作量迅速增大的 矛盾 本文提出一种新的求解方法 不需穷举 出所 有可能的下料方式 而是将 下料优化问题转化为 多级序列线性 优化 问题求 解 每级求解 时 在 当 前可行 的下料方式 中选择其 中最优的一种进行下 料 并尽可能多地重复使用此种下料方式 然后再 对剩余的待下料棒材又重新优化选取新的当前最 优的下料方式 不断重复上面操 作 直到所有剩余 待下料棒材数 目均减小至零 为止 4 2 1 当前最优下料方式计算模型 给定 种长度的待下料棒材 z 1 z 2 z 每 件待下料棒材所需 的数量分别为 D1 D2 D 母 材 长 度 为 L 设在最优一种下料方式 中 第 i 件待下料棒 材 的重复根数为 由此建立数学模型 目标 函数 ma x Z l ix l f l i x L 约 束 条 件 D i 1 2 z 0 优化变量 1 2 均为非负整数 这是一个整数线 性规划 问题 由于每次截 取的不同长度 待下料棒材种类 有限 所 以仍可用 分枝定界法求解 4 2 2 多级序列线性优化方法计算过程 将上述当前最优下料方式计算求解作为多级序 列线性优化计算的子程序 在每级求解 中重复调用 完整的求解过程如下 1 根据给定 条件调用 当前最 优下料计算子 程序求解 得到优 化值 z 组成 的 z 作 为第 一 级 下 料方 式 2 计算此种下料方式的重复次数 即此种下 料方 式所 需 母 材 L 的根 数 P D D 1 D 2 D 咖n 石 J 3 计算去掉 P根 后 余下 的每种待下 料棒 材 的根 数 D Di 一尸 A 4 将 D 作为新一级优化计算 的给定值 如 果所有的 D 都 已减小 至零 则优化计算 结束 否 则转步骤 1 重新调用当前最优下料方式计算子 程序 求得新一级的下料方式和重复次数 5 各级最优下 料方式及其重 复次数的集合 即为多级序列线性优化 的最终结果 算法流程图如图 4所示 图4启发式序列线性优化算法流程 图 4 3 新算法计算结果及对 比 为验算新算法 的有效性 本文进行 了下述两 组计算对 比 4 3 1 新算法与 常规线性整数规划 优化方法的 比较 例 1 需 下 长 4 6 3 c m 的 棒 材 1 0 0件 长 4 0 5 c m的棒材 2 0 0件 长 3 2 4 c m的棒材2 0 0件 长 2 5 6 c m 的 棒 材 2 0 0件 长 1 8 2 c m 的 棒 材 2 0 0件 母材长为 4 m 求最优下料方案 用前述常规线性 整数规划优化 方法求解 计 算结果如表 2所示 表 2 常规线性整数规 划优化方 法求解算例 1 计算结果表 总计需要母材 7 0条 材料的利用率9 9 8 9 计算利用时间 1 h 1 6 mi n 用本文提出的启发式多级序列线性优化方法 维普资讯 2 1 0 大 连 轻 工 业 学 院 学 报 第2 2 卷 求解 计算结果如表 3所示 表 3 启发式多级序列线性优化方法求解算例 1计 算结 果 表 总计需要母材 7 1条 材料利用率为9 8 4 9 计算利用时间 1 7 S 可见 与常规线 性整数规划优化方 法的方法 相比 启发式多级 序列线性优化方 法能 够大大节 省计算时间和数据 的存储 空间 并且节 材的效果 相 当 4 3 2 新算法与基于遗传算法的求解方法的比较 以文献 4 中提 到 的例 子 为 例 母 材 长 度 3 m 需下长 2 2 m 的棒材 3件 长 1 8 m 的棒材 3件 长 1 2 m的棒材 4件 长0 5 m的棒材 6件 长0 3 m的棒材 6件 用基于遗传算法 的求解方法计算 文献 4 中 的计算结果如表 4所示 表 4基于遗传 算法的求解方法求解 文献 算例 计 算结 果 表 用本文提 出的启发式多级序列线性优化方法 求解 计算结果如表 5所示 表 5 启发式 多级序列线性优化方法求解文献 算例 计 算结 果 表 下料方式 棒材类 型 下料根数 Pa t t e r n I Pa t t e r n 2 Pa t t e r n 3 Pa t t e r n 4 Pa t t e r n 5 Pa t t e r n 6 1 0 0 0 1 1 0 0 0 2 0 0 经对 比可 知 两种 方 法 都需 要 原 材料 8根 材 料的利用率相同 但采用 启发式多级 序列线性 优 化方法 计算 只需 1 S 文献 4 中的例子较简单 当需要的零件数增加时 由于基于遗 传算 法的求 解方法对 同一问题需要多次运行 从 多种 下料 方 案中择优 算法的计算速度将 比较缓慢 而采用本 文提出的新算 法 不但能保 证相 同的材料 的利用 率 而且计算速度有显著地提高 本 文 另对 1 0 0组 实 际 下 料 数 据 进 行 了 实 验 计算速度和下料 优化 效果理想 材料利用率均达 到 9 3 以上 5 结 论 网格钢窗设计可按其拓扑形式建立参数化模 型 采用参数化 C AD方法进行设计 本文提出的 启发式多级序列线性优化 新算法 将一维棒材下 料问题分解为多级序列线 性优化 问题 大大简化 了求解问题 的规模和复杂度 优化效果明显 参 考文献 1 S UL I MA N M A P a t t e rn g e n e r a t i n g p r o c e d u r e f o r t h e c u t t i n g s t ock p r o b l e m J I n t J P r o d u c t i o n E c o n o mi c s 20 01 74 2 93 301 2 刘 勇彪 等 截 面长 条 类材 料 下 料 方 案 的最 优 化设 计 J 机械设 计与制造 1 9 9 4 5 1 2 1 3 3 vA L E RI O d e C A R vA L HO J M E x a c t s o l u t i o n o f C U t t i n g s t oc k p r o b l