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

1、面向纸制品包装材料加工企业的优化下料问题研究 摘 要 切割下料问题广泛存在生产制造企业中,其工业应用领域非常广阔,本文以面向纸制品包装材料加工企业的优化下料问题为研究对象,开展纸卷下料的应用研究。 本文首先介绍了课题的研究目标、课题来源和行业背景,概括了本课题的研究内容和理论基础。以一家大型纸制品包装材料加工企业的实际生产作为本文的应用研究背景,针对企业面临的下料困难提出总体解决方案和实施步骤,首先从改进原纸的下料规格出发,优化下料规格使之更符合实际生产的要求。继而根据纸制品包装材料的生产特点和具体切割工艺要求,研究纸制品包装材料加工企业的优化下料模型,建立多种原纸规格的数学模型,结合公司实际

2、生产数据求解昀优下料方案并进行结果分析。 通过研究纸制品包装材料加工企业的切割下料问题,运用科学的方法为企业提出优化下料策略,寻找昀优的下料方案, 改进下料效果,达到改善企业的生产管理、提高竞争力和增强应变能力的目的。关键词:纸制品包装,切割下料问题,组合优化 - 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 popu

3、larity 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 a

4、re 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

5、 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 companys producing and cutting specification. then two stereotypes of csp in the paper p

6、acking 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 目 录

7、 摘 要.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 优化下料问题的研究方法.

8、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

9、章 纸制品包装材料企业的下料模型研究.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

10、 第 6 章 总结与展望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:第一组产

11、品数据.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:2

12、50g类产品的产量分布情况.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 p

13、roblem,简称csp),通常是指在一组给定的原材料上,尽可能多地排放需要的1零件或产品,使得原材料的耗用量昀低或者利用率昀大,以减少废料。 工业和建筑业的许多原材料,例如圆钢、圆木、钢筋、铁板、薄铁皮、塑料板以及纸张、布匹等,一般都存在下料或排样的问题。它是针对如何使切割对象在有限的空间中昀有效地利用空间布局而衍生出来的问题, 也就是将待切割对象摆放在一定规格的大件原料表面上进行套材切割,目的使原料损耗率昀低。 加工制造过程中的优化下料问题是制造系统资源优化利用问题之一,一个好的下料计算方法和下料方案,可以提高原材料的使用率、降低生产成本,从而提高产品的市场竞争力。 原材料成本高、下料效果

14、差已经成为制约纸制品包装材料加工行业发展的瓶颈之一。为此,本文拟在一家大型纸制品包装材料加工企业进行应用研究,针对该企业面临的下料困难,提出整体对策方案,然后基于纸制品包装材料加工行业的现状和生产特点,结合加工工艺的要求和其他限制条件,采用优化下料技术为同类企业研究优化下料的数学模型并求解昀优下料方案, 以达到提高原材料利用率、指导生产的目的。 1.2 课题来源和研究内容 1.2.1 课题来源 本文以一家生产烟草包装材料为主的大型纸制品包装企业为研究背景,近年,随着烟草行业的繁荣,公司的生产规模得到很大的提高,产品品种和业务种类向多元化发展。随着市场竞争加剧以及公司进行组织变革,生产管理方面的

15、问题逐渐凸显,公司领导越来越意识到原材料成本高、下料困难是制约公司发展的瓶颈之一。因此,在公司领导的大力支持和帮助下,本文作者有幸到企业进行实- 1 - 1暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 习调研并开展优化下料问题的研究。通过熟悉生产流程总结归纳出实际的切割工艺要求和下料限制条件,分析企业的产品生产和原材料的需求状况,为企业改进下料决策,寻找有效求解昀优下料方案的方法。 1.2.2 研究内容 本文运用定性和定量方法,结合纸制品包装材料加工企业的切割工艺要求和生产限制条件,进行纸卷优化下料问题的应用研究,为企业提供改善经营的方法和途径,主要完成以下内容: (1)

