面向纸制品包装材料加工企业的优化下料问题研究

面向纸制品包装材料加工企业的优化下料问题研究 摘 要 切割下料问题广泛存在生产制造企业中,其工业应用领域非常广阔,本文以 面向纸制品包装材料加工企业的优化下料问题为研究对象,开展纸卷下料的应用 研究。 本文首先介绍了课题的研究目标、课题来源和行业背景,概括了本课题的研 究内容和理论基础。以一家大型纸制品包装材料加工企业的实际生产作为本文的 应用研究背景,针对企业面临的下料困难提出总体解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 和实施步骤,首先从 改进原纸的下料规格出发,优化下料规格使之更符合实际生产的要求。继而根据 纸制品包装材料的生产特点和具体切割工艺要求,研究纸制品包装材料加工企业 的优化下料模型,建立多种原纸规格的数学模型,结合公司实际生产数据求解昀 优下料方案并进行结果分析。 通过研究纸制品包装材料加工企业的切割下料问题,运用科学的方法为企业 提出优化下料策略,寻找昀优的下料方案, 改进下料效果,达到改善企业的 生产 管理、提高竞争力和增强应变能力的目的。 关键词:纸制品包装,切割下料问题,组合优化 - I - I Abstract Cutting Stock Problem CSP is one of the most widely studied problems in the applied research. It exists in a variety of industries and enjoys great popularity of researchers to a large extend. In this thesis, an applied research of the cutting stock problem in the paper packing industry is conducted so that an improvement of material utilization could be achieved The aim of the research and the background information of the paper packing industry are presented in the first part. Then a study review on cutting stocking problem is described in detailIn the main part of the thesis, the author conducts a complete study on the CSP in a paper packing company. In order to solve the difficulties of CSP in the company, an optimal approach is concreted in two steps: Firstly, an optimization research of the stock sizes is given after product study and analysis. Secondly, a mathematical model of CSP with multi stock sizes is specifically developed basing on the company’s producing and cutting specification. Then two stereotypes of CSP in the paper packing company are solved and the optimization cutting patterns are found. The optimal method is proved feasible and effectiveAt last, an overall review of this research is given, pointing out the trends of CSP study Keywords: Paper Packing Industry, Cutting Stock Problem, Optimization - II - II 目 录 摘 要.I ABSTRACT.II 第 1 章 绪论.1 1.1 研究目标和选题意义..1 1.2 课题来源和研究内容..1 1.2.1 课题来源.1 1.2.2 研究内容.2 1.3 研究路线.3 第 2 章 优化下料问题概述.4 2.1 优化下料问题的应用领域4 2.2 优化下料问题的分类..5 2.3 本文研究的行业背景..6 2.3.1 优化下料问题与包装行业的关系6 2.3.2 包装材料加工行业面临的下料困难..7 2.4 本章小结.9 第 3 章 优化下料问题的研究综述10 3.1 优化下料问题的研究现状.10 3.1.1 优化下料问题的分类描述.10 3.1.2 优化下料问题的研究方法.12 3.2 二维排样问题的研究现状.14 3.2.1 二维排样问题的分类14 3.2.2 二维矩形排样的分类15 3.2.3 矩形件优化排样问题的研究综述.16 3.3 本章小结..19 第 4 章 应用研究背景与整体对策20 4.1 公司概况..20 4.2 公司面临的下料困难21 4.2.1 产品种类繁多,原纸品种和规格复杂..21 4.2.2 原纸进口比例高,订购时间长..22 4.3 解决下料困难的整体对策.22 4.3.1 产品分析与归类..23 4.3.2 优化原纸规格,提高原材料的利用效率.29 4.3.3 确定昀优下料方案..33 - III - III 4.4 本章小结..33 第 5 章 纸制品包装材料企业的下料模型研究..34 5.1 纸制品包装材料加工行业的现状和加工特点..34 5.2 纸卷优化下料问题的提出.36 5.3 纸卷的下料特点与工艺要求37 5.4 纸制品包装材料加工的优化下料技术..41 5.4.1 优化下料的设计思想41 5.4.2 基于多种原纸宽度规格的条带生成42 5.5 面向纸制品包装材料加工的下料模型..44 5.5.1 建立多种原纸宽度规格的下料数学模型.44 5.5.2 数学模型适用性分析46 5.5.3 切割方式的调整..47 5.6 计算实例..47 5.6.1 实例一48 5.6.2 实例二50 5.6.3 结果分析..52 5.7 本章小结..53 第 6 章 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 与展望54 注 释56 参考文献.58 发表 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 清单62 致 谢63 - IV - IV 图表目录 表2-1:优化下料问题的应用领域4 表2-2: 包装行业的切割类型和应用举例7 表4-1:产品产量和品种数量情况表23 表4-2:产品种类与原纸品种的关系表.29 表4-3:375G类的原纸规格改进方案..30 表4-4:325G类产品的原纸改进方案..30 表4-5:250G类产品的原纸改进方案..31 表4-6:270G类产品的原纸改进方案..32 表4-7:低克重产品的原纸改进方案32 表5-1:原纸克重与边损量关系.38 表5-2:按经验给出的若干下料方式45 表5-3:第一组产品数据.48 表5-4:第一组原纸数据.49 表5-5:第一组产品生成的条带数据49 表5-6:实例一的优化方案..49 表5-7:第二组产品数据.50 表5-8:第二组原纸数据.50 表5-9:第二组产品生成的条带数据51 表5-10:实例二在没有库存限制条件下的优化方案..51 表5-11:实例二在库存限制条件下的优化方案52 图1-1:本文的研究路线..3 图2-1:平面套材问题的分类.6 图3-1:卷材切割.16 图3-2:直通切割16 图3-3:正交切割.16 图4-1:产品分类图..24 图4-2:375G类产品的产量分布情况..25 图4-3:325G类产品的产量分布情况..25 图4-4:250G类产品的产量分布情况..26 图4-5:270G类产品的产量分布情况..26 图4-6:75G SD类产品的产量分布情况27 图4-7:75G KT类产品的产量分布情况27 图4-8:97G类产品的产量分布情况28 图4-9:102G类产品的产量分布情况..28 图4-10:157G类产品的产量分布情况.29 图5-1:两种切割样式38 图5-2:两种排放方式39 图5-3:连续排放方式42 - V - V暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 第 1 章 绪论 1.1 研究目标和选题意义 在生产实践中,许多制造行业经常遇到切割下料问题(Cutting Stock Problem,简称CSP),通常是指在一组给定的原材料上,尽可能多地排放需要的 1 零件或产品,使得原材料的耗用量昀低或者利用率昀大,以减少废料。 工业和 建筑业的许多原材料,例如圆钢、圆木、钢筋、铁板、薄铁皮、塑料板以及纸张、 布匹等,一般都存在下料或排样的问题。它是针对如何使切割对象在有限的空间 中昀有效地利用空间布局而衍生出来的问题, 也就是将待切割对象摆放在一定规 格的大件原料表面上进行套材切割,目的使原料损耗率昀低。 加工制造过程中的 优化下料问题是制造系统资源优化利用问题之一,一个好的下料计算方法和下料 方案,可以提高原材料的使用率、降低生产成本,从而提高产品的市场竞争力。 原材料成本高、下料效果差已经成为制约纸制品包装材料加工行业发展的瓶 颈之一。为此,本文拟在一家大型纸制品包装材料加工企业进行应用研究,针对 该企业面临的下料困难,提出整体对策方案,然后基于纸制品包装材料加工行业 的现状和生产特点,结合加工工艺的要求和其他限制条件,采用优化下料技术为 同类企业研究优化下料的数学模型并求解昀优下料方案, 以达到提高原材料利用 率、指导生产的目的。 1.2 课题来源和研究内容 1.2.1 课题来源 本文以一家生产烟草包装材料为主的大型纸制品包装企业为研究背景,近 年,随着烟草行业的繁荣,公司的生产规模得到很大的提高,产品品种和业务种 类向多元化发展。随着市场竞争加剧以及公司进行组织变革,生产管理方面的问 题逐渐凸显,公司领导越来越意识到原材料成本高、下料困难是制约公司发 展的 瓶颈之一。因此,在公司领导的大力支持和帮助下,本文作者有幸到企业进行实 - 1 - 1暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 习调研并开展优化下料问题的研究。通过熟悉生产流程总结归纳出实际的切割工 艺要求和下料限制条件,分析企业的产品生产和原材料的需求状况,为企业改进 下料决策,寻找有效求解昀优下料方案的方法。 1.2.2 研究内容 本文运用定性和定量方法,结合纸制品包装材料加工企业的切割工艺要求 和生产限制条件,进行纸卷优化下料问题的应用研究,为企业提供改善经营的方 法和途径,主要完成以下内容: (1) 第一章:概括本课题的选题意义和研究目标,简述本课题的来源、 研究内容和研究路线。 (2) 第二章:概述优化下料问题、应用领域和分类,介绍优化下料问题 与包装材料加工行业的关系及应用情况,总结该行业在下料管理方面存在的问题 和制约因素。 (3) 第三章:详细综述优化下料问题的理论研究,重点概述二维矩形排 样问题的研究现状,为本课题开展应用研究提供必要的理论基础,运用有关知识 解决纸卷切割下料的问题。 (4) 第四章:以一家大型纸制品包装材料加工企业为背景开展应用研究, 针对企业的下料困难提出整体对策,从两个层次解决应用中的下料问题。首先, 选择合适的下料原料规格;其次,寻找昀佳的下料方案。 (5) 第五章:论述纸制品包装材料加工的生产特点,在满足实际切割工 艺要求的前提下为同类企业研究优化下料模型,建立多种原纸宽度规格的数学模 型,运用线性规划求解,以公司的实际数据为求解实例并分析结果。 (6) 第六章:对本研究进行总结和展望,指出本研究的不足之处和后续 研究工作的方向。- 2 - 2暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 1.3 研究路线 本文的研究思路是以一家大型纸制品包装材料加工企业为背景进行应用研 究,针对企业面临的下料困难提出整体对策:首先分析公司的产品生产情况,改 进原材料下料规格,使之更适于生产;其次基于同尺寸产品的大规模优化排样研 究的基础上,为纸制品包装材料加工行业的切割下料问题提出优化下料技术,研 究多种原纸宽度规格的数学模型,运用线性规划求解纸卷下料的实际应用问 题, 用理论指导实践生产。论述企业具体的 优化下料问题的概述和 下料问题和限制 分类 条件开展面向纸制品 提出解决下料问 课题的行业 包装材料加工企 背景 题的整体对策和业的应用研究 实施步骤优化下料的 建立纸卷下研究综述 料的数学模 型并求解 目标:解决优化下料问题, 改 善纸卷的下料效果图 1-1:本文的研究路线 Figure 1-1: The Research Route of This Thesis - 3 - 3暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问 题研究 第 2 章 优化下料问题概述 2.1 优化下料问题的应用领域 在工业应用领域上,优化下料问题有多种提法,例如切割问题(Trim Loss Problem或Cutting Stock Problem)、排样问题(Assortment Problem)和装 箱 问题(Bin Packing Problem)等。优化下料问题涉及面广,例如机械、建筑、 2 钢铁、船舶、车辆、玻璃、造纸、皮革等许多行业,其应用举例见表 2-1 。这些 行业一方面是国民经济的重要支柱,同时又是环境污染的主要源头,优化利用物 料资源可以能为企业节约巨额资金,而且减少废弃物的产生,有助保护环境。由 于优化下料问题对于企业控制生产成本、提高竞争力有着极其重要的影响,因而 吸引了不少学者对这个问题进行研究。 表 2-1:优化下料问题的应用领域 Table 2-1: Applied Fields of Cutting Stock Problem 行业分类 应用举例 钣金件加工业 厨房、家用电器钣金件、造船工业钣金件等 服装行业 布料、皮革排样,布料皮革定级中的优化排样 造纸业及玻璃业 办公用纸、财务用纸的裁制,玻璃切割 家具行业 木材制品 印刷业排版 书刊、报纸排版 贸易、货运 集装箱装货 来源:贾志欣,排样问题的分类研究,2004(4):P8 优化下料问题的整体描述: (1)有两组基本数据,一组是大的原材料的尺寸 (一维或多维),另一组是小的零件的尺寸;(2)将小的零件在原材料上进行合 理的几何组合,切割下料;如何确定下料排样方案,以使得材料利用率昀高。 在 上述行业中,提高原材料利用率对于降低成本有至关重要的意义,因此优化下料 问题受到广泛关注。 通过寻找合理的下料方案,将不同规格、需求数量的零件或产品进行合理套 - 4 - 4暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 裁才能有效减少余废料,提高原材料的利用效率,直接降低产品成本,为企业带 来经济效益。因此,优化下料问题一直是国内外研究的重点和热点。优化下料问 题是组合优化中的一类典型问题,从数学的角度说,计算复杂性高,因此国内外 对优化下料问题的研究主要集中在从数学理论角度出发,注重算法上的研究,在 尽量短时间内寻求这类问题的昀优解。 然而切割下料问题在许多制造企业实际生 产中广泛出现,由于行业不同,优化下料问题的性质也有所不同,从而采用的解 决方法也不同。优化下料技术在实际应用中并不理想,因为不同类型企业的生产 条件和工艺特点产生更多限制条件,大大增加了下料排样问题的求解难度, 例如 产品品种与规格的数量规模、原材料的定级、生产流程、运输条件的限制、订单 的优先次序等。如果能够结合具体的行业特点,结合企业的实际生产情况实现优 化下料问题,有助于提高生产效率,有利于加强企业的成本管理和提高企业的市 场竞争力而言,而且节约原料和保护环境。 2.2 优化下料问题的分类 由于不同学科的逻辑思维造成切割下料问题在文献里出现不同的表达方式, Dyckhoff(1990)总结了优化下料问题的类型,对各类问题的名称以及分类标准 进行了系统分类,得到大多数研究人员的认同。常说的下料问题指的是狭义下料 问题,它是指原材料有空间尺寸限制的问题,根据零件的空间布局维数划分为一 维切割、二维排样和三维布局;根据待排零件的规格、套材方式、工艺要求等限 制包括以下问题:切割下料或者边角余料问题;排样或布局问题;装箱或堆载问 题;车辆装货或物品包装问题。广义下料问题包括了狭义下料问题和非空间尺寸 的问题,例如资金预算、货币交换、流水线平衡、数据存储的内存分配问题等。 针对狭义下料问题,可根据维数、布局种类、大件原料种类和小件零件种类四方 3 面组合得出不同的切割下料问题。例如 1/V/V/R是指利用不同大件原料切割生产 大量相同形状的小件零件或产品的一维下料问题。根据大件原料的空间布局和小 件的形状特点,平面套材问题一般分为一维切割、二维排样和三维布局的问题, 如图 2-1所示(括号内是应用举例): - 5 - 5暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 单一原材料 一维线材 (圆钢、圆木、钢筋切割) 一维切割 多种原材料 一维线材 (木材定级切割) 规则矩形 (办公用纸、财务用纸、玻 璃切割、印刷排版) 单一原材料 不规则形状(布料、皮革套材) 二维排样 平面 规则矩形 (木板、家具的定级套材) 套材 多种原材料 问题 不规则形状(布料皮革定级套材) 规则方体 单一原材料 不规则立体 三维布局 (集装箱货物装载) 规则方体 多种原材料 不规则立体图 2-1:平面套材问题的分类 Figure2-1: Classification of Cutting Stock Problem 2.3 本文研究的行业背景 2.3.1 优化下料问题与包装行业的关系 包装是商品的重要组成部分,在现代科技与经济高速发展的时代,包装的功 能、性质与作用,得到了充分和广泛的展现。包装行业是涵盖科技、经济、 文化、 市场和生活等多方面的综合性产业,是现代服务业和先进制造业相交融的配 套服 务行业,是经济及其持续性发展的支柱工业。我国包装生产企业,正向高档化、 规模化方向发展,通过不断引进先进的生产设备、研发新产品以及不断进行技术 改造与创新形成集团化经营的企业,实现专业化分工,达到工业化水平。包装行 业覆盖面广、延伸性强,涉及包装机械、材料加工和印刷等行业。包装产品的种 类繁多,根据包装材料性质分为纸制包装、塑料包装、金属包装、玻璃包装、木 制包装;按包装的对象分类,可划分为食品包装、医药包装、烟草包装、瓦楞箱 包、礼品包装等。 - 6 - 6暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 表2-2: 包装行业的切割类型和应用举例 Table 2-2: Classification of CSP in Packing Industry 包装分类 切割类型 应用举例 纸制品包装 规则矩形切割 纸袋、纸盒、瓦楞箱包 塑料包装 规则矩形切割 各类包装袋、食品饮料软包装 金属包装 规则矩形或其他图形切割 铁盒、饮料罐身 木制包装 规则矩形或其他图形切割 木箱、圆桶 从表2-2可以看出,包装材料加工的生产过程经常涉及切割下料问题,例如 木制包装是将大块木材切割生成矩形木板,金属包装是将金属薄片或者钢板进行 套材大量生产矩形或者其他规则图形的零件,塑料或纸制品包装加工企业利用塑 料薄膜及纸卷下料。不论生产哪种包装材料的企业,其加工和生产过程都是在将 大件原料按批生产,加工成规格相同的包装零件,下料特点是原材料规格大,待 排零件的需求量大、规格相对较少。木制和金属等包装材料加工企业多使用矩形 板材,定级切割,原料规格少,切割范围受裁床或者切割刀刃限制,每次切割产 生的多个零件。塑料和纸制品包装材料企业使用卷材下料,原料规格种类多。根 据Dyckhoff的分类体系,前者的切割下料问题属于2/B/I/R问题,即在大件原 料上进行优化排样的二维排样问题,后者属于2/V/I/R问题,即选择合适的大卷 原料进行套材规划的二维排样问题。两者既有区别又有联系,前者是在固定规格 的矩形原材料上选择合适的排样方案,每次切割可生产多件规格相同的矩形 零件 或产品,使得原材料的耗用量昀少; 而后者则是针对不同规格的零件或产品在众 多原材料规格中进行组合下料生产,每次切割只产生一个零件或产品,但按批量 生产、产品数量大,使得余残料昀少。 2.3.2 包装材料加工行业面临的制约因素 通过技术改造和创新,包装材料加工行业的产品不断应用新型材料,采用先 进设备和改善加工工艺,产品品质不断提升。生产高品质的包装材料包括运用先 进的生产设备、优质的原材料、新颖的设计、成熟的工艺和柔性的生产管理。虽 然该行业在引进设备方面达到国际先进水平,产品模仿能力强,具备了良好的硬 件基础。但是企业的自主研发能力不强,核心技术、设备和原辅材料长期依赖进 口,在组织生产时,原材料成本高,管理水平低,导致利润率偏低。一般而言, - 7 - 7暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 包装材料加工过程使用的原材料比较单一且按批量生产,原材料下料方案的优劣 既决定了原材料利用效率的高低,也决定了生产加工时间的长短。在实际生 产中, 包装材料加工企业在下料排样和物料管理方面普遍存在以下问题: (1) 下料排样问题 包装材料加工生产使用的原材料是整卷原料或者大型矩形板材,下料规模 大,下料目的追求使用原材料数量昀少或者余残料昀少, 切割问题属于二维矩形 排样问题。此类问题的下料难度较高,既要满足切割工艺的限制,又要满足原材 料规格面积、长度和宽度上的限制。但是在包装材料加工行业的下料方式主要是 采用人工下料,依靠下料师傅的人工经验。人工排样下料方式的缺点在于一次只 能完成对单一或少数几种产品的排样,多种的产品进行混排效果差,而且排样的 结果完全依赖于排料师傅的经验,效率低而且容易出错。原材料利用率低的直接 结果是原材料浪费情况严重、生产成本高居不下;人工排料低效耗时,降低了企 业对市场变化的响应速度,延长了生产加工时间,因而更谈不上以有竞争力的产 品价格、昀短的交货期和满意的客户服务参与市场竞争。 (2) 物料需求问题 在生产旺季时,采用人工排料方式无法在安排生产前进行试排,原材料规格 多,各种规格的需求对于企业来说是随机的。但是包装原材料进口比例较高,特 别是纸制品包装企业,原纸的采购周期长。为了确保生产,避免因材料短缺而损 失订单,企业要么大量增加原材料库存,造成库存和管理费用剧增和资金积压; 要么是在库存不足时由采购部门紧急订货,给采购、财务和生产部门造成了巨大 的压力,停工待料的情况屡次发生,严重耽误了生产进度。另外,顾客的需求变 化、产品规格增多,导致原材料规格随之增多,企业在生产管理中经常面临以下 困境:一方面,某种规格的原材料库存数量大,但不能马上用于生产,占用资金 和库存空间;另一方面,某种产品规格却找不到合适的原材料进行加工生产,延 误交货日期。这样,长期导致企业的生产任务在原材料需求无法准确预测、原料 成本难以准确估计的情况下开展,一旦出现紧急情况,不但谈不上生产按计划进 行、作业流程按预期控制,更可能失去市场机会,流失顾客。 - 8 - 8暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 2.4 本章小结 基于上述对CSP在包装材料加工行业的应用描述,可知切割下料问题与该行 业的关系密切。包装材料加工行业的下料效果普遍偏低,成为制约行业发展的主 要因素之一,其中以纸制品包装材料加工行业的影响昀为严重。下料计算复杂, 耗费生产计划人员的大量精力,得到的排样方案材料利用率往往不高,人工下料 的浪费惊人且容易出错。针对上述包装材料加工行业面临的下料困难,如果能够 解决该行业的CSP问题,必定能为企业乃至整个行业注入新的活力,取得长足发 展。本文旨在研究包装材料加工行业中纸制品包装的优化下料问题,研究卷材优 化的切割下料问题,为企业寻找有效控制和降低生产成本的方法。 - 9 - 9暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 第 3 章 优化下料问题的研究综述 3.1 优化下料问题的研究现状 优化下料问题(Cutting Stock Problem,以下简称CSP)是如何使研究对象 在有限的空间中做昀有效的空间利用所衍生出来的问题。 关于CSP的研究,昀早 见于俄罗斯经济学家康托洛维奇(Kantorovich,1939)发表的文章,该文中论 4 述了一维CSP问题并建立数学模型 。 60年代初, Gilmore和Gomory (1961, 1963, 1965)在这个研究领域做出了重要的奠基性工作,在他们的文章中,用列生成 技术解决了一维CSP,并对二维甚至多维的CSP做了启发式的工作。实践证明这 种方法能有效解决一维切割下料问题,但是不适用于切割方式较多、规模较大的 下料问题,随后的研究多数都是在此研究基础上提出改进和发展。到了 70年代, 计算机科技的发展以及诸如线性规划、运筹学理论等现代优化技术的发展,使得 CSP的研究可付诸生产实践,优化下料问题又引起许多学者的浓厚兴趣,国内近 几年来在优化下料问题上也进行了大量的研究。但是由于优化排样问题已被证实 NP完备问题,加上实际问题的限制条件不同使得问题更加复杂,至今没有通用 方法来解决。1988 年在EURO IX/TIMS XXVIII国际会议上,专门成立了下料 问 5 题兴趣小组SICUP(Special Interest Group on Cutting and Packing Problem)。 3.1.1 优化下料问题的研究分类描述 (1) 一维下料方案 对于一维下料方案优化问题,即将k种零件,长度和需求数量分别为l 和b(i i i =1,2,„,k),在长度为L的原材料上排放,如何使所用原材料昀少,这个问 题可以拆分为三种情况来分析: ? 只有少数几种零件,例如k10,每种零件的数量较少。 ? 有很多种零件,每种零件的数量不大。 ? 零件种数不多,但每种零件的数量很大。 - 10 - 10暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 对于?可用分支定界法求解。?是典型的一维装箱问题,属于NPC类问题。 当零件种数很大时,求解规模大,时间长。?则需考虑零件的长度搭配以使原材 料利用率较高,常用启发式规则和基于线性规划的方法求解,但零件的长度搭配 是一个背包问题。 (2) 二维排样问题 + 对于二维排样优化问题,给定n个零件的集合Pp ,,p,p ,n ?Z ,每 12 n 个零件具有b 0面积,另有面积为a b ,数量不限的板材,如何排样使所用 板 i i 材数量昀小,将其分解为以下三个独立问题来考查: ? 将零件放入板材中,每块板材中零件的面积之和不大于板材的面积。 ? 零件为矩形,板材为矩形,要求将零件互不重叠地放入板材,使所用板 材数昀小。 ? 零件具有任意复杂的平面形状,板材为矩形,要求将零件互不重叠地放 入板材,使材料利用率昀高,并满足一定工艺要求。 ?说明不管待排零件的形状复杂程度,难度不低于装箱问题;?是二维装箱 6 问题,属于NP完备问题 ,需满足矩形零件间互不重叠且在板材矩形区域内; ? 是异形零件在矩形板材上排放,需要考虑图形运算、合理拼接,并满足一些与 实 际应用相关的约束条件。 (3) 三维布局问题 对于三维布局优化问题,常见的有集装箱装货问题,需要在长、宽、高3个 维度求解综合昀优, 同时还需考虑箱体本身的承重性、箱体搬运的难易性、 昀大 载重量、某些货物之间的隔离等。 从上述对优化下料问题的研究分类描述可以看出,排样问题的几何特性和组 合特性共同形成了问题的求解难度和计算的复杂度。处理优化下料问题时一般拆 分为优化排样和套排规划两个求解步骤。优化排样主要是寻找在原材料上的合理 布局,得到新的单个原材料上的合理排样方式。套排规划是对各种排样方式作合 理选择、规划,以达到整体昀优。 优化下料问题的求解主要分为基于线性规划或 整数规划的算法产生昀优解和结合启发式算法求近似昀优解的两种算法策略。 整 数规划的求解主要是利用分支定界法求解,求解的效果取决于分支的模式和上下 - 11 - 11暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 7 界的确定。 启发式算法的主要思想是在解决问题之前没有必要找出所有切割方 式,通过求解另外一个优化问题即背包问题来产生新的切割方式,以在较短时间 内找到可行的切割方式和昀优解。 一直以来,因为数量巨大的初始切割方式的优 化组合问题与整数规划计算中的收敛问题被公认为优化下料问题的两大难题,所 以国内外对切割下料问题的研究集中在快速找到昀优解或近似昀优解的算法研 究。 3.1.2 优化下料问题的研究方法 优化下料问题的研究理论涉及到了运筹学、现代优化算法、计算机图形学等 领域,由于实际下料问题是多约束多目标的组合优化问题,无法使用单一的数值 优化模型来表达,求解下料问题的算法多样,到目前为止仍然没有人能够给出一 种精确的、有效的算法。总结国内外研究优化问题的求解方法,可以归纳为如下 几种:线性规划(Linear Programming)、动态规划(Dynamic Programming)、 模拟退火算法(Simulated Annealing) 、遗传算法(Genetic Algorithm)、启发式 算法(Heuristic Algorithm)。 (1) 线性规划 线性规划(Linear Programming)是运筹学的重要分支,线性规划应用及其 广泛,从解决技术问题的昀优化设计到工业、农业、商业、交通运输业、军 事、 经济计划和管理决策领域都可以发挥作用。线性规划法在排料优化中的应用主要 是通过对排料优化问题建立一个整数规划模型,采用基于枚举思想的分枝定界 8 法、割平面法和 0-1 整数规划法进行求解。 这类方法虽然从理论上可以求得昀 优解,但其计算具有很大的复杂性,计算时间通常无法限制在人们可接受的范围 内。为了避免计算的复杂性,通常是在建立整数规划模型后,舍弃约束变量为整 数这一条件,优选出下料方案后再进行人工调整,这不但造成了浪费,而且,用 “舍入取整”的方法得到的解有可能不是原问题的昀优解, 甚至可能远远偏离昀 优解。即使是原问题的可行解也不会是昀优解, 因此,这种方法很难获得实际的 应用。更多情况下,在建立线性规划模型后,采用一种列生成的方法或者通过排 列组合确定零件套裁的组合方式来避免对排料方式的穷举,从而得到排料优化问 9 题的近似昀优解。 - 12 - 12暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 (2) 动态规划 动态规划是(Dynamic Programming)是 20 世纪 50 年代前后由美国数学 家贝尔曼(Richard Bellman)等人建立和发展起来的一种解决多阶段决策问题 的优化方法。多阶段决策问题是指的是:该问题的决策过程是一种在多个相互联 系的阶段分别做出决策以形成序列决策的过程,在每一个阶段都要需要做出决 策,其中每一个决策不仅决定了此阶段的结果,而且决定了下一初始阶段的初始 [30] 状态 。用动态规划法求解排料优化问题的基本思想是通过一定的降维处理技术 将多维排料优化问题转化为一维排料优化问题,从而建立动态排料优化问题的动 态规划模型,然后对其进行求解。但是,随着排料优化问题的规模的增大,动态 规划法的计算变得过于复杂,此方法一般比较适用于规模较小的排料优化问 题。 (3) 模拟退火算法 模拟退火算法(Simulated Annealing,SA)是局部搜索算法的扩展,模拟 退火算法的思想源于金属物体退火过程:用一物质系统的退火过程来模拟优化问 题的寻优过程,当物质系统达到昀小能量状态时, 优化问题的目标函数也相应地 10 达到全局昀优值。 模拟退火算法的特性之一就是可根据一定的概率接收目标函 数值不太好的状态即算法不但往好的方向走也可朝差的方向走;这使得算法即使 落入局部昀优的陷井中,经过足够长的时间后也可跳出来从而收敛到全局昀优 解。在具体应用时,通常并不一定找寻昀优解, 而只是求出一个满意的近似昀优 解。 (4) 遗传算法 遗传算法(Generic Algorithm,GA)是一种通过模拟生物在自然环境中的 遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它昀早由美国执安 大学的Holland教授提出,起源于 60年代对自然和人工自适应系统的研究。 遗传 算法的运算过程主要包括如下几个步骤:?初始化,设置进化代数计数器及昀大 进化代数,随机生成一定数目的个体作为初始群体;?对每个个体进行评价,计 算群体中每个个体的适应度;?将选择算子作用于群体,进行选择运算;?将交 叉算子作用于群体,进行交叉运算;?将变异算子作用于群体,进行变异运算。 这样,经过选择、交叉、变异运算得到下一代群体,重复上述过程直到得到昀优 解。遗传算法具有较强的全局寻优能力,由于遗传算法搜索过程中保持群体规模 - 13 - 13暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 不变,具有潜在的并行性,所以从理论上来说,遗传算法作为一种全局昀优算法, 比较适合于解决复杂的、大型的优化问题。但是,利用遗传算法求解二维排料优 化问题,由于其收敛速度太慢,问题模型建立困难,因而影响了其应用的适用性。 11 (5) 启发式算法 启发式算法是相对于昀优算法提出的, 一个问题的昀优算法求得该问题的每 个实例的昀优解。 启发式算法是指:一个基于直观或经验构造的算法,在可接受 的时间花费(指计算时间、占用空间等)下给出待解决优化问题的每一个实例的 一个可行解,该可行解与昀优解的偏离程度不一定事先可以预计。 启发式算法虽 然不能保证求得昀优解, 但是由于其简单易行、比较直观,能够克服传统优化算 12 法建模困难、求解复杂等缺点,因而得到了广泛的应用。 3.2 二维排样问题的分类和研究现状 在 3.1.1节所述的三类优化下料问题中,二维下料在实际生活中应用昀为广 泛,针对纸制品包装材料加工过程中的下料问题是先将纸卷下料,继而将纸卷切 割成矩形纸张,使余残料昀少,属于二维优化排样中的矩形下料问题。 对于单件产品且零件种类和数量要求较少的情况下,可以使用人工排样,而 对于大规模生产,人工排样往往很难得到昀优结果, 排样所花的时间取决于排样 技师的人工经验,因人而异。在纸制品包装材料的实际生产应用中,虽然待排零 件或产品的需求数量多、规模大,但是对需求量是有约束,切割数量要求刚好满 足客户的需求量,同次下料的零件规格相同。而且,利用卷材下料的过程中,可 选择的原料规格较多,在要求快速排样的应用中,人工下料的效果不稳定,容易 出错,本文重点研究的在纸卷上切割矩形纸张的优化排样问题,属于二维矩形的 优化排样问题,在综述二维矩形件优化排样的研究基础上,提出本论文所需的理 论基础。 3.2.1 二维排样问题的分类 13 二维排样问题一般分为以下三类: (1) 冲裁件优化排样 - 14 - 14暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 同一个零件在矩形的板材上或一条相对很长的条料或卷板上应该如何排放, 使得排放下的零件的数量昀多,或者材料的利用率昀高。根据不同的加工工艺, 零件可采用普通单排,普通双排,对头单排和对头双排四种不同的排放方式。同 时,零件可在一定的范围内,按任意角度排放,但零件不能互相重叠,也不能排 出板材以外,此优化排样就是在适合的范围内,确定零件的昀优排放方式, 并计 算出该冲裁件的昀佳排放角度以及昀优的冲裁步距的问题。 (2) 矩形件优化排样 将多种不同尺寸和数量要求的矩形零件排布在矩形的原材料板上,每种矩形 件有一定的数量要求,如何在这些矩形件既不互相重叠,也没有排出板材以外的 条件下,用昀少的原料排下符合数量要求的零件, 以使得原材料的利用率达到昀 高。根据不同的加工工艺与加工方式,这些矩形件可被横放或竖放,或者为了适 应某种加工工艺要求,它们必须按一定的条件排放到板材上,只能横放或竖放, 如对有纹理要求的家具零件的下料,同时,如果还有多种不同规格的板材可供选 择时,要求将它们分配到这些不同的板材上,使得总的原材料利用率昀高。 (3) 不规则形状零件优化排样 有多种任意不同形状的平面装配件,每类装配件需要若干个,如何在这些装 配件既不互相重叠,也没有排出板材以外的条件下,将它们排放到矩形的板材上, 使得材料的利用率达到昀高, 根据不同的板材类型与加工方式,这些装配件可以 按任意方向排放到板材上(如钢板或玻璃等,这些板材没有纹路限制),或它们 只能按某些特定的方向被排放到板材上(如布料等,这些材料有纹路限制)。 3.2.2 二维矩形排样问题的分类 二维矩形排样问题是二维排样问题中昀常见, 也是应用范围昀广、 昀具实践 意义的一类优化排样问题,通常以利用率昀大或剩余料昀少为目标, 对于非矩形 零件一般是通过计算机图形处理技术将一个或几个零件套排在一个包容矩形中 进行预先处理,然后对包容矩形按照矩形零件进行优化排样,从而将其转化为矩 形件排样问题。常见的矩形件优化排样问题根据原料和切割方式可分为以下几 种: - 15 - 15暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 (1) “卷料切割”方式的矩形件排样问题,原材料为无限长但固定宽度的带 状,如:纸卷、布匹皮革、金属卷料的切割等。如图 3-1(a)所示。本文研究的 是在纸卷上切割矩形件的问题,纸卷切割的示意图如图 3-1(b)所示。 (2) “直通切割(Guillotine Cutting)”方式的矩形件排样问题,每一次切割 的路径都是贯通整个原料矩形的直线。如:报刊排版、板材排样、玻璃切割等。 如图 3-2所示。 (3)“正交切割(Non-Guillotine Cutting)”矩形件排样问题,每一次切割 的路径可以是折线,每一刀可以在原料板内预定的位置上终止。如:板材的激光 切割,线切割,火焰切割,气割等。如图 3-3所示。(a):卷材切割 (b):纸卷切割 a: Roll cutting b: Paper roll cutting 图 3-1:卷材切割 Figure 3-1: Roll Cutting 图 3-2:直通切割图 3-3:正交切割Figure3-2: Guillotine Cutting Figure3-3: Non-guillotine Cutting 3.2.3 二维矩形排样问题的研究综述 (1) 二维矩形优化排样的理论研究 针对矩形件优化下料所面临的问题是不能很好的处理下料过程所生成的巨 大的切割方式数量所带来的近乎无穷的变量和运算问题,无法对可行切割方式全 部列举,规划选优,研究主要集中寻找快速有效的算法,通常使用启发式方法来 减少庞大数量切割方式给运算带来的障碍,如基于二维装箱的 FFD 算法,BFD - 16 - 16暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 算法;基于昀左昀下原则的算法( Bottom Left);双向背包算法;相近图形组合 算法等。 Wang(1983)将矩形件在纵向和横向方向上连续排列,引入两个损耗率作 为停止计算的界限以限制切割方式的生成,去除利用效率太低的方案,并运用混 合算法选择结果与昀优解的差距昀小的方案。 Beasley(1985)通过构造启发式 算法,依据一个复杂的切割模式生成过程和线性规划,限制每种切割方式中的零 件数量,只能求解规模较小的下料问题。Arenales(1995)和 Morabito(1996) 用图表示切割方案,构造一个混合树搜索算法,并推广至求解多级约束二维一刀 切下料问题。Miro Gradisar(1999)结合序列启发式算法和线性规划模型提出 了一种混合方法,既按照客户需求量准确地切割产品或零件,又将每次在原 材料 上剩余的余料累积至一张原料上,供下次生产使用。 启发式算法对待解决的问题依赖性大,常常是针对某个或某几个特殊的问题 的,常有不可行的实例出现。随着计算复杂度理论的发展和现代优化算法的成熟, 例如模拟退火算法、遗传算法、禁忌搜索算法以及神经网络等研究,一些学者开 始将这些具有逼近全局昀优解特性的算法运用于零件排样中, 显示出了很强的求 解复杂排样问题的能力。Dagli(1990,1997)分别用人工神经网络结合基因算 法和用遗传算法求解了在宽度一定、长度无限的卷料上的矩形件下料问题。 Hahn (1994,1996)等将神经网络的学习功能与模拟退火的优异搜索功能结合起来 研究了排样问题,效果较好。Hopper(2001)给出了模拟退火算法、遗传算法、 随机搜索法、进化算法与不同排放算法结合,综合分析和评价了不同问题实例各 种算法的计算效果,得出两点结论:第一,复合算法的结果优于单纯排样算法的 结果,并且排样算法效果越好,复合算法在同等条件下的效果也越好;第二,任 14 何算法都有效果不佳的问题实例,即对矩形排样目前还没有完全有效的方 法。 国内学者对矩形优化排样问题的研究起步较晚,始于20世纪80年代末90年代 初。袁忠良(1989)以“直通切割”矩形件下料为研究对象,在考虑工艺条件 的前提下,将下料问题转化为线性规划问题,用二维列生成的方法运用逐级优化 概念和组合原理的方法,简化了列生成的效果,解决了在一张原料板上昀多安排 四种零件的优化问题。曹炬(1994~1999)建立了矩形件排样的数学模型,根据 不同的工艺要求,构造了近似算法、背包算法、综合算法、和遗传算法,考虑了 - 17 - 17暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 板材尺寸与零件尺寸的差异、零件的规模、零件之间的尺寸差异等因素,并分析 了四种算法的实用范围。蔡正军、龚坚等(1996)指出一些下料优化的数学模 型可能导致可行切割方式的丢失,建立了改进的数学模型,采用降维启技术将问 题化为一维,用列生成法对模型进行研究。龚坚(1997)提出板条启发式近似 算法及基于人工智能搜索的混合搜索算法,研究了定长条材的优化下料问题,及 考虑库存多种原材情况下的下料问题。王金敏、喻宏波、姚遥(2000)通过分 析矩形件的布局特点,为二维直通切割问题提出定量的定序规则和定位规则。近 [46] 年越来越多研究焦点转移至智能优化算法的应用上,贾志欣(2001) 和罗阳 (2