（机械制造及其自动化专业论文）多原材二维guillotine优化下料技术及应用系统研究.pdf

重庆大学硕士学位论文 ab s t r ac t abs tract r e s e r v e a n d o p t i m iz a t i o n o f m a t e r i a l i s a n im p o r ta n t p a rt o f s u s ta i n a b le d e v e l o p m e n t p r o j e c t , a l s o , t h e k e y c o n s t it u e n t o f g r e e n m a n u f a c t u re . c u tt in g s t o c k p r o b l e m ( c s p ) i s t h e re s e a r c h d i re c t io n t o s a v e a n d u s e m a t e r i a l p ro p e r ly . i t h a s v e ry im p o r t a n t p r a c t i c a l m e a n in g . a s k n o w n , t w o - d i m e n s i o n a l g u i l lo t in e c u tt in g s t o c k m e t h o d i s n p - h a r d , s o , i n a v e r a g e s it u a t io n , t h e re i s n o p o l y n o m i a l b o u n d a r i th m e t i c . t h e re f o r e , t h e p r a c t i c a l fr u i t i n e n g in e e r i n g p r a c t i c e i s f e w , t h o u g h t h e c o r r e s p o n d in g t h e o ry a n d a r it h m e t i c r e s e a r c h i s m a n y . n o w a f e w c o m p a n ie s p r o v i d e s o ft w a r e t o s o l v e c s p b as e d o n o n e k i n d m a t e r i a l , a n d mu l t i - m a t e r i a l c s p s o l u t i o n h a s n o t b e e n r e p o rt e d . t h i s p a p e r a im s a t c o m p u t e r - a i d e d m u lt i- m a t e r i a l t w o - d im e n s i o n a l g u i l l o t i n e c u tt in g s to c k t e c h n iq u e a n d i t s a p p l i c a t i o n , a n d r e s e a r c h e s i t s m o d e l i n g a n d s o l v in g a r it h m e t i c . t h e t y p ic a l a r ith m e t i c a re c o m p a re d a n d a n a ly z e d , a n d t h e i r p r a c t i c a l c h a r a c t e r i s t i c s in e n g in e e r in g a re re s e a r c h e d . b o t h t h e o ry v a lu e a n d p r a c ti c a l a p p li c a t io n c a p a b il it y a r e c o n s i d e r e d as p o s s i b l e . a m o d e l , w h i c h u s e m a t e r i a l c o s t as g o a l f u n c t i o n i s p re s e n t e d , a n d it s s u p e r i o r i t y t o m o d e l u s i n g m a t e r i a l u ti li z in g r a t e a r e p o in t e d o u t . i n o r d e r t o s o lv e l a r g e q u a n t it y m a t e r i a l c s p , a f e w n e w c s p m e t h o d s a re c o m p a r e d , a n d t h e s u p e r i o r it y o f c o l u m n c r e a t i n g m e t h o d a re p re s e n t e d . a ft e r d e e p a n a l y z i n g c o l u m n - c r e a ti n g m e t h o d , c o l u m n c re a t in g s o l v in g a r it h m e ti c fi tt i n g v a r io u s m a t e r ia l a r e g i v e n . a i m i n g a t t h e d i r e c ti o n d e m a n d o f c u tt in g s t o c k in f u rn i tu r e a n d a r c h it e c t u r e i n d u s t ry , t h e p r o p e rt i e s o f m a t e r i a l c l a s s a re re d e fi n e d . t h e n , t h e s p e c i a l c s p i s s o l v e d s u c c e s s f u l l y b y u s i n g a v e r a g e c s p m e t h o d . t h e s o l v i n g a r i t h me ti c o f t wo - d i me n s i o n a l mu l ti - ma t e r i a l g u i l l o t i n e cs p mo d e l a re re s e a r c h e d . a n d c o r r e s p o n d in g d y n a m ic e l i m in a ti o n o f c o m p u t e r 叩e r a t i o n e r r o r a n d s u b - o p t i m i z a ti o n h e u r i s ti c a r it h m e ti c a r e re s e a r c h e d . i n o r d e r t o a c h i e v e t h e a u t o m a ti c i m p l e m e n t a n d i n t e g r a ti o n t o o t h e r s y s t e m ( e x . q u o t in g s y s t e m a n d ma t e r ia l ma n a g e m e n t s y s t e m ) o f t h e s y s t e m , t h e p a p e r p re s e n t s a c o m p u t e r a i d e d c u tt i n g m e th o d t o g u a r a n t e e t h e u s e o f re d u n d a n t m a t e r i a l . f in a l ly , as e x t e n s i o n o f t w o - d i m e n s i o n a l c s p , t w o - d i m e n s i o n a l i r re g u l a r p a tt e rn c s p i s re s e a r c h e d . a n i r r e g u l a r p a tt e rn c s p m o d e l i s e s t a b l is h e d , a n d c o r r e s p o n d i n g p r a c ti c a l s o l v i n g a r it h m e ti c i s g i v e n o n th e s h o u ld e r o f p as t w o r k b y o t h e r s , m u lt i - m a t e r i a l b o a r d a n d b a r m a t e r i a l c s p s o ft w a r e a r e d e v e l o p e d u s i n g v c 6 众a c t u a l ly , t h e m o r e e ff e c t i v e 重庆大学硕士学位论文 u t i l iz i n g r a t e a n d fl e x i b il i ty o f m a t e r i a l u s i n g m a t e r i al c s p t h a n b y u s i n g s in g l e m a t e r i al c s p . k e y w o r d s : g u i l l o t i n e - c u t t i n g m u lt i - m a t e r i al k n a p s a c k p r o b l e m a re a c h i e v e d b y u s i n gmu l t i - c s p c u t t i n g s t o c k p r o b l e m 重庆大学硕士学位论文 1绪论 1绪 论 1 . 1 课万的 提出 及宜义 环境、资源、人口是当今人类社会面临的三大主要问题。环境问题 和资源、人口 两问题有着根本性的内 在联系。 特别是资源问 题，它不仅涉 及人类世界有限的资源如何利用，而且它又是产生环境问 题的主要根源。 于是， 近年来，一个新的概念己 经提出:最有效地利用资源和最低限度地 产生废弃物，是当前世界上环境问 题的治本之道。优化利用资源是我国经 济发展战略的重要内 容之一， 也是整个世界最重要的 研究课题之一。 一方面，节约原材料，优化利用资源是经济可持续发展战略的重要 内容之一，也是绿色制造研究的重要组成部分。另一方面， 在当今市场经 济条件下， 对某一 个企业而言，节约原材料， 提高原 材料利用率，降 低成 本，是该企业在市场经济竞争中取胜的必要条件。 制造业4 7 是将 制造资 源 ( 物料、能 源、 设 备工具、资 金、 技术、 信 息和人力等)， 通过制造过程转化为 可供人们使用和利用的工业品或生活 消费品的行业，制造系统就是一个输入制造资源 ( 原材料、能源等)，通 过制造过程输出产品或半成品的输入输出系统。制造业量大面广，对环境 的总体影响很大。可以说，制造业一方面是创造人类财富的支柱产业，但 同时又是当前环境污染的主要源头。制造系统中，制造资源 ( 简称资源) 的最优规划和利用是当前机械工程科学技术研究的前沿之一。制造资源的 优化利用问 题也是一个绿色制造问 题它不仅涉及到通过最优的方式 利用有限的资源，以使企业取得最大的经济效益，而且也是减少废弃资源 对环境污染的根本措施。 制造过程中物料特别是原材料的优化利用问题是指以尽可能高的物 料利用率和尽可能少的 物料损耗完成所要求的产品 任务。 物料的 优化利用 涉及面很广，涉及到从产品的设计、 制造、包装、运输、 使用到报废的 整 个 产品 生 命 周 期 的 各 个 方 面 。 二 维g u i l l o t i n e 切 割 优 化 下 料 10 1 1 11 就 是 一 个在产品设计、 制造和使用中 如何节约原材料、 优化利用资源的问 题。 在某些行业所需要的原材料中， 板材占 有相当的比重。 对板材的下料， g u i l l o t i n e切割 ( 也称二维边到边切割) 是广泛应用的一种下料方式， 适用于机械、 钢铁、 船舶、 车辆、建筑、 造纸、家具、玻璃、皮革等制造 业。以建筑装饰工程为例，近1 0 年来，我国建筑装饰工程得到飞速发展， 1 9 9 0 年装饰工程费用约为9 0 亿元，1 9 9 9 年上升到 1 6 0 0 亿元， 2 0 0 0年 达 2 0 0 0亿元。根据有关资 料估计，我国建筑装饰消费己占建筑工程造价 的 3 0 0/ ( - 4 0 %，是一个庞大的消费市场。其中就建筑装饰玻璃而言，从 5 0 重庆大学硕士学位论文 1绪论 年代开始， 我国 就己 生产钢化、 夹层玻璃。 改革开 放后， 我国引 进了 镀膜、 中空、 槽形、空心玻璃生产线。 到目 前为止， 绝大部分建筑装饰玻璃均可 生产， 平板玻璃产量占 世界第一， 建筑装饰玻璃生产能力约为 1 7 8 2 0万 - 1 8 8 2 0 万平方米。 对于大型原材料切割的单位， 在传统下料过程中，经常面临着原材料 的巨 大浪费;一批零部件板材下料后，我币 门 常常看到这样的结果:余料边 角大量堆积，给后续清理和环境污染制造了 很大麻烦。原因是传统的下料 方法存在弊端， 优化效率低。传统的下料方式主要有以下两种: 1 .单一下料法: 基本不考虑下料零件的相互混合下料问 题，而是按 每一种需要的板材零件大小规格和数量分别地独立下料，各自 下 够为止。 2 另 外一种叫做大到小边角料利用法。该方法的主要思想是将所需 的板材零件按照面积从大到小排序，然后从大到小依次下料，下 下一种零件板材时如果能利用前面的余料就首先利用余料来下 料。 单一下料法工人操作简单、容易记忆，因而容易推广， 但原材料利用率很 低，浪费很大; 大到小 边角料利用法比 上一 种利用率稍高， 但浪费仍然很 大，而且当零件种类较多时，工人操作困难。 通过上面分析，如果单靠人工凭经验完成下料工作，原材料利用率和 工作效率都很低。 随 着计算机的出 现， 计算机辅助完成下料工作就显得尤 为必要和重要了。自2 0 世纪6 0 年代， 人们就己 经开始二维优化下料方面 的理论和计算机算法的研究，目前己 有许多公司提供软件产品， 但是能进 入工程实用阶段的成果较少。实用中的单原材优化下料程序只有少数几 个，混合套裁的多原材优化下料程序目 前国内尚未见报道。而实用中混合 套裁能比单种规格原材料下料具有更高的材料利用率和更高的灵活性。下 面通过一个简单的算例加以说明: 例 1 .某工程需一批玻璃， 其大小和数量如下:( 单位: m m ) 1 ) 8 0 0 x 2 8 0 的玻璃 2 0 0 张;2 ) 6 0 0 x 2 8 0 的玻璃 1 1 0 张; 3 ) 6 0 0 x 3 5 0 的玻璃2 2 0 张。如果为单一原材料，原材料尺寸为1 0 0 0 x 2 0 0 0 ，问如何进行下料? 解:1 .如果采用单一下料法，则排样结果如表1 . 1 所示: 表1 . 1 巨亚不4 可福丽丽丽森丽 藕蔺丁丽藕 29一13-37 ，.1日1内匕 8 0 0 x 2 8 0 6 0 0 x 2 8 0 6 0 0 x 3 5 0 重庆大学硕士学位论文 绪论 共需原材料2 9 + 1 3 + 3 7二7 9 张; 原材料利用率6 9 . 2 9 % . 2 .如果采用 “ 从大到小边角利用法” ， 则排样结果如表1 . 2 所示: 裹 1 . 2 下料方 案编号 每种篡草 件所排的数量下料 张数 所得下料件的数量 1 )2 )3 )1 )2 )3 ) 17002 81 9 600 24211421 30633 602 1 61 0 8 4021102 1 合计6 62 0 0 2 2 01 1 0 共需原材料2 8 + 1 + 3 6 + 1=6 6 张;原材料利用率8 2 . 9 3 % 0 3 .用优化下料方法， 则得排样图如图1 . 1 所示; 这样采用优化下料方法只需要原材料6 0 张， 原材料利用率9 1 . 2 3 % e r一r一r一r一r一r一r一 1 r11 r1 r111 2 r2 r 1d 3 r3 r 1d 3 r3 r 1o 1 tt切 割方式 需1 0 0 0 x 2 0 0 0 的原 材料5 张2 9切割 方式需1 0 0 0 x 2 0 0 0 的原 材料5 5 张 图1 . 1单原材优化下料图例 由上可见，采用传统的人工下料方法原材料利用率很低，造成了原 材料的巨大浪费，而且由于人工排样本身费时、费力;易于出错，一 般工厂都安排专门的经验丰富的技师来下料，这就造成了 人力资源的 巨大浪费。采用了优化下料方法后，能大大增加原材料的利用率，而 且提高了 工作的效率，节约了人力。 但是在实际操作中， 人们经常遇 到这种情况，由于以前库存的原因或原材料市场供应丰富，使得现有 的原材料有多种选择。在这种情况下就给优化下料提出了新的要求， 即如何利用多种原材料而不是只靠一种原材料来下料，提高原材料的 利用率，这一定会比单一原材优化下料更为有效的节约原材料。 还是 以 例 1 . 1 为例， 假设此时不止有 1 0 0 0 x 2 0 0 0 这种规格的原材料，而且 还有一 种 8 0 0 x 1 5 0 0规格的 原材料， 假设两 种原材料的 单 位面 积价格 相等，则此时应该如何搭配使用两种原材料来下料使原材料费用最省， 选择多原材优化下料后其结果为: 需要 1 5 0 0 x 8 0 0的原材料 7张、需 要 1 0 0 0 x 2 0 0 0的 原材 料5 5 张， 排 样图 如图1 . 2 所示， 原 材料利 用率 9 2 . 4 7 % 0 重庆大学硕士学位论文 1绪论 1 r 11 r 1 1 r 1 1 r 1 1 r 2 r2 r 1 r 3 r3 r 1 r 3 r3 r 1 r 1 #切割方式需1 5 0 0 x 8 0 0 的 原材料7 张2 #切割 方式需1 0 0 0 x 2 0 0 0 的 原材1 ; 5 5 m c 图1 . 2多 原 材优化下 料图 例 由此可见，利用多种原材料优化组合来下料是比单一原材料下料有 更高的原材料利用率。 在当 今市场经济条件下， 各种板材供应规格多， 例 如市场上常用的 浮法玻 璃规格就有小片玻 璃 ( 尺寸: 长度 6 1 0 - 1 8 4 0 m m , 宽度 9 1 4 - 2 4 4 0 m m) 、中片玻璃 ( 尺寸:长度 1 5 2 5 - 3 0 5 0 m m ，宽度 2 6 0 0 - 3 6 6 0 m m ) 和大片玻璃 ( 尺寸: 长度 4 0 0 0 - 6 0 0 0 m m ，宽度 2 6 0 0 - 3 6 6 0 m m ) 三 个等级十几种规格。在市场经济和信息经济条件下对于特殊板材，更有厂 家提出了网 上定做的功能。 在这种形势下， 对于一个原材料加工厂家， 如 何把握机遇、充分发挥市场优势，灵活选用各种规格板材原材料，实现最 佳选取原材料以 节省费 用， 直接关系到企业效益的 好坏。 例如:就建筑装 饰玻璃而言，我国年生产能力约为 1 7 8 2 0万 1 8 8 2 0万平方米 ( 单价十几 到二十几j c j 平方米不等) ，如果将利用率提高一个百分点，就能节约上亿 元人民币。 发挥市场优势， 灵活选用各种规格板材原材料，实现最佳选取原材料 以节省费用这也就是二维混合套裁优化下料要解决的问题。因此研究二维 优化下料混合套裁模型及其应用具有重要意义。 1 . 2 优化下 料 技术的国内 外 研究 现 状 及 评述 优 化 下 料 技 术 的 研 究 理 论 涉 及 到 线 性 规 划( l p ) (3 0 3 41 、 动 态 规 划 4 3 7 11 启发式算法 ( s h p ) 168 1- 73 1 以 及人工智能 ( a i ) 4 4 (4 51等多 种学术研究前沿理 论， 而且鉴于 优化下料其固 有的复杂性和多 样性， 对于学术的 深层发展和 繁荣，具有一定的推动意义.而且由于优化下料技术具有经济效益 ( 节约 成本) 和社会效益 ( 可持续发展、 绿色制造)明 显等特点， 使得很多国内 外学者投入到优化下料的技术研究中来。 一 般二维下料常用切割形式可以 分为以 下几种: 直角 切割: 矩形零 件板 材的 边必须和原 材料平 行 ( 图1 .3 ) w 2 ) , ， ( 玩 ，从) ， 每 种原 材 对 应的 价 格 记为y c i , y c 2 , ， y c k e 待下的m种 零 件的 长、 宽 分 别记 为 ( 1 w , ) . ( 1 2 1w 2 ) 1 ， ( 1 m ,w m ) ， 每 种 零 件的 需 求量 分 别 为b , , b 2 , ， b m 。 问 题 转 化 为 在以 上 条 件 下， 求如 何 下料使所用原材料的总成本最小?可用如下的数学模型来描述: 重 庆 大 学 硕 士 学 位 论 文 2 多 原 材 二 维 g u illo t吮选 业 一壁 遨丝鲤旦矍遨壑堕 x n k m i n 艺 卜 又 t卢 y c 订 声 j k x 飞 9 . 士 。 艺 q (k .z ) _ b . a . 1 j = 1 i =1 2 , v j 。 l , =1 , 2 ,. ， 尤 一， p) ? 0i， 且 为 整 数 ， 其中: z c- 最小成本 ( 目 标函数) ; y c ,一 一 第k 种 原 材 料的 价 格; k -原材料的种数; 砂 一 一在 第k 种 原 材 料 上 下 料 的 第j 种 下 料 方 式 的 使 用 次 数 ， 即 用 第j 种下料方式切割第k 种原材料的张数。 n 、 一一 第k 种原材所选用的下料方式总数; b 第i 种 待 下 零 件的 需 求量; 可， 一 第 k 种 原 材 对 应 的 第 j 种 下 料 方 式 下 第 i 种 零 件 的 数 量 ; 该下料数学模型是典型的 整数线性规划模型，目 标函 数 z c记录下料过程 原 材料的 成本。 约束条件既规定了 待下料零件在原 材料上的合理排样又满 足了待下料零件的数量要求。 在 该 模 型 中 ， 由 所 有 a 岁 项 组 成 切 割 矩 阵 a ， 其 中 每 一 列 a 份 都 代 表 了 一 种 可 行 的 切 割 方 式 和 相 应 的 原 材 料 ， 所 以 a 岁 的 值 不 是 随 意 的 ， 而 是 受 下 料 排 样 的 实 际 所 制 约 ， 而 a (k ) 的 生 成 方 法 也 是 优 化 下 料 问 题 中 的 一 个 关键技术列生成法。 在后面详细讨论中会述及。 该下料数学模型是典型的整数线性规划模型，目 标函数z c记录下料 过程原材料的 成本。 约束条件既规定了 待下料零件在原材料上的合理排样 又满足了待下料零件的数量要求。 2 . 2 橄型的 优点 原材料成本最小利用一种或多种规格原材料完成给定的下料任 务，且使原 材料成本最小。 这样就避免了 因为只考虑了 原材料总体利用率 而忽略了 原材料成本的问 题， 适合实际 运用中的多 种规格原材料混合套裁 问题。比只单纯的强调材料利用率具有优越性，而且在下面的论述中洲门 会看到，本模型实际上包含了以 利用率最高为目 标函数的设计模型，因而 就具有更广的实用范围。 重 庆 大 学 硕 士 学 位 论 文 2 多 原 材 二 维 g u illo tin e 优 化 下 料 数 学 模 型 和 差 键 越 鑫 哑 窒 例如某工程利用 两种 规格分别为1 : 2 0 0 0 m m x 1 5 0 0 m m和ii : 2000m x 1 2 0 0 m n 的原材料， 完成如下的下料任务1 : 1 4 5 0 m m x 6 5 0 m m x 5 0 件、 2 : 9 0 0 m m x 6 5 0 m m x 5 0件、 3 : 5 0 0 t n m x 3 0 0 m m x 1 0 0件。已 知原材料 价格分别为3 0 0 0 元/ 张和2 0 0 0 元/ 张。原材料以及零件图形如下图2 . 1 : 2 困 图2 . 1原材料和下料板材示意图 方案一、以 材料利用率最高进行下料，得如下的下料方案 ( 图2 . 2 ) : 1 i 1 i 1 i 1 6 张1 5 张i1 张 日 322 3 3 33 3 3 33 22 2 一 3 3 1 3 3 i i 1 1 张 i1 张 图2 . 2以 利用率为目 标的结果 共计用去原材料1 2 3 张、原材料1 1 1 1 张; 材料利用率9 5 .7 8 %; 材料 花费9 1 0 0 0 元q 方案二、以 材料费 用最少进行下 料， 得如下的下料方案 ( 图2 . 3 ) : 共计用去原材料1 1 6 张、原材料1 1 2 0 张; 材料利用率9 5 . 1 8 % ;材 料花费8 8 0 0 0 元0 通过以上的比 较可以 看出，尽管方案一的材料利用率比方案二的提 高了0 .6个百分点， 但材料的费用却多了3 0 0 0元， 对于实际工程操作而 言，方案一是不可取的。 重 庆大学 硕士 学位论 文2 多 原 材二 维g u i l l o t i n e 优化 下 料数学 模型和 关键技术 研究 1 22 33 3 3 1 1 5 张11 张 22 2 一 3 3 3 3 3 国 国 3 3 3 1 1 1 6 张 1 1 4 张 图2 . 3以材料费用为目 标的结果 2 . 3涉及关镇技术 2 . 3 . 1 板 条 类 的 构 造 和 板 条 启 发 式 算 法 对于优化下料的研究，最先是一维优化下料条材优化。条材优化 的 求解过程是一维背包运算， 相对简单， 求解算法较成熟。 在解决二维优 化下料问 题时，引入了 板条的概念，从而将二维优化 下料近 似为一维 优 化下料问 题。 例如有如 右图2 .4 所示下料 板材 ( 或称为 零 件) :长为1 ，宽为w。 将n ( n _ 1 ) 个此零 件沿零件长方向 依次 排列 得到如图2 .5 所示 1 图 2 .4下料板材示意 n 个 n 个 图2 . 5沿零件长生成板条 图2 石沿零件宽生成板条 重 庆 大 学 硕 士 学 位 论 文 2 多 原 材 二 维 g u illo tin e 优 化 下 料 参 学 摸 型 丛鲤丝塑堕 板 条 ( s tr ip ) 。 也 可以 将n ( n _ 1 ) 个 此 零 件 沿 零 件 宽 方向 依次 排 列 得 到 如 图2 .6所示板条。n 二 1 时， 是一种特殊板条即是原零件本身，因此板条 仍具有零件本身的 属性， 有长宽两个方向的 尺寸要求，与条材零件有本质 的区别。 我们有如下定义: 定 义1 板条区 别 于条材在于 板 材在两个垂 直方向 上都有长 度要 求， 如果能 把零件成组看待， 使得零件组在一个方向 上的长度近似于待排样的 大矩形的某一个方向的长度，而使零件组的另一个方向在大矩形的另一个 方向上 套裁，那么， 板材也就成为“ 条材” ， 这种零件组就成为 板条， 这 就是引入板条的原始思想。随着面向 对象编程思想的推广，发现用可以 变 化长度的 板条能 增加板条柔性， 提高优化效率。因 此本文所提出的板条不 仅仅是简单的零件组， 还包含了一系列的操作运算。 定义2零 件的 剩余需求量零件的 需求量减去零件已 排样的数量所 得的剩余量。 按照定义1 ， 我们可以 构造任何零件基于任何原材料的板条。对于多 原材二维优化下料而言， 我们要处理的 是在每一种原材料上的 优化排样， 需要构造基于每一种原材料的全部零件的 板条对象。然后借助于板条启发 式算法进行二维背包问题 ( t d k p )的求解计算。 定义3板条启发式算法由于t d k p 是一个n p 一 完备问 题，一般情 况下，最优解的求解十分困 难，计算开销大，而生产实际中又迫切需要给 出这种问题的解决方案，为此，借鉴于一维条材的处理方法我们给出一种 板条启发式方法， 该方 法把二维问 题降为 一维问 题来处理， 算法简单、 节 约内存、计算高效， 适用于处理实际问 题，尽管这种方法得到的可能不是 最优解，但可得出该问 题的近似解 ( 逼近解) 。 多原材二维优化下料的板条启发式算法分三阶段完成: ( 1 ) 对 于 每 一 种 下 料 零 件( 心 ， w i ) j s i m ， 用 面 向 对 象 的 方 法 构 造 基 于 每一 种 原 材 料 ( 乌 ， 巩) i p , k 的 候 选 板 条 类 对 象 ( 变量) ; ( 2 )通过求解一维背包问 题确定 选用原材料和候选板条在该原材料 上的排样; ( 3 )剩余面积的处理: 把剩余面积处理成若干个子矩形， 与( 1 ) 、 ( 2 ) 的处理类似，先生成基于子矩形的候选板条，然后通过求解背 包问题确定板条在子矩形内的排样。 2 . 3 .1 .1 板 条类 的 构造 重 庆 大 学 硕 士 学 位 论 文 2 多 原 材 二 维 g u illo tin e 休 些 王 空 遨兰鲤壑丝遨塑丝 2 . 3 . 1 . 1 . 1 板条 类 的 结 构 前面论述了板条的引入意义和板条定义，在多原材优化下料情况下， 板条具有如下的特征: . 板条类具有长、宽两个方向的尺寸要求; . 板条类的实例记录了 相应的原 材料编号和下料零件编号和所含下料零 件数量; . 板条类在整体结构不变情况下具有对所含相应下料零件数量在一定范 围内增减的能力，以 提高板条柔性; . 板条类应该记录剩余面积的信息，以 方便剩余面积处理; . 板条类应该记录下料零件在相应原材料上的排样类型。 在板条类的对象定义的成员 变量为: .1板条长; 板条宽; 板条所含零件的最大数 表2 . 1 : v r l 余料长; 刀 a g 板条所含零件数; 板条价值; 原材料沿板条长方向上的 下料零件在相应原材料上 的排样类型; 在板条类的对象定义的方法为: . c o n s t ru c t根据指定原材料和下 料零件构造板条类的新实例; . a d d在整体结构不变情况 下所含相应下料零件数量增加; . s u b t r a c t在整体结 构不变 情况 下所含相应下料零件数量减少: 表2 . 1 描绘了板条类。 c l a s s s t ri p p ri v a t e o b j e c t 1 o b j e c t w o b j e c t m a x n o b j e c t n o b j e c t v o b j e c t r l o b j e c t f la g p u b l i c me t h o d c o n s t r u c t me t h o d a d d me t h o d s u b t r a c t 板条类对应的原材料编号 和下料零件 编号在实现中 通过易于循环处理的二 维数组进行标志;下料零件在相应原材料上的排样类型共有四种，见下一 节的详细描述。 2 . 3 . 1 . 1 . 2 若于 第i 种原 材 料 ( 人 ，班) 的 候 选 板条的 生 成 重 庆 大 学 硕 士 学 位 论 文 2 多 原 材 二 维 g u illo tin e 优 化 下 料 数 学 模 型 塑 塑些些丝 设 原 材 料 矩 形 集 为g = ( lw , ) , ( l 2 , 叱) , . . . ， ( j ,k , w k ) ， 对 任一 第 i ( i e 1 , k )种 原 材 料 矩 形 为 ( l , , w) 。 设 待 排 下 料 零 件矩 形 集为 r = w , i w i ) , ( 1 2 , w 2 ) , . . . ， ( 1 aw e , ) ) ， 任 选 其 中第 l ( 1 e 1 , m )种下料零件 忆 , w 1) . 选中 原 材 料i 和下 料零 件i 如 右图 2 . 长、 宽， 工 . 7所示。则基于原材料矩形的 可以生成以 下四种类型的板条。 s t r i p 1 w类型:原材料长与下料 图 2 . 7 零件宽同向并且沿原材料长方向 排列下料零件， 原材料和下料零件示意图 如图2 . 8 所示。 s t r i p 1 1 类型: 原 材料长与 下料零件长同向 并且沿原 材料长方向 排列下料零件，如图2 . 9 所示。 w .1j 卜- . 1 .z iw i i 蛾w , 耳立 气 图2 . 8 s t r i p 1 w 卜w 4 l ; 类型板条示意图 图2 . 9 s t r i p 1 1 类型板条示意图 自 网阮卜| 不|.i|业 峨 一| 了!|j 土 厌 l i l i 图2 . 1 0 s t r i p es w w 类型 板条示意图 图2 . 1 1 s t r i p we w 1 类型 板条 示意图 i i i . s t r i p - w w类型: 原 材料宽与 下 料零 件宽同向 并且沿原 材料宽方向 排列下料零件，如图2 . 1 0 所示。 i v . s t r i p - w 1 类型: 原材料宽与 下 料零件长同向 并且沿原材料宽 方向 排列下料零件， 如图2 . 1 1 所示。 对于 板条s t r i p 1 w和s t ri p es i l 都 是 沿 原 材 料的 长 度方向 生 成， 并 且 板 条的长和原材料的长度同向， 通常 称这两种板条为水平候选板条。 相应地 称沿原材料的宽度方向生成，并且板条的长和原材料的宽度同向的板条 s t ri p y w w 和s t r i p - w 为 垂 直候选板条。 重 庆大学硕士 学位论 文2 多 原 材二维g ui l lo t in e 优化下 料数学 模型 和关键技术 研究 我 们以s t r i p 1 w 类型板条 对象的 构造为 例详细讨 论板条对象的 构造 过程， 其他类型板条对象的 构造与此相似。对于任意选中的原材料i 和下 料零 件j ， 其s t r i p _ 1 w 类型 板条s tr ip _ iw ij 6 对 象构造图 形， 如右下图2 . 1 2 所示。其成员变量在初始构造函数 ， 止 习 件 c o n s t r u c t 中定义如下: s tr ip ! - 1 ,1 6 1 二= m in ( b ,， in t ( l f w ) ) 不 . w 生 卜 一 -一 1,i i 斌 妇 个 l ; 图2 . 1 2 s t r i p l w i j 对象构造 strlp-strlp-恤业strip-strip- 另外方法 ( 函数) a d d 和s u b t r a c t 是 改 变 所 含 相 应 下 料 零 件 数 量n( 改 动 的 有 效 范围 是 【 0 ， m a c 川 ) ， 而 不 是 最大数量m a x n ，相应板条长. 1 和余料长r l 也要改变。 2 .3 .1 .1 .3 特殊怕况处理 当 给定的 原材料i 和下料零件j 在某 种类型的 排样上所得板条含下料 零件的 最大数量. m a x n为零时， 此时该 板条不存在， 在实际程序处理中， 该排样类型的分支被去除。引 起.m a x n为零有三种情况， 其一是在类型的 排样的 某一方向 上原材料的 尺寸小于下 料零件的尺寸，即所谓的排不下的 情 况 ; 其 二 是 当 该 下 料 零 件己 经 排 完 ， 此 时b j = 0 ; 最 后 一 种 情 况 是 下 料 零件对原材料有纹理要求， 从而限制了 排样类型。 前两种情况由 板条类构造过程实现， 后一种情况适用于用户对下料 零件有纹理 ( 方向) 要求的情况，如对于有木纹方向 要求的家具开板，当 原材料纹理沿原材料的长度方向而且要求下料零件的纹理与原材料纹理相 同 时 ， 就 必 须 使s tr ip ix和s tr ip w 1 排 样 的。成 员 变 量 为 零。 这 种 操 作 简便的 方法是实 现有方向 性要 求材料下 料的 基础。 定 义 4原 材 料 有效 对于 某 种原 材料i 和下 料 零 件i ， 在 初始 化构 造函数中，如果对所有类型的排样都有.m a x n为零，则称原材料i 对下料 零 件j 无效， 即 不能 选择利 用原 材料i 来 对零 件j 下料; 否 则 称原材 料i 对 下 料零件1 有效。 如果 某原 材料i 对下料 零件 集合r 中 的 任意零 件都 有效， 则称原材料i 为全效原材料; 相应地称对下料零件集合r中的部分零件有 效的原 材料为有效原 材料; 对于少量那些 对下料零件集合r 中的任意零件 均无效的 原材料为无效原材料或零效原材料. 2 . 3 .1 . 2 板条启发式算 法 重 庆 大 学 硕 士 学 位 论 文 2 多 原 材 二 维g u i llo tin e 优 化 下 料 数 学 模 型 和 关 键 技 术 研 塞 2 . 3 . 1 . 2 . 1 板 条 在 选中 原 材 料 拒 州 止的 排 布 在上一节我们生成了 一定数量的水平和垂直候选板条， 类似于条材 的 套裁， 对 应 地 我 们 将 水 平 板 条 沿 选中 原 材料 矩 形( lw , ) 的 宽 度 方向 套 裁， 垂 直 板 条 沿 选中 原 材 料 矩 形( l , w , ) 的 长 度 方向 套 裁， 则 可以 得 到 二 维背包问 题的一 个近似排样，由 板条的生成规则知， 这种近似排样是满足 g u i l l o t in e切割条件的。另外考虑到由 于这是一个近似排样一般情况下这 些板条不会把整个原材料矩形都填满，即在板条排样后还存在余量。在这 些剩余面积中， 有可能适合再排各种零件，所以我们把二维背包问 题的求 解过程近似转化为: v (t d k p ) 、 m a x 扣 “ 二 ，(p i) + v s ( s l) , v - ( p 2 ) + v s (s 2 ) 其中: 问 题p 1 为w n o r ) ( p 1 ) = m a x 艺v iy , y- .n , y , 、 w , y ,。 且为整数 0 y i b ，i 二 1 , 2 , . . . , m 产|烈|it 玩是零件 i 在原材料 s中能排板条的最大数量 b y ( b . = i n t ( b , 1 .n ) 。 问 题s 1 即 为 在处 理问 题p 1 ( 即 获 得水平板条 在原 材料 矩形的 最优排 样) 后，在剩余面积的处理问 题。 问 题 p 2 为v (- ) ( p 2 ) = m a x 艺v i y , 万 w y : l , y , _ 0 且为整数 0 y , 瓦 ， ，i = 1 ,2 , . . . , m j|别!1 重 庆 大 学 硕 士 学 位 论 文 2 多 原 材 二 维 g u illo tin e 优 化 下 料 夔 学 鲤些差 丝 垫鲤丛 问 题p 2即为求解垂直板条沿原 材料矩形长度方向 的最优套裁方式:与问 题s 1 类似，问 题s 2 为处理问 题p 2( 即获得垂直板条在原材料矩形的最 优排样)后的余料处理问题。 问 题p 1 . p 2为典型的一维背包问题， 其求解方法后面第3 章介绍，二维 背包的近似求解即为选取两 种板条处理方式中 价值最大的排样方式。 下面 主要阐 述剩余面积的 处理方法， 对 s 1 . s 2 处理方法相同， 故下面的 说明 对s 1 . s 2 不加以区分。 2 . 3 . 1 . 2 . 2 翻杂 面 积的 处 理 方法 和 胡创 舰的 确定 在优化下料过程中，难免会有余料产生，一般工程规模越大余料也越 多， 若不及时将余料入库保存， 就会造成原材料的 丢失浪费。为了 在下料 过程中 加入余料管理功能， 将最终余料进行入库，首先要确定切割线的 位 置，统计相应的余料。 2 . 3 . 1 . 2 . 2 . 1 传统俐 余面积的 处理方法 由 于以为参考的矩形生成候选板条的排样不一定正好等于原材料矩形 的长或宽，如右图2 . 1 3 所示， 在求解问题 p 1 , p 2后， 在原 材料矩形的长或宽方向会产生 余料，这些余料可以 划分为若 干个子矩形区域，若这些子矩 形满足一定的长、宽条件，则 仍可以继续下各种零件。因 此 ， 我 们 把 这 些 余 料 区 域 划 分图 2 . 1 3 剩 余 面 积 示 意 图 为若干个子矩形， 作为子问题 来处理。 以 垂直板条为例，在第二阶段求解背包问 题