16、第一章:概括本课题的选题意义和研究目标,简述本课题的来源、研究内容和研究路线。 (2) 第二章:概述优化下料问题、应用领域和分类,介绍优化下料问题与包装材料加工行业的关系及应用情况,总结该行业在下料管理方面存在的问题和制约因素。 (3) 第三章:详细综述优化下料问题的理论研究,重点概述二维矩形排样问题的研究现状,为本课题开展应用研究提供必要的理论基础,运用有关知识解决纸卷切割下料的问题。 (4) 第四章:以一家大型纸制品包装材料加工企业为背景开展应用研究,针对企业的下料困难提出整体对策,从两个层次解决应用中的下料问题。首先,选择合适的下料原料规格;其次,寻找昀佳的下料方案。 (5) 第五章:论

17、述纸制品包装材料加工的生产特点,在满足实际切割工艺要求的前提下为同类企业研究优化下料模型,建立多种原纸宽度规格的数学模型,运用线性规划求解,以公司的实际数据为求解实例并分析结果。 (6) 第六章:对本研究进行总结和展望,指出本研究的不足之处和后续研究工作的方向。- 2 - 2暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 1.3 研究路线 本文的研究思路是以一家大型纸制品包装材料加工企业为背景进行应用研究,针对企业面临的下料困难提出整体对策:首先分析公司的产品生产情况,改进原材料下料规格,使之更适于生产;其次基于同尺寸产品的大规模优化排样研究的基础上,为纸制品包装材料加工行业

18、的切割下料问题提出优化下料技术,研究多种原纸宽度规格的数学模型,运用线性规划求解纸卷下料的实际应用问题,用理论指导实践生产。论述企业具体的优化下料问题的概述和 下料问题和限制 分类 条件开展面向纸制品提出解决下料问课题的行业包装材料加工企背景 题的整体对策和业的应用研究 实施步骤优化下料的 建立纸卷下研究综述 料的数学模型并求解目标:解决优化下料问题, 改善纸卷的下料效果图 1-1:本文的研究路线figure 1-1: the research route of this thesis - 3 - 3暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 第 2 章 优化下料问题概述

19、 2.1 优化下料问题的应用领域 在工业应用领域上,优化下料问题有多种提法,例如切割问题(trim loss problem或cutting stock problem)、排样问题(assortment problem)和装箱问题(bin packing problem)等。优化下料问题涉及面广,例如机械、建筑、2钢铁、船舶、车辆、玻璃、造纸、皮革等许多行业,其应用举例见表 2-1 。这些行业一方面是国民经济的重要支柱,同时又是环境污染的主要源头,优化利用物料资源可以能为企业节约巨额资金,而且减少废弃物的产生,有助保护环境。由于优化下料问题对于企业控制生产成本、提高竞争力有着极其重要的影响,因

20、而吸引了不少学者对这个问题进行研究。 表 2-1:优化下料问题的应用领域table 2-1: applied fields of cutting stock problem 行业分类 应用举例 钣金件加工业 厨房、家用电器钣金件、造船工业钣金件等 服装行业 布料、皮革排样,布料皮革定级中的优化排样 造纸业及玻璃业 办公用纸、财务用纸的裁制,玻璃切割 家具行业 木材制品 印刷业排版 书刊、报纸排版 贸易、货运 集装箱装货 来源:贾志欣,排样问题的分类研究,2004(4):p8 优化下料问题的整体描述: (1)有两组基本数据,一组是大的原材料的尺寸(一维或多维),另一组是小的零件的尺寸;(2)将小

