基于混合整数数学规划的方形件产品排样优化研究

Research on Square Piece Products Layout Optimization Based on Mixed Integer Mathematical Programming

摘要: 本文针对方形件产品的排样优化问题，提出了一种基于混合整数数学规划的解决方案。首先，通过建立混合整数数学规划模型，考虑了产品项的高精度和高自由度，以及需要满足的三阶段切割需求，制定了相应的约束条件。在算法实现过程中，通过对数据集的预处理，使得宽度相似的产品项能够按顺序输入，以满足齐头切的要求。针对二维三阶段切割下料问题，使用混合遗传算法和BL算法等进行编码建立混合数学整数规划模型以及相应的约束条件，并通过多次试验得到了较好的排样方案，实现了高效的板材利用率，分别达到81.903%，81.249%，84.575%以及85.246%。实验结果表明，所提出的方法均取得了显著的优化效果，为方形件产品的生产提供了有效的排样方案。

Abstract: This paper proposes a solution based on mixed integer mathematical programming for the layout optimization problem of square piece products. First, by establishing a mixed integer mathematical programming model, taking into account the high precision and high degree of freedom of the product items, as well as the three-stage cutting requirements that need to be met, the corresponding constraints are formulated. During the implementation of the algorithm, through preprocessing of the data set, product items with similar widths can be input in order to meet the requirements of simultaneous cutting. Aiming at the problem of two-dimensional and three-stage cutting and blanking, a hybrid mathematical integer programming model and corresponding constraints were established using hybrid genetic algorithms and BL algorithms for coding. A better layout plan was obtained through multiple experiments and an efficient layout was achieved. The plate utilization rates reached 81.903%, 81.249%, 84.575% and 85.246% respectively. Experimental results show that the proposed methods have achieved significant optimization effects and provide an effective layout scheme for the production of square piece.

1. 引言

智能制造目前已成为世界制造产业中的主流，也是我国的产业发展的主要目标。随着需求多样化和产品更多的个性化定制，在机械制造中需要的不再是以往的高重复度简单化零件和产品，更多的是根据个性化定制能够使用同一台机器制造出不同种类的产品，在保证质量的同时用更短的设计周期来完成生产。这需要的就是智能化在产业中的应用，系统生命周期、互联互通的服务模式等已经成为目前企业在智能制造转型中的主要竞争点。在实际生产过程中有许多产业链都需要用到智能制造，例如电子零件、玻璃分割、机械部件、板材加工等。对于此类产品，客户可能提出的产品需求多种多样、订单大小无法预测且产品质量要求高。所以需要企业有高效快速的“个性化方法”来满足顾客的需求，且机器具有此等高精度和高自由度的能力[1]。

本文所提到的方形件产品一般是以板材为主要原片、通过二维加工后(例如切割)的多种配件组合形成的一类产品。常见方形件产品一般出现在计算、通讯、消费电子、板式家具、玻璃、钣金件等行业，多采用“多品种小批量”的个性化定制生产。需要生产组织通过订单组批和排样优化的模式提高原材料的利用率，并对不同的批次进行分拣和合并，以保证生产时间上的高效。

上述个性化定制生产模式中的订单组批与排样优化至关重要，订单组批是将不同订单组成若干批次，实现订单的批量化生产。在对小批量、多品种、大规模的订单进行组批生产时，如果组批批次太小，材料利用率低，生产效率低；如果组批批次太大，材料利用率会提高，但订单交货期得不到保证，订单分拣难度提高，生产效率降低，缓冲区容量不足而造成堵塞等，需要解决个性化与生产高效性之间的矛盾。排样优化本质上是一个下料问题(也称切割填充问题)，优化的目的是合理规划方形件在板材上的布局，以减少下料过程中存在板材浪费，简化切割过程。此类问题是一种计算复杂度很高的组合优化问题，也是运筹学中的一个重要分支。下料作为众多制造企业生产链中产品及零部件生产的第一道工序，消耗的材料和资源不容小视，如何提高材料利用率，降低原材料消耗，是企业减少资源和能源浪费，承担环境责任所要解决的关键问题。

随着制造业的发展和技术的进步，方形件产品在各个领域的应用日益广泛。方形件产品通常以板材为主要材料，通过切割加工后形成各种具有个性化需求的产品。然而，如何有效地利用原板材，提高板材利用率，成为了制造企业面临的一项重要挑战。传统的排样方法往往存在板材利用率低、加工效率低下等问题，无法满足现代生产的需求。

