智能优化排样技术及其应用

第1章 绪论 1.1 引言 排样问题也称为排料问题、套料问题，或二维装箱问题，国外也将其称为下料问题(cutting stock problem)，是指在给定的板材区域内找出待排零件的非重叠*优排布方案，使得材料利用率*高，或者浪费的材料*少。排样与切割问题广泛存在于机械、船舶、电气、轻工等行业中需要使用板材类原材料的生产加工领域，表1.1列出了排样问题的一些主要应用领域。通过排样优化可以提高材料利用率，减少材料浪费，从而带来巨大的社会效益和经济效益。因此，对优化排样技术的研究和应用开发一直是学术界和工业界关注的重点问题之一。 表1.1排样问题的主要应用领域 我国提出的“中国制造2025”战略中，以提高产业自动化程度、减少资源消耗为目标，并将单位国内生产总值能耗下降3.1%作为当年经济社会发展的主要目标任务之一。应用优化排样技术一方面可以降低员工劳动强度，大大提高排样效率和材料利用率，帮助企业缩减成本，从而带来可观的经济效益，另一方面也支持了绿色制造理念。通过智能优化排样，材料利用率即使有1%的提高，也会为企业节约大量成本，为全社会带来巨大的社会效益和经济效益。以机械制造业为例，我国是制造大国，也是各类钢材的消耗大国。据产业信息网提供的统计信息[ZYB1][d2]①，我国钢材消耗量每年增长接近10%，2017年钢材消耗量达7亿t，2018年前三季度钢材产量为8.2亿t，其中钢板占了大部分比重。尤其在工程机械、机车、船舶、桥梁等以钢结构件制造为主的重工业，钢板消耗量巨大。如何通过智能优化排样来提高钢板利用率以减少钢板消耗，不仅对降低这些行业的制造成本、提高经济效益具有重要意义，而且对于全社会的节材降耗和节能减排都具有十分重要的意义。 1.2 排样问题分类 Wscher等[1]从排样维度、零件种类、原材料种类、零件形状、工艺约束等角度对排样问题进行了总结与归纳，如图1.1所示。根据该分类法则，纵向上将排样问题按排样维度划分为一维排样问题、二维排样问题、三维排样问题和多维排样问题，横向上将排样问题按其在实际工程应用中的特点又分别按排样零件种类、原材料种类、零件形状、工艺约束等多种维度划分成多个变种问题。在排样问题的研究中，将其按排样维度、零件形状、工艺约束来分类得到比较广泛的认可。 图1.1 排样问题分类 1.2.1 按排样维度分类 按排样维度，可将排样问题分为一维排样问题、二维排样问题、三维排样问题及多维排样问题。 1.一维排样问题 一维排样也称为线材排样，是指给定一定数量和长度规格的线材(如管材或型材)，要求从线材长度方向切割出一定数量和种类的毛坯(各类毛坯的长度不一，数量要求也不同)，如何进行优化排样，即确定各个毛坯在各根线材上的切割顺序，使消耗的线材总长度*少。 例如，给定根数不限的一批管材，其长度均为10m，现需要从上述管材中切割出一批长度分别为4m、3m和2m的三种毛坯，各种毛坯的数量分别为10件、20件、30件，通过优化排样确定这60件毛坯在每根用到的管材上的切割顺序，使消耗的管材总长度(或数量)*少。上述线材排样问题示意图如图1.2所示。 图1.2 线材排样问题示意图 2.二维排样问题 二维排样也称为板材排样，是指将若干二维平面形状的零件以一定的顺序并在合适的位置及角度方向依次排布于板材内部，排布的每个零件之间互不重叠且完全包含于板材区域之内，使得排样后的所有零件占用的板材总面积*小，即板材利用率*大。图1.3是一批二维异形零件在一张矩形板材内的二维排样示意图。 图1.3 板材排样示意图 二维排样是在生产实践中*广泛存在的一类排样问题，例如，生产制造中常见的金属板材切割下料、服装布料裁剪、皮革裁剪、板式家具开料等裁切加工都属于二维排样问题。显然，由于零件几何形状上的复杂性，二维排样问题比一维排样问题的求解难度更大，特别是对复杂不规则图形的二维排样一直以来都是学术界研究的热点问题之一。本书讨论二维排样问题。 3.三维排样问题 三维排样也称为装箱排样，近年来越来越受到学术界和工业界的重视。三维排样问题是指在一个给定的有限三维空间内，对于给定的若干三维形状的零件，确定每个零件的放置顺序、放置位置及方位，使得这些零件所占用的总空间*少。三维排样问题的典型应用场景是物流行业中的集装箱*大化装填问题。图1.4是装箱排样过程示意图。 图1.4 装箱排样过程示意图 除此之外，还有考虑除长宽高三维尺寸之外更多维度的排样问题，一般统称为多维排样问题。例如，航天飞机驾驶舱的仪器仪表布局问题，不仅需要考虑空间布局的紧凑性，还要考虑载重量、重心、稳定性、可拆卸等其他多个维度的问题，是一类典型的多维排样问题。 1.2.2 按零件形状分类 排样问题按排样零件的形状特点，可以分成两类：规则形状排样问题与不规则形状排样问题。其中，一维规则形状排样的零件的截口形状为直口，一维不规则形状排样的零件的截口形状为非直口异形；二维规则形状排样的零件形状为矩形，又称矩形排样或矩形件排样，二维不规则形状排样的零件形状为异形(或任意多边形)，且板材形状也可为异形，又称异形排样或异形件排样；三维规则形状排样的零件形状为直方体，三维不规则形状排样的零件形状为三维异形体，且三维装填空间也可为异形非直方体。本书讨论二维排样中的矩形排样问题及异形排样问题。 1.矩形排样问题 矩形排样问题可以描述为：设一组数量为n的待排样矩形零件为R1， R2， ， Rn，零件编号遵循有序自然序列，且零件之间有强互异性。每个矩形零件的宽高尺寸都确定，设第i(i=1，2， ， n)个零件的宽为wi，高为hi，则第i个零件Ri可以表示为(wi， hi)[ZYB3][d4]。将R1， R2， ， Rn按照某一序列排放到一定规格的矩形板材上，目标是使矩形板材的利用率*大，且在排样过程中需要满足以下约束条件： (1)矩形零件需完全放入板材边界内； (2)排放入板材边界内的矩形零件不相互重叠； (3)矩形零件可以翻转90°或者不能翻转90°； (4)板材内部矩形零件的边与板材边界平行。 矩形排样根据板材规格情况又可分为定长定宽的二维矩形装箱排样问题，以及定宽不定长的二维矩形带排样问题。在矩形不能排满板材的情况下，这两类排样问题是等效的。图1.5为一组20个矩形件的矩形排样示例，图中的每个矩形大小都不相同，且每个矩形在排样过程中不能翻转90°。 图1.5 矩形排样示例 矩形排样问题按工艺约束可进一步划分为一刀切(guillotine cutting)矩形排样问题和自由切(free cutting)矩形排样问题。一刀切也称为通裁通切或通裁通剪，是指由板材的一端沿直线方向(通常是沿水平或垂直方向)贯通切割或裁剪至另一端。自由切则无此限制，刀具可以沿着矩形边界自由切割。一刀切是板材切割中的一种常见工艺，广泛存在于板式家具开料、玻璃切割、金属薄板裁剪等加工中。图1.6是一刀切和自由切两种矩形排样情况的对比示例。 图1.6 一刀切和自由切两种矩形排样对比示例 2.异形排样问题 异形排样问题可以描述成将一组任意二维平面图形(简称异形件或零件) P1，P2， ， Pn以合理的次序和方位角排放在矩形或异形板材S上的适当位置，使板材利用率*高，同时满足如下约束条件： (1)异形件Pi、Pj互不重叠(i≠j)； (2)Pi必须完全包含于板材S内； (3)异形件不能旋转或可在一定角度范围内旋转。 图1.7 为一组20个异形件在矩形板材内的排样示例，其中每个异形件可以任意旋转。图1.8为板材为异形时的排样示例。 图1.7 板材为矩形时的异形排样示例 图1.8 板材为异形时的排样示例 异形排样问题的计算复杂度与求解难度远远高于矩形排样问题。相比矩形排样，异形排样时每个零件的可选位置和方位角可在一定范围内连续变化，其搜索空间远大于矩形排样。 排样问题是一个典型的组合优化问题，广泛存在于生产实践中，因此排样下