21、的零件在原材料上进行合理的几何组合,切割下料;如何确定下料排样方案,以使得材料利用率昀高。 在上述行业中,提高原材料利用率对于降低成本有至关重要的意义,因此优化下料问题受到广泛关注。 通过寻找合理的下料方案,将不同规格、需求数量的零件或产品进行合理套- 4 - 4暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 裁才能有效减少余废料,提高原材料的利用效率,直接降低产品成本,为企业带来经济效益。因此,优化下料问题一直是国内外研究的重点和热点。优化下料问题是组合优化中的一类典型问题,从数学的角度说,计算复杂性高,因此国内外对优化下料问题的研究主要集中在从数学理论角度出发,注重算法上

22、的研究,在尽量短时间内寻求这类问题的昀优解。 然而切割下料问题在许多制造企业实际生产中广泛出现,由于行业不同,优化下料问题的性质也有所不同,从而采用的解决方法也不同。优化下料技术在实际应用中并不理想,因为不同类型企业的生产条件和工艺特点产生更多限制条件,大大增加了下料排样问题的求解难度,例如产品品种与规格的数量规模、原材料的定级、生产流程、运输条件的限制、订单的优先次序等。如果能够结合具体的行业特点,结合企业的实际生产情况实现优化下料问题,有助于提高生产效率,有利于加强企业的成本管理和提高企业的市场竞争力而言,而且节约原料和保护环境。 2.2 优化下料问题的分类 由于不同学科的逻辑思维造成切割

23、下料问题在文献里出现不同的表达方式,dyckhoff(1990)总结了优化下料问题的类型,对各类问题的名称以及分类标准进行了系统分类,得到大多数研究人员的认同。常说的下料问题指的是狭义下料问题,它是指原材料有空间尺寸限制的问题,根据零件的空间布局维数划分为一维切割、二维排样和三维布局;根据待排零件的规格、套材方式、工艺要求等限制包括以下问题:切割下料或者边角余料问题;排样或布局问题;装箱或堆载问题;车辆装货或物品包装问题。广义下料问题包括了狭义下料问题和非空间尺寸的问题,例如资金预算、货币交换、流水线平衡、数据存储的内存分配问题等。针对狭义下料问题,可根据维数、布局种类、大件原料种类和小件零件

24、种类四方3面组合得出不同的切割下料问题。例如 1/v/v/r是指利用不同大件原料切割生产大量相同形状的小件零件或产品的一维下料问题。根据大件原料的空间布局和小件的形状特点,平面套材问题一般分为一维切割、二维排样和三维布局的问题,如图 2-1所示(括号内是应用举例): - 5 - 5暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 单一原材料 一维线材 (圆钢、圆木、钢筋切割) 一维切割 多种原材料 一维线材 (木材定级切割) 规则矩形 (办公用纸、财务用纸、玻璃切割、印刷排版) 单一原材料 不规则形状(布料、皮革套材) 二维排样 平面规则矩形 (木板、家具的定级套材)套材多种原

25、材料 问题 不规则形状(布料皮革定级套材) 规则方体单一原材料 不规则立体三维布局 (集装箱货物装载) 规则方体 多种原材料 不规则立体图 2-1:平面套材问题的分类 figure2-1: classification of cutting stock problem 2.3 本文研究的行业背景 2.3.1 优化下料问题与包装行业的关系 包装是商品的重要组成部分,在现代科技与经济高速发展的时代,包装的功能、性质与作用,得到了充分和广泛的展现。包装行业是涵盖科技、经济、文化、市场和生活等多方面的综合性产业,是现代服务业和先进制造业相交融的配套服务行业,是经济及其持续性发展的支柱工业。我国包装生产

26、企业,正向高档化、规模化方向发展,通过不断引进先进的生产设备、研发新产品以及不断进行技术改造与创新形成集团化经营的企业,实现专业化分工,达到工业化水平。包装行业覆盖面广、延伸性强,涉及包装机械、材料加工和印刷等行业。包装产品的种类繁多,根据包装材料性质分为纸制包装、塑料包装、金属包装、玻璃包装、木制包装;按包装的对象分类,可划分为食品包装、医药包装、烟草包装、瓦楞箱包、礼品包装等。- 6 - 6暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 表2-2: 包装行业的切割类型和应用举例 table 2-2: classification of csp in packing ind