针对这一问题，本文提出了一种基于混合整数数学规划的方形件产品排样优化方法。首先，我们建立了混合整数数学规划模型，考虑了产品项的高精度和高自由度，以及需要满足的三阶段切割需求，并制定了相应的约束条件。利用混合遗传算法和BL算法等进行编码，通过多次试验得到了较好的排样方案，实现了高效的板材利用率。引入组批优化策略，采用Kmeans++聚类算法对订单进行分组，进一步提高了板材利用率。实验结果表明，所提出的方法在数据集中均取得了显著的优化效果，为方形件产品的生产提供了有效的排样方案。本文的研究对于提高制造企业的生产效率、降低生产成本具有重要的理论意义和实际应用价值。

2. 研究背景

2.1. 模型背景

在个性化的生产模式中，订单组批与排样优化是两个非常重要的环节，订单组批是将不同订单组成若干批次，实现订单的批量化生产。在这之中需要考虑的因素非常多，本文仅考虑订单交货期、材料利用率、生产效率等约束，以此来保证交货期相近且具有相同材质的产品尽量在同一个生产批次。批次的定义为完成若干订单全部任务且不含任何不完整订单任务的订单集合。

排样优化的本质是一个下料问题，也称切割填充问题，根据同批次内产品的尺寸与数量，进行充分的排样优化，以此达到最大化板材原片利用率。其中切割要求即齐头切方案以及切割阶段数规定可在建模过程进行统筹约束考虑，并在程序中有所体现[2]。本文的排样方式为齐头切约束，即每次直线切割使得板材分成两块，不可在中间随意分割。齐头切示意图如图1所示。本文的优化目的是通过建立数学模型对原板材进行最优规划布局，以减少切割过程中对原材料的浪费，并且将切割阶段控制在3次及以下。

Figure 1. Diagram of the guillotine cut

图1. 齐头切示意图

对于原材料的切割方式有许多，本文已明确使用齐头切的方式，且以精确方式进行分割，切割的阶段数规定小于等于3，即在三个阶段内切割出准确尺寸的方形件。三阶段排样方式是一种特殊且操作便捷的排样方式[3]，符合日常生产要求，以板材使用数量最少为目标，并在原材料大小和所给数据集所具有数据特点的约束下进行编程，建立混合整数规划模型。针对二维剪板下料问题等大规模组合问题混合整数规划(MIP)是一种速度快，精度高的求解途径，同时包含整数变量和连续变量的数学规划[4]。在图2中可看到三阶段精确排样方式主要有两种类型：三阶段匀质排样方式(3E)、三阶段同质排样方式(3H) [5]。其中左图为三阶段匀质排样方式，右图为三阶段同质排样方式。

Figure 2. Diagram of three-stage precise layout methods

图2. 三阶段精确排样方式示意图

在实际切割过程中，第一刀可能垂直于长边，也可能垂直于短边，如图3所示。

Figure 3. Diagram of actual cutting

图3. 实际切割示意图

可见，第1阶段的横向切割生成模块称之为条带，如Stripe 1和Strip 2；第2阶段纵向切割生成模块称之为栈，如Strip 1继续被切割分成Stack 1、Stack 2和Stack 3；第三阶段横向切割生成模块称之为产品项，如Stack 1继续被切割分成Item 1、Item 2和Item 3。

2.2. 模型假设及符号说明

对于待切割的对象成为产品项，产品项的方向可以是固定的，也可以是旋转的，在一个条带中有一个或多个产品项相邻排列组成。条带一般分为三种类型：同质条带、匀质条带和普通条带。如图4所示，同质条带中的产品项均为相同长宽，匀质条带中要包含的是相同宽度的产品项，普通条带中的产品项没有任何限制。当约束条件仅为切割方法为齐头切且阶段数小于等于3的条件下，可以看出选择同质条带和匀质条带是最合适的，使得板材利用率提高，对后续满足三阶段切割是非常有效的途径[6]。

Figure 4. Diagram of different types of strips

图4. 不同条带类型示意图

对于本文将有以下假定：

1) 在切割过程种只考虑齐头切的切割方式(直线切割、切割方向垂直于板材一条边，并保证每次直线切割板材可分离成两块)；

2) 切割阶段数 ≤ 3，同一个阶段切割方向相同；

3) 排样方式为精确排样；

4) 假定板材原片仅有一种规格且数量充足；

5) 不考虑锯缝宽度(即切割的缝隙宽度)影响。

表1为本文建立模型中的符号说明：

Table 1. Symbol description

表1. 符号说明