27、ustry 包装分类 切割类型 应用举例 纸制品包装 规则矩形切割 纸袋、纸盒、瓦楞箱包 塑料包装 规则矩形切割 各类包装袋、食品饮料软包装 金属包装 规则矩形或其他图形切割 铁盒、饮料罐身 木制包装 规则矩形或其他图形切割 木箱、圆桶 从表2-2可以看出,包装材料加工的生产过程经常涉及切割下料问题,例如木制包装是将大块木材切割生成矩形木板,金属包装是将金属薄片或者钢板进行套材大量生产矩形或者其他规则图形的零件,塑料或纸制品包装加工企业利用塑料薄膜及纸卷下料。不论生产哪种包装材料的企业,其加工和生产过程都是在将大件原料按批生产,加工成规格相同的包装零件,下料特点是原材料规格大,待排零件的需求量

28、大、规格相对较少。木制和金属等包装材料加工企业多使用矩形板材,定级切割,原料规格少,切割范围受裁床或者切割刀刃限制,每次切割产生的多个零件。塑料和纸制品包装材料企业使用卷材下料,原料规格种类多。根据dyckhoff的分类体系,前者的切割下料问题属于2/b/i/r问题,即在大件原料上进行优化排样的二维排样问题,后者属于2/v/i/r问题,即选择合适的大卷原料进行套材规划的二维排样问题。两者既有区别又有联系,前者是在固定规格的矩形原材料上选择合适的排样方案,每次切割可生产多件规格相同的矩形零件或产品,使得原材料的耗用量昀少; 而后者则是针对不同规格的零件或产品在众多原材料规格中进行组合下料生产,每

29、次切割只产生一个零件或产品,但按批量生产、产品数量大,使得余残料昀少。 2.3.2 包装材料加工行业面临的制约因素 通过技术改造和创新,包装材料加工行业的产品不断应用新型材料,采用先进设备和改善加工工艺,产品品质不断提升。生产高品质的包装材料包括运用先进的生产设备、优质的原材料、新颖的设计、成熟的工艺和柔性的生产管理。虽然该行业在引进设备方面达到国际先进水平,产品模仿能力强,具备了良好的硬件基础。但是企业的自主研发能力不强,核心技术、设备和原辅材料长期依赖进口,在组织生产时,原材料成本高,管理水平低,导致利润率偏低。一般而言,- 7 - 7暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下

30、料问题研究 包装材料加工过程使用的原材料比较单一且按批量生产,原材料下料方案的优劣既决定了原材料利用效率的高低,也决定了生产加工时间的长短。在实际生产中,包装材料加工企业在下料排样和物料管理方面普遍存在以下问题: (1) 下料排样问题 包装材料加工生产使用的原材料是整卷原料或者大型矩形板材,下料规模大,下料目的追求使用原材料数量昀少或者余残料昀少, 切割问题属于二维矩形排样问题。此类问题的下料难度较高,既要满足切割工艺的限制,又要满足原材料规格面积、长度和宽度上的限制。但是在包装材料加工行业的下料方式主要是采用人工下料,依靠下料师傅的人工经验。人工排样下料方式的缺点在于一次只能完成对单一或少数

31、几种产品的排样,多种的产品进行混排效果差,而且排样的结果完全依赖于排料师傅的经验,效率低而且容易出错。原材料利用率低的直接结果是原材料浪费情况严重、生产成本高居不下;人工排料低效耗时,降低了企业对市场变化的响应速度,延长了生产加工时间,因而更谈不上以有竞争力的产品价格、昀短的交货期和满意的客户服务参与市场竞争。 (2) 物料需求问题 在生产旺季时,采用人工排料方式无法在安排生产前进行试排,原材料规格多,各种规格的需求对于企业来说是随机的。但是包装原材料进口比例较高,特别是纸制品包装企业,原纸的采购周期长。为了确保生产,避免因材料短缺而损失订单,企业要么大量增加原材料库存,造成库存和管理费用剧增

32、和资金积压;要么是在库存不足时由采购部门紧急订货,给采购、财务和生产部门造成了巨大的压力,停工待料的情况屡次发生,严重耽误了生产进度。另外,顾客的需求变化、产品规格增多,导致原材料规格随之增多,企业在生产管理中经常面临以下困境:一方面,某种规格的原材料库存数量大,但不能马上用于生产,占用资金和库存空间;另一方面,某种产品规格却找不到合适的原材料进行加工生产,延误交货日期。这样,长期导致企业的生产任务在原材料需求无法准确预测、原料成本难以准确估计的情况下开展,一旦出现紧急情况,不但谈不上生产按计划进行、作业流程按预期控制,更可能失去市场机会,流失顾客。 - 8 - 8暨南大学硕士学位论文面向纸制

33、品包装材料加工企业的优化下料问题研究 2.4 本章小结 基于上述对csp在包装材料加工行业的应用描述,可知切割下料问题与该行业的关系密切。包装材料加工行业的下料效果普遍偏低,成为制约行业发展的主要因素之一,其中以纸制品包装材料加工行业的影响昀为严重。下料计算复杂,耗费生产计划人员的大量精力,得到的排样方案材料利用率往往不高,人工下料的浪费惊人且容易出错。针对上述包装材料加工行业面临的下料困难,如果能够解决该行业的csp问题,必定能为企业乃至整个行业注入新的活力,取得长足发展。本文旨在研究包装材料加工行业中纸制品包装的优化下料问题,研究卷材优化的切割下料问题,为企业寻找有效控制和降低生产成本的方

34、法。 - 9 - 9暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 第 3 章 优化下料问题的研究综述 3.1 优化下料问题的研究现状 优化下料问题(cutting stock problem,以下简称csp)是如何使研究对象在有限的空间中做昀有效的空间利用所衍生出来的问题。 关于csp的研究,昀早见于俄罗斯经济学家康托洛维奇(kantorovich,1939)发表的文章,该文中论4述了一维csp问题并建立数学模型 。 60年代初, gilmore和gomory (1961, 1963,1965)在这个研究领域做出了重要的奠基性工作,在他们的文章中,用列生成技术解决了一维cs

35、p,并对二维甚至多维的csp做了启发式的工作。实践证明这种方法能有效解决一维切割下料问题,但是不适用于切割方式较多、规模较大的下料问题,随后的研究多数都是在此研究基础上提出改进和发展。到了 70年代,计算机科技的发展以及诸如线性规划、运筹学理论等现代优化技术的发展,使得csp的研究可付诸生产实践,优化下料问题又引起许多学者的浓厚兴趣,国内近几年来在优化下料问题上也进行了大量的研究。但是由于优化排样问题已被证实np完备问题,加上实际问题的限制条件不同使得问题更加复杂,至今没有通用方法来解决。1988 年在euro ix/tims xxviii国际会议上,专门成立了下料问5题兴趣小组sicup(s

36、pecial interest group on cutting and packing problem)。 3.1.1 优化下料问题的研究分类描述 (1) 一维下料方案 对于一维下料方案优化问题,即将k种零件,长度和需求数量分别为l 和b(ii i=1,2,k),在长度为l的原材料上排放,如何使所用原材料昀少,这个问题可以拆分为三种情况来分析: 只有少数几种零件,例如k10,每种零件的数量较少。 有很多种零件,每种零件的数量不大。 零件种数不多,但每种零件的数量很大。 - 10 - 10暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 对于可用分支定界法求解。是典型的一维装箱