符号	说明	单位
N	每次精确排样使用原板材的数量	4
L	原板材的长度为2440 cm	3
W	原板材的宽度为1220 cm	6
m	待排样的产品项数量	3
i	产品型号$i\in I,I=\left\{1,2,\cdots ,m\right\}$	3
$l_{i{s}_i}$	产品型号为i的产品项的长度	3
$s_i$	产品型号为i的长度不同类型种类	3
$w_i$	产品型号为i的产品项的宽度
K	排样方式的数量
P	排样方式的集合
$a_{ij}$	每种排样方式中所含的i型产品项数量
$x_j$	排样方式的使用频率
$Z_p$	p批次的订单中耗用的板材数量
$a_i$	排样方式中所包含的i型产品项的数量
$v_i$	i型产品项的面积
$r_i$	i型产品项的当前剩余需求量
$M_{\text{item}}^p$	p批次中产品项的数量
$A_{\text{item}}^i$	第i块板材中产品项所占用的面积

3. 模型的建立及求解

3.1. 遗传算法

遗传算法(Genetic Algorithm, GA)起源于对生物系统所进行的计算机模拟研究，是一种借鉴自然选择思想和自然遗传机制的随机全局搜索优化算法。GA模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任一初始种群出发，通过随机选择、交叉和变异操作，产生一群更适合环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代不断繁衍进化，最后收敛到一群最适应环境的个体，从而求得问题的优质解。

GA类似于自然进化，通过作用于染色体上的基因寻找好的染色体来求解问题 。遗传算法对求解问题本身一无所知，它仅仅需要评价算法所产生的每个染色体，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。

在GA中，问题的每个有效解被称为一个“染色体”，也称为“串”，对应于种群中的每个生物个体。染色体的具体形式是一个使用特定编码方式生成的编码串，编码串中的每一个编码单元称为“基因”。

GA通过比较适应值区分染色体的优劣，适应值越大的染色体越优秀。评估函数用来计算并确定染色体对应的适应值。选择算子按照一定的规则对种群的染色体进行选择，得到父代种群。一般情况下，越优秀的染色体被选中的次数越多。交叉算子作用于每两个成功交配的父代染色体，染色体交换各自的部分基因，产生两个子代染色体。子代染色体取代父代染色体进入新种群，而没有交配的染色体则直接进入新种群。变异算子使新种群进行小概率的变异。染色体发生变异的基因改变数值，得到新的染色体。经过变异的新种群替代原有种群进入下一次进化。

表2列出了生物遗传概念在GA中的对应关系。

Table 2. Correspondence between biological genetic concepts in GA

表2. 生物遗传概念在GA中的对应关系

生物遗传概念	GA中的对应关系
适者生存	算法停止时，最优目标值的解有最大的可能被留住
种群	根据适应度函数值选取的一组解
个体	一个有效解
染色体	解的编码
基因	染色体上的编码单元
适应性	适应度函数值
交配	通过交配原则产生一组新解的过程
变异	编码的某一分量发生变化的过程
进化结束	算法满足终止条件时结束，输出全局最优解

在GA中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传操作后的个体集合形成下一代新的种群。再对这个新种群进行下一轮进化。

一般GA的主要步骤如下：

Step 1初始化：初始化规模为N的种群，其中染色体每个基因的值采用随机数产生器生成并满足问题定义的范围。当前进化代数为0。

Step 2个体评价：用评估函数对种群中所有染色体进行评价，分别计算每个染色体的适应值，保存适应值最大的染色体Best。

Step 3选择运算：采用轮盘赌选择运算对种群的染色体进行选择操作，产生规模同样为N的种群。

Step 4交叉运算：按照概率从种群中选择染色体进行交叉运算。两两父代染色体交换部分基因，产生两个新的子代染色体，子代染色体取代父代染色体进入新种群。没有进行交叉的染色体直接复制进入新种群。

Step 5变异运算：按照概率对新种群中染色体的基因进行变异操作。发生变异的基因数值发生改变。变异后的染色体取代原有染色体进入新种群，未发生变异的染色体直接进入新群体。

Step 6循环操作：变异后的新种群取代原有种群，重新计算种群中各个染色体的适应值。倘若种群的最大适应值大于Best的适应值，则以该最大适应值对应的染色体替代Best，即更新最大适应值大于Best。

Step 7终止条件判断：当前进化代数加1。如果进化代数超过规定的最大进化代数或Best达到规定的误差要求，算法结束，Best可表示问题的一个解；否则返回Step 3。

GA具体计算流程如图5所示。

Figure 5. Flow chart of GA’s specific calculation

图5. GA具体计算流程图

3.2. 模型建立