37、问题,属于npc类问题。当零件种数很大时,求解规模大,时间长。则需考虑零件的长度搭配以使原材料利用率较高,常用启发式规则和基于线性规划的方法求解,但零件的长度搭配是一个背包问题。 (2) 二维排样问题 +对于二维排样优化问题,给定n个零件的集合pp ,p,p ,n z ,每12 n个零件具有b 0面积,另有面积为a b ,数量不限的板材,如何排样使所用板i i材数量昀小,将其分解为以下三个独立问题来考查: 将零件放入板材中,每块板材中零件的面积之和不大于板材的面积。 零件为矩形,板材为矩形,要求将零件互不重叠地放入板材,使所用板材数昀小。 零件具有任意复杂的平面形状,板材为矩形,要求将零件互不

38、重叠地放入板材,使材料利用率昀高,并满足一定工艺要求。 说明不管待排零件的形状复杂程度,难度不低于装箱问题;是二维装箱6问题,属于np完备问题 ,需满足矩形零件间互不重叠且在板材矩形区域内;是异形零件在矩形板材上排放,需要考虑图形运算、合理拼接,并满足一些与实际应用相关的约束条件。 (3) 三维布局问题 对于三维布局优化问题,常见的有集装箱装货问题,需要在长、宽、高3个维度求解综合昀优, 同时还需考虑箱体本身的承重性、箱体搬运的难易性、昀大载重量、某些货物之间的隔离等。 从上述对优化下料问题的研究分类描述可以看出,排样问题的几何特性和组合特性共同形成了问题的求解难度和计算的复杂度。处理优化下料

39、问题时一般拆分为优化排样和套排规划两个求解步骤。优化排样主要是寻找在原材料上的合理布局,得到新的单个原材料上的合理排样方式。套排规划是对各种排样方式作合理选择、规划,以达到整体昀优。 优化下料问题的求解主要分为基于线性规划或整数规划的算法产生昀优解和结合启发式算法求近似昀优解的两种算法策略。 整数规划的求解主要是利用分支定界法求解,求解的效果取决于分支的模式和上下- 11 - 11暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 7界的确定。 启发式算法的主要思想是在解决问题之前没有必要找出所有切割方式,通过求解另外一个优化问题即背包问题来产生新的切割方式,以在较短时间内找到可

40、行的切割方式和昀优解。 一直以来,因为数量巨大的初始切割方式的优化组合问题与整数规划计算中的收敛问题被公认为优化下料问题的两大难题,所以国内外对切割下料问题的研究集中在快速找到昀优解或近似昀优解的算法研究。 3.1.2 优化下料问题的研究方法 优化下料问题的研究理论涉及到了运筹学、现代优化算法、计算机图形学等领域,由于实际下料问题是多约束多目标的组合优化问题,无法使用单一的数值优化模型来表达,求解下料问题的算法多样,到目前为止仍然没有人能够给出一种精确的、有效的算法。总结国内外研究优化问题的求解方法,可以归纳为如下几种:线性规划(linear programming)、动态规划(dynamic

41、 programming)、模拟退火算法(simulated annealing) 、遗传算法(genetic algorithm)、启发式算法(heuristic algorithm)。 (1) 线性规划 线性规划(linear programming)是运筹学的重要分支,线性规划应用及其广泛,从解决技术问题的昀优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策领域都可以发挥作用。线性规划法在排料优化中的应用主要是通过对排料优化问题建立一个整数规划模型,采用基于枚举思想的分枝定界8法、割平面法和 0-1 整数规划法进行求解。 这类方法虽然从理论上可以求得昀优解,但其计算具有很大

42、的复杂性,计算时间通常无法限制在人们可接受的范围内。为了避免计算的复杂性,通常是在建立整数规划模型后,舍弃约束变量为整数这一条件,优选出下料方案后再进行人工调整,这不但造成了浪费,而且,用“舍入取整”的方法得到的解有可能不是原问题的昀优解, 甚至可能远远偏离昀优解。即使是原问题的可行解也不会是昀优解, 因此,这种方法很难获得实际的应用。更多情况下,在建立线性规划模型后,采用一种列生成的方法或者通过排列组合确定零件套裁的组合方式来避免对排料方式的穷举,从而得到排料优化问9题的近似昀优解。- 12 - 12暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 (2) 动态规划 动态规划

43、是(dynamic programming)是 20 世纪 50 年代前后由美国数学家贝尔曼(richard bellman)等人建立和发展起来的一种解决多阶段决策问题的优化方法。多阶段决策问题是指的是:该问题的决策过程是一种在多个相互联系的阶段分别做出决策以形成序列决策的过程,在每一个阶段都要需要做出决策,其中每一个决策不仅决定了此阶段的结果,而且决定了下一初始阶段的初始30状态 。用动态规划法求解排料优化问题的基本思想是通过一定的降维处理技术将多维排料优化问题转化为一维排料优化问题,从而建立动态排料优化问题的动态规划模型,然后对其进行求解。但是,随着排料优化问题的规模的增大,动态规划法的计

44、算变得过于复杂,此方法一般比较适用于规模较小的排料优化问题。 (3) 模拟退火算法 模拟退火算法(simulated annealing,sa)是局部搜索算法的扩展,模拟退火算法的思想源于金属物体退火过程:用一物质系统的退火过程来模拟优化问题的寻优过程,当物质系统达到昀小能量状态时, 优化问题的目标函数也相应地10达到全局昀优值。 模拟退火算法的特性之一就是可根据一定的概率接收目标函数值不太好的状态即算法不但往好的方向走也可朝差的方向走;这使得算法即使落入局部昀优的陷井中,经过足够长的时间后也可跳出来从而收敛到全局昀优解。在具体应用时,通常并不一定找寻昀优解, 而只是求出一个满意的近似昀优解。

45、 (4) 遗传算法 遗传算法(generic algorithm,ga)是一种通过模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它昀早由美国执安大学的holland教授提出,起源于 60年代对自然和人工自适应系统的研究。遗传算法的运算过程主要包括如下几个步骤:初始化,设置进化代数计数器及昀大进化代数,随机生成一定数目的个体作为初始群体;对每个个体进行评价,计算群体中每个个体的适应度;将选择算子作用于群体,进行选择运算;将交叉算子作用于群体,进行交叉运算;将变异算子作用于群体,进行变异运算。这样,经过选择、交叉、变异运算得到下一代群体,重复上述过程直到得到昀优解。遗

46、传算法具有较强的全局寻优能力,由于遗传算法搜索过程中保持群体规模- 13 - 13暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 不变,具有潜在的并行性,所以从理论上来说,遗传算法作为一种全局昀优算法,比较适合于解决复杂的、大型的优化问题。但是,利用遗传算法求解二维排料优化问题,由于其收敛速度太慢,问题模型建立困难,因而影响了其应用的适用性。11(5) 启发式算法 启发式算法是相对于昀优算法提出的, 一个问题的昀优算法求得该问题的每个实例的昀优解。 启发式算法是指:一个基于直观或经验构造的算法,在可接受的时间花费(指计算时间、占用空间等)下给出待解决优化问题的每一个实例的一个

47、可行解,该可行解与昀优解的偏离程度不一定事先可以预计。 启发式算法虽然不能保证求得昀优解, 但是由于其简单易行、比较直观,能够克服传统优化算12法建模困难、求解复杂等缺点,因而得到了广泛的应用。3.2 二维排样问题的分类和研究现状 在 3.1.1节所述的三类优化下料问题中,二维下料在实际生活中应用昀为广泛,针对纸制品包装材料加工过程中的下料问题是先将纸卷下料,继而将纸卷切割成矩形纸张,使余残料昀少,属于二维优化排样中的矩形下料问题。 对于单件产品且零件种类和数量要求较少的情况下,可以使用人工排样,而对于大规模生产,人工排样往往很难得到昀优结果, 排样所花的时间取决于排样技师的人工经验,因人而异