方形件产品排样优化问题可描述为：待切割的板材原片尺寸为$L\times W$ ，且库存数量充足，令宽度相同的产品项为“同一种类型”的产品项，则待排样的产品项有m种，其中同一类型的产品项长度不一定相同，长、宽及需求量分别为$l_{is},w_i,d_i$ ，其中i为产品型号，$i\in I,I=\left\{1,2,\cdots ,m\right\}$ ，$s_i$ 为i型产品长度不同类型种类。本文旨在求出一个最优的二维三阶段排版方案，即排完全部需求产品项所使用的板材原片数量最少。

以板材用量最少为目标的二维三阶段剪切下料问题，可用数学模型(3.1)表示，

$\begin{array}{l}\min z={\displaystyle \sum _{j=1}^K{x}_j}\\ s.t.\{\begin{array}{l}{\displaystyle \sum _{j=1}^K{a}_{ij}{x}_j=d_i,i=1,2,\cdots ,m}\\ x_j\in N,j=1,2,\cdots ,K\end{array}\end{array}$ (3.1)

该问题的求解需要确定排样方案的排样方式集合种所包含的K种排样方式：$P=\left\{p_1,p_2,\cdots ,p_k\right\}$ ，明确每种排样方式中所含的i型产品项数量$a_{ij}$ 、排列位置和顺序，确定排样方式的使用频率$x_j$ ，$i=1,2,\cdots ,m,j=1,2,\cdots ,K$ 。其中$x_j$ 是整型决策变量。

三阶段剪切下料问题的解是由3E排样方式组成的三阶段排样方案[7]。在此问题中，3E排样方式是有约束三阶段排样问题的解。因此约束三阶段排样问题又称为子问题。下料问题本身又称为主问题。子问题的3E排样方式生成的算法作为3E排样方案的子算法，需要不断地重复调用，产生多个不同的3E排样方式组合，才能排完全部需求产品项，得到一个3E排样方案。因此，排样方案的优劣不仅与主问题的求解框架有关，而且严重依赖子问题的排样方式生成算法。

子问题是约束三阶段排样问题：寻找产品项在板材上的3E排样方式，最大化板材中所包含的产品项总面积，而所包含产品项的数量不能超过其剩余需求量。

约束问题可用数学模型(3.2)表示，

$\begin{array}{l}{Z}_p=\max {\displaystyle \sum _{i=1}^m{a}_i{v}_i,P\in 3E}\\ s.t.a_i\le r_i,a_i\in N,i=1,\cdots ,m\end{array}$ (3.2)

其中，$Z_p$ 为3E排样方式的价值，$a_i$ 为排样方式中所包含的i型产品项的数量，$v_i$ 为i型产品项的面积，$r_i$ 为i型产品项的当前剩余需求量。其中，$i=\left\{1,\cdots ,m\right\}$ 。

3E排样方式由同向条带组成，条带中包含同向堆，限制同一堆上只排入“同种类型”同方向的产品项，有利于简化切割操作。第一阶段一次性把板材剪切成多个条带，第二阶段可将条带剪切成多个堆，第三阶段剪切出产品项。

3.3. 模型求解

对于以上混合整数规划模型，本文采用混合GA求解，用GA确定产品项的排列次序，对应GA中的基因序列，对种群中的染色体进行进化操作，最终选择最好的染色体序列。

采用十进制编码方法对产品项进行固定编码。每个基因对应一个产品项，对需求多于一个的产品项采用重复编码的方式，全部产品项的一个排列称为一个染色体。即将每一矩形进行编号$i=\left\{1,2,\cdots ,m\right\}$ 。零件编号构成一个整数串$p=\left\{p_1,p_2,\cdots ,p_n\right\}$ ，其中，$p_i\le n$ 。该整数串表示了一种排样图，即为一个解。其中，每一位整数代表一个矩形，并且每一位整数可以有正负之分，正号表示零件不发生旋转，负号表示将零件旋转90度。一个整数串就是一个染色体，每一个染色体对应一种排样图，m个染色体构成一个种群。

对于给定的序列，采用启发式算法得到一个排样方案。以矩形带的宽度方向为x轴，高度方向为y轴建立坐标系，使用一种基于递归方式的启发式方法设计解码方式。

首先将排样图划分为多个条带，条带的高度等于该条带第一个产品项y项的高度，所有条带的高度总和即为板材的高度。每一个条带分成多个栈，栈的长度等于第一个产品项放置后x向的宽度，栈的高度等于栈中所有产品项高度之和，并要求其不超过所属条带的高度，栈中任何一个产品项的高度都不超过栈的高度。排样时按当前染色体指定的顺序，逐一将产品项放到板材中。如果当前栈中放不下，就创建一个新栈；如果当前条带中放不下，就创建一个新条带。

用$l_k$ 和$w_k$ 表示当前染色体第k个基因对应产品的长度和宽度，$k=\left\{1,2,\cdots ,K\right\}$ ，其中，$K={\displaystyle \sum _{i=1}^n{d}_i}$ 。解码算法描述如下：

Step 1初始排放：令$k=1$ ，将$R_i$ 从右上角输入先向下，再向左移动放置在矩形带的左下角，然后将$R_i$ 沿着y轴方向的高度作为第一个条带的高度划分出来，x轴方向的长度为该条带的第一个栈的宽度，令$k=k+1$ ，跳转至Step 2；

Step 2栈的创建和排放：按照染色体的序列排放下一个产品项$R_i$ 。

Step 2.1若$k>K$ ，跳转至Step 4。否则跳转至Step 2.2。

Step 2.2若可以排放在该栈上，令$k=k+1$ ，跳转至Step 2.1。否则跳转至Step 2.3；

Step 2.3该条带剩余的空间若可以排放$R_i$ ，则在该条带创建一个新栈并放置$R_i$ ，记新栈宽度为R排放之后x轴方向的宽度，令$k=k+1$ ，跳转至Step 2.1；否则跳转至Step 3；

Step 3创建一个新的条带：若$l_i\ge w_i$ ，$R_i$ 为自然方向排放，记录新条带高度为$R_i$ ，排放后y轴方向的高度值，令$k=k+1$ ，若$k<K$ ，跳转至Step 2.3，否则跳转至Step 4。

Step 4终止并输出最优排样方式。

根据上述解码之后，对于给定的染色体序列均可得到一个确定的排样方案。

遗传算法的进化方向是通过对排样方案的目标函数值的估价来引导的，最终结果是得到最优解或者接受当前解。在本题问题中，我们的目标是寻找带长度最小的排样方案$P$ 。当两个排样方案长度值相同时废料率越小表明适应度越好，故定义适应度函数如下，

$F\left(p\right)=H-\frac{1}{\left|J\right|}{\displaystyle \sum _{j\in J}\frac{l_j\text{waste}}{l_j\text{high}\times w}},J\subset \left\{1,2,\cdots ,L\right\},\left|J\right|＜\frac{L}{2}$ (3.3)

其中，H是当前排样方案P对应的带长度值，L为方案P对应的层数，从P中选择一部分浪费率较大的

层组成集合J，其大小为$\left|J\right|$ 为第J层的废料率，其中$\frac{l_j\text{waste}}{l_j\text{high}\times w}$ 为j层的废料，即为不可继续利用的空间

和，$l_j\text{high}$ 为j层的高度。

4. 模型评价

4.1. 实验结果

模型的最终效果如表3所示，由数据可以得知方形件产品排样优化利用率稳定在80%以上，效果较好。

Table 3. Result indicator table

表3. 结果指标表

数据集	板材利用率
A1数据集	81.903%
A2数据集	81.249%
A3数据集	84.575%
A4数据集	85.246%

4.2. 模型优缺点

GA将问题的可行解构成种群把每一个可能的解看作种群的个体运行时算法在整个解空间内随机搜索按一定的评估策略或适应度函数对每一个个体作出评价不断地使用选择、交叉、变异这三种遗传算子使问题的解不断进化直至产生最优解。因为GA在解决大空间、非线性全局寻优等复杂问题时比起传统方法有独特的优越性，所以得到了广泛的研究和应用。与传统优化方法相比，GA的优越性主要体现在如下方面：

1) GA仅仅利用个体的适应度进行群体的进化，不需要优化模型中目标函数和约束函数的导数信息，因而具有极强的鲁棒性，适合解决各种优化问题。

2) GA利用设计变量编码在设计变量空间进行多点搜索，突变算子能避免交叉繁殖收敛于局部优良个体，并保持群体搜索的多样性，这些确保了遗传算法具有更强的全局寻优能力。

3) 此外由于GA搜索过程中保持群体规模不变，因而具有潜在的并行性，所以适合解决复杂的、大型的优化问题。

GA有两个明显的缺点：

1) 出现早熟往往是由于种群中出现了某些超级个体，随着模拟生物演化过程的进行，这些个体的基因物质很快占据种群的统治地位，导致种群中由于缺乏新鲜的基因物质而不能找到全局最优值；

2) 由于GA中选择及杂交变异等算子的作用，使得一些优秀的基因片段过早丢失，从而限制了搜索范围，使得搜索只能在局部范围内找到最优值，而不能得到满意的全局最优值[8]。