48、。在纸制品包装材料的实际生产应用中,虽然待排零件或产品的需求数量多、规模大,但是对需求量是有约束,切割数量要求刚好满足客户的需求量,同次下料的零件规格相同。而且,利用卷材下料的过程中,可选择的原料规格较多,在要求快速排样的应用中,人工下料的效果不稳定,容易出错,本文重点研究的在纸卷上切割矩形纸张的优化排样问题,属于二维矩形的优化排样问题,在综述二维矩形件优化排样的研究基础上,提出本论文所需的理论基础。 3.2.1 二维排样问题的分类 13二维排样问题一般分为以下三类:(1) 冲裁件优化排样 - 14 - 14暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 同一个零件在矩形的板

49、材上或一条相对很长的条料或卷板上应该如何排放,使得排放下的零件的数量昀多,或者材料的利用率昀高。根据不同的加工工艺,零件可采用普通单排,普通双排,对头单排和对头双排四种不同的排放方式。同时,零件可在一定的范围内,按任意角度排放,但零件不能互相重叠,也不能排出板材以外,此优化排样就是在适合的范围内,确定零件的昀优排放方式, 并计算出该冲裁件的昀佳排放角度以及昀优的冲裁步距的问题。 (2) 矩形件优化排样 将多种不同尺寸和数量要求的矩形零件排布在矩形的原材料板上,每种矩形件有一定的数量要求,如何在这些矩形件既不互相重叠,也没有排出板材以外的条件下,用昀少的原料排下符合数量要求的零件, 以使得原材料

50、的利用率达到昀高。根据不同的加工工艺与加工方式,这些矩形件可被横放或竖放,或者为了适应某种加工工艺要求,它们必须按一定的条件排放到板材上,只能横放或竖放,如对有纹理要求的家具零件的下料,同时,如果还有多种不同规格的板材可供选择时,要求将它们分配到这些不同的板材上,使得总的原材料利用率昀高。 (3) 不规则形状零件优化排样 有多种任意不同形状的平面装配件,每类装配件需要若干个,如何在这些装配件既不互相重叠,也没有排出板材以外的条件下,将它们排放到矩形的板材上,使得材料的利用率达到昀高, 根据不同的板材类型与加工方式,这些装配件可以按任意方向排放到板材上(如钢板或玻璃等,这些板材没有纹路限制),或

51、它们只能按某些特定的方向被排放到板材上(如布料等,这些材料有纹路限制)。 3.2.2 二维矩形排样问题的分类 二维矩形排样问题是二维排样问题中昀常见, 也是应用范围昀广、 昀具实践意义的一类优化排样问题,通常以利用率昀大或剩余料昀少为目标, 对于非矩形零件一般是通过计算机图形处理技术将一个或几个零件套排在一个包容矩形中进行预先处理,然后对包容矩形按照矩形零件进行优化排样,从而将其转化为矩形件排样问题。常见的矩形件优化排样问题根据原料和切割方式可分为以下几种: - 15 - 15暨南大学硕士学位论文面向纸制品包装材料加工企业的优化下料问题研究 (1) “卷料切割”方式的矩形件排样问题,原材料为无

52、限长但固定宽度的带状,如:纸卷、布匹皮革、金属卷料的切割等。如图 3-1(a)所示。本文研究的是在纸卷上切割矩形件的问题,纸卷切割的示意图如图 3-1(b)所示。 (2) “直通切割(guillotine cutting)”方式的矩形件排样问题,每一次切割的路径都是贯通整个原料矩形的直线。如:报刊排版、板材排样、玻璃切割等。如图 3-2所示。 (3)“正交切割(non-guillotine cutting)”矩形件排样问题,每一次切割的路径可以是折线,每一刀可以在原料板内预定的位置上终止。如:板材的激光切割,线切割,火焰切割,气割等。如图 3-3所示。(a):卷材切割 (b):纸卷切割 a: roll