论文部分内容阅读
摘要对于二维下料问题,平均利用率最大化为目标,建立数学模型,并在充分满足切断式切割方式的基础上,定义了随机决策方法和最适面积决策方法对下料方案进行决策,基于优先级和下料方案的不同组合,构造了四种结构相同的启发式算法。数据测试结果表明,四种启发式算法均可有效求解该问题,且采用面积优先级规则和最适面积决策方法实现的启发式算法效果最佳。
关键词二维下料数学模型启发式
中图分类号:TB11文献标识码:A
1 引言
实际生产中经常需要对标准尺寸原材料进行切割,以满足加工需要,称为下料问题(Cutting Stock Problem)。典型的二维下料问题可表述如下:将若干相同规格的矩形原材料切割成若干种规格的矩形零件,下料时零件的边必须分别和原材料的边平行,所有零件的厚度均与原材料一致。特别当所有零件的宽度均与原材料相等,则问题称为一维下料问题。目前通常主要涉及一些板材等的下料问题和纸张、布料等的排样问题。相关数据统计,原材料成本占总生产成本的45%～60%,而下料方案的优劣直接影响原材料的利用率,进而影响原材料成本。
本文以原材料平均利用率最大化为目标,有针对性的对二维下料问题展开研究。为方便说明,将原材料定义为母板,切割后材料定义为子板,该问题的几何约束可概括为以下四个方面:其一,母板的长边长度不可小于子板的长边长度,同时,其短边长度不可小于子板的短边长度;其二,当对母板进行切割设计时,排布于同一块母板上的所有子板,其平行于母板的长度方向的边长之和不可超过母板长度方向的边长,同时,其平行于母板的宽度方向的边长之和不可超过母板宽度方向的边长;其三,每块母板下料得到的所有子板面积之和不得超过其自身面积,并且,排布于同一块母板上的子板之间不允许存在面积上的交叠或覆盖。在该问题研究过程中,不考虑边缘切损量。
如果不考虑子板在母板上排列的几何约束,把母板看成背包,把子板看成待装包的物品,将母板面积作为背包容量,那么,该下料问题则可被归结为一类特殊的多背包问题,在运筹学和优化领域,其为经典的NP-hard问题。本文将探讨采用启发式算法和智能优化算法对其进行求解。
2 问题的数学模型描述
下面将对本文所研究的二维下料问题的特点进行详细的说明。
2.1切断式切割(Guillotine Cutting)
切断式切割,即指在母板上每次切割的轨迹均为一条边到边的连通直线,又称为“Edge to Edge”切割,如图1所示,(a)、(b)分别为非切断式切割和切断式切割的示意图,图中画有斜线的部分表示切损废板。切断式切割
为本文所研究的情况。
2.2 母板和子板规格多样化
根据实际情况,下料的母板规格可能不尽相同,生产中对于子板的需求也是如此。母板和子板的规格多样性无疑增加了问题求解的难度。
2.3同时涉及一维下料和二维下料
为了增加原材料利用率,实际操作时通常会首先下料与母板宽度(或长度)相同的子板,也就是一维下料,在此基础上,再针对剩余的母板进行二维下料。事实上,一维下料问题可以说是二维下料问题的一个特例。
2.4不限定子板在母板上的排布方式
下料时要考虑子板在母板上的排布方式,鉴于母板和子板均为矩形,本文定义了如下两种排布方式:若排布在母板上的子板的长(或宽)与母板自身的长度方向(或宽度方向)平行,则称子板为平行排布方式,如图1中的1#和4#子板;若排布在母板上的子板的长(或宽)与母板自身的长度方向(或宽度方向)垂直,则称子板为垂直排布方式,如图1 (a)中的2#和3#子板。本文所研究的下料问题仅涉及以上两种排布方式。
本文所研究的二维下料问题的数学模型及符号说明如下。
其中,为决策变量,为1表示子板j取自母板,否则为0,、分别表示母板、子板总数,、分别表示母板、子板集合,、、分别表示母板的面积、长度、宽度,、、分别表示子板的面积、长度、宽度。数学模型中,式(1)为问题的目标函数,即最大化母板的平均利用率;式(2)和(3)表达了下料过程的几何约束。
3 问题的启发式算法求解
首先对母板的下料方案和性质作如下说明及定义:
3.1下料方案
为便于问题的求解,本文规定:子板均从母板的左下角切割得到,每次切割均为切断式切割。如图2所示,每从母板的左下角切割得到一块子板,就会有两块新母板(包括面积为零的情况)产生。这里,本文要对母板切断方式作以定义:若母板的首次切断方向沿着其长度方向,则称其为上下式切断;若母板的首次切断方向沿着其宽度方向,则称其为左右式切断。
下料时,子板在母板上的排布方式最多可能有平行和垂直两种,而对于每一种排布方式,又存在两种母板切断方向。故从母板上切割一块子板最多可能有四种方案。如图3所示,本文将子板平行排布且母板左右式切断的切割类型定义为“AI型”切割,将子板平行排布且母板上下式切断的切割类型定义为“AII型”切割,将子板垂直排布且母板左右式切断的切割类型定义为“BI型”切割,将子板垂直排布且母板上下式切断的切割类型定义为“BII型”切割。
3.2母板具有方向继承性
初始状态下母板的长边和短边为其永久的长度方向和宽度方向,切割后产生的新母板具有继承性,其平行于原母板长度方向和宽度方向的各边分别为其长度方向和宽度方向。也就是说,在某些情况下,切割过程中重新产生的母板长度方向的边长可能小于其宽度方向的边长,如图2中切割产生的新母板B。
前文已经分析过无委托厚板匹配问题的特点及复杂性,其属于NP-hard问题,即其不存在多项式时间求解算法,同时作为一类多目标优化的实际问题,开发指数级时间的求解算法未免显得有些不切实际。事实上,对于这类问题通常推荐构造快速有效的启发式算法对其进行求解。
根据问题的目标及约束,并参考一些学者提出的切断式切割问题的求解方法,本文构造了求解该问题的启发式算法。其基本思想为依次完成每块母板的下料工作。基本方法为:以母板序列为基准,依次扫描子板序列中的每个子板,并根据几何约束判断当前子板从母板下料的合理性,若合理,则选择一种切割方案,在当前母板上采取切断式切割获得该子板,同时分别更新当前的母板和子板序列;由初始母板切割得到的新母板,将继续进行下料;依上述思想及方法反复针对匹配对象序列进行操作,直到当前母板序列为空时,整个算法过程结束。算法具体步骤如下:
Step 1:初始化解的集合;
Step 2:按照优先级,将母板序列和子板序列重新排序;
Step 3:LOOP1(母板序列)
LOOP2(子板序列)
判断该子板从当前母板下料的合理性;
直到找到可从当前母板下料的子板或子板序列扫描结束;
若找到可从当前母板下料的子板,则转至Step 4,否则,转至Step 6;
直到满足算法的终止准则;
输出问题的解;
Step 4:将当前合理下料的母板与子板记录到解的节点集合中;
Step 5:决策切割方案后,对母板进行切割;
Step 6:更新匹配对象序列,转至Step 3。
利用启发式求解问题过程中,存在很多关键的决策环节。
(1)优先级。很明显,序列的顺序直接反映了母板以及子板在算法执行过程中的优先级,也严重影响解的质量。若算法对母板和子板序列的扫描起始于首单元而终止于尾单元,则越是靠近首单元的母板或子板,其优先级也就越高。对于一块母板来说,其优先级越高,也就意味着其选择子板的优先权越高,同时其备选子板集合也越大。实际人工下料中,往往优先考虑一维下料。据此,本文设计了两种优先级:一是面积优先级,即将母板序列和子板序列按照面积非减和非增的顺序进行排序;二是宽度优先级,即将母板序列和子板序列按照宽度非减和非增的顺序进行排序。
(2)下料合理性判断方法。根据几何约束,主要从宽度和长度两方面来判断母板与子板匹配的合理性,即子板必须能够从母板上切割得到,也就是说,子板的长边长度不得超过母板的长边长度,同时子板的短边长度不得超过母板的短边长度。
(3)下料方案决策方法。如图3所示,下料包括“AI型”、“AII型”、“BI型”和“BII型”四种方案。本文定义了两种决策方法:随机决策方法和最适面积决策方法。
随机决策方法。决策下料方案时,随机地从四种方案中选择一种。这种方法不仅可以扩大解的搜索空间,而且比较便于实现。
最适面积决策方法。首先,以每种母板下料方案中产生的两块新母板(包括面积为零的母板)为基准,分别从子板序列中挑选可从其上下料的最大面积子板,选中的子板的面积则记为该新母板的最适面积,当然,两块新母板不能重复选择同一块子板,如果新母板的面积为零,则将其最适面积记为零;然后,分别计算每种母板下料方案中两块新母板的最适面积之和;最后,按新母板的最适面积之和最大的下料方案进行决策。
(4)序列更新方法。对当前子板序列进行扫描的过程中,若找到适合下料的子板,则依据下料方案进行切割,并更新当前的母板和子板序列。更新过程主要是将已下料母板和子板信息分别从序列中删除,同时将下料后获得的新母板(面积不为零的)按优先级插入到序列中。
若对现有的全部子板扫描过后,仍未找到适合当前母板下料的子板,此时更新操作即是将当前母板信息从序列中删除。
(5)算法终止准则。本文将母板序列或子板序列为空作为整个启发式算法结束的充分必要条件。
4 算法性能测试
如前所述,启发式算法求解二维下料问题的关键在于优先级的确定和下料方案的决策,本文分别设计了两种优先级规则和两种下料方案,两两组合后形成了四个结构相同的启发式算法。下面将对四种启发式算法进行实验并对比其性能。
本文利用计算机随机产生了涉及8种规模的模拟数据,即母板数分别为10、20、50、80、100、200、300、500的情况,每种规模产生6组数据进行测试,利用其平均结果对算法性能进行评价。母板长度在4000mm到25000mm之间,宽度在1300mm到4800mm之间;子板长度在3000mm到25000mm之间,宽度在900mm到4800mm之间;全部为均匀分布。
算法均在Visual C++ 6.0环境下采用C++语言编程实现,并在具有3.0G主频的Pentium(R)4系列CPU、1G物理内存、Windows XP操作系统的计算机上进行了性能测试。
表1为算法平均测试结果,其中,H1表示采用宽度优先级规则和随机决策方法实现的启发式算法,H2表示采用宽度优先级规则和最适面积决策方法实现的启发式算法,H3表示采用面积优先级规则和随机决策方法实现的启发式算法,H4表示采用面积优先级规则和最适面积决策方法实现的启发式算法。
关键词二维下料数学模型启发式
中图分类号:TB11文献标识码:A
1 引言
实际生产中经常需要对标准尺寸原材料进行切割,以满足加工需要,称为下料问题(Cutting Stock Problem)。典型的二维下料问题可表述如下:将若干相同规格的矩形原材料切割成若干种规格的矩形零件,下料时零件的边必须分别和原材料的边平行,所有零件的厚度均与原材料一致。特别当所有零件的宽度均与原材料相等,则问题称为一维下料问题。目前通常主要涉及一些板材等的下料问题和纸张、布料等的排样问题。相关数据统计,原材料成本占总生产成本的45%～60%,而下料方案的优劣直接影响原材料的利用率,进而影响原材料成本。
本文以原材料平均利用率最大化为目标,有针对性的对二维下料问题展开研究。为方便说明,将原材料定义为母板,切割后材料定义为子板,该问题的几何约束可概括为以下四个方面:其一,母板的长边长度不可小于子板的长边长度,同时,其短边长度不可小于子板的短边长度;其二,当对母板进行切割设计时,排布于同一块母板上的所有子板,其平行于母板的长度方向的边长之和不可超过母板长度方向的边长,同时,其平行于母板的宽度方向的边长之和不可超过母板宽度方向的边长;其三,每块母板下料得到的所有子板面积之和不得超过其自身面积,并且,排布于同一块母板上的子板之间不允许存在面积上的交叠或覆盖。在该问题研究过程中,不考虑边缘切损量。
如果不考虑子板在母板上排列的几何约束,把母板看成背包,把子板看成待装包的物品,将母板面积作为背包容量,那么,该下料问题则可被归结为一类特殊的多背包问题,在运筹学和优化领域,其为经典的NP-hard问题。本文将探讨采用启发式算法和智能优化算法对其进行求解。
2 问题的数学模型描述
下面将对本文所研究的二维下料问题的特点进行详细的说明。
2.1切断式切割(Guillotine Cutting)
切断式切割,即指在母板上每次切割的轨迹均为一条边到边的连通直线,又称为“Edge to Edge”切割,如图1所示,(a)、(b)分别为非切断式切割和切断式切割的示意图,图中画有斜线的部分表示切损废板。切断式切割
为本文所研究的情况。
2.2 母板和子板规格多样化
根据实际情况,下料的母板规格可能不尽相同,生产中对于子板的需求也是如此。母板和子板的规格多样性无疑增加了问题求解的难度。
2.3同时涉及一维下料和二维下料
为了增加原材料利用率,实际操作时通常会首先下料与母板宽度(或长度)相同的子板,也就是一维下料,在此基础上,再针对剩余的母板进行二维下料。事实上,一维下料问题可以说是二维下料问题的一个特例。
2.4不限定子板在母板上的排布方式
下料时要考虑子板在母板上的排布方式,鉴于母板和子板均为矩形,本文定义了如下两种排布方式:若排布在母板上的子板的长(或宽)与母板自身的长度方向(或宽度方向)平行,则称子板为平行排布方式,如图1中的1#和4#子板;若排布在母板上的子板的长(或宽)与母板自身的长度方向(或宽度方向)垂直,则称子板为垂直排布方式,如图1 (a)中的2#和3#子板。本文所研究的下料问题仅涉及以上两种排布方式。
本文所研究的二维下料问题的数学模型及符号说明如下。
其中,为决策变量,为1表示子板j取自母板,否则为0,、分别表示母板、子板总数,、分别表示母板、子板集合,、、分别表示母板的面积、长度、宽度,、、分别表示子板的面积、长度、宽度。数学模型中,式(1)为问题的目标函数,即最大化母板的平均利用率;式(2)和(3)表达了下料过程的几何约束。
3 问题的启发式算法求解
首先对母板的下料方案和性质作如下说明及定义:
3.1下料方案
为便于问题的求解,本文规定:子板均从母板的左下角切割得到,每次切割均为切断式切割。如图2所示,每从母板的左下角切割得到一块子板,就会有两块新母板(包括面积为零的情况)产生。这里,本文要对母板切断方式作以定义:若母板的首次切断方向沿着其长度方向,则称其为上下式切断;若母板的首次切断方向沿着其宽度方向,则称其为左右式切断。
下料时,子板在母板上的排布方式最多可能有平行和垂直两种,而对于每一种排布方式,又存在两种母板切断方向。故从母板上切割一块子板最多可能有四种方案。如图3所示,本文将子板平行排布且母板左右式切断的切割类型定义为“AI型”切割,将子板平行排布且母板上下式切断的切割类型定义为“AII型”切割,将子板垂直排布且母板左右式切断的切割类型定义为“BI型”切割,将子板垂直排布且母板上下式切断的切割类型定义为“BII型”切割。
3.2母板具有方向继承性
初始状态下母板的长边和短边为其永久的长度方向和宽度方向,切割后产生的新母板具有继承性,其平行于原母板长度方向和宽度方向的各边分别为其长度方向和宽度方向。也就是说,在某些情况下,切割过程中重新产生的母板长度方向的边长可能小于其宽度方向的边长,如图2中切割产生的新母板B。
前文已经分析过无委托厚板匹配问题的特点及复杂性,其属于NP-hard问题,即其不存在多项式时间求解算法,同时作为一类多目标优化的实际问题,开发指数级时间的求解算法未免显得有些不切实际。事实上,对于这类问题通常推荐构造快速有效的启发式算法对其进行求解。
根据问题的目标及约束,并参考一些学者提出的切断式切割问题的求解方法,本文构造了求解该问题的启发式算法。其基本思想为依次完成每块母板的下料工作。基本方法为:以母板序列为基准,依次扫描子板序列中的每个子板,并根据几何约束判断当前子板从母板下料的合理性,若合理,则选择一种切割方案,在当前母板上采取切断式切割获得该子板,同时分别更新当前的母板和子板序列;由初始母板切割得到的新母板,将继续进行下料;依上述思想及方法反复针对匹配对象序列进行操作,直到当前母板序列为空时,整个算法过程结束。算法具体步骤如下:
Step 1:初始化解的集合;
Step 2:按照优先级,将母板序列和子板序列重新排序;
Step 3:LOOP1(母板序列)
LOOP2(子板序列)
判断该子板从当前母板下料的合理性;
直到找到可从当前母板下料的子板或子板序列扫描结束;
若找到可从当前母板下料的子板,则转至Step 4,否则,转至Step 6;
直到满足算法的终止准则;
输出问题的解;
Step 4:将当前合理下料的母板与子板记录到解的节点集合中;
Step 5:决策切割方案后,对母板进行切割;
Step 6:更新匹配对象序列,转至Step 3。
利用启发式求解问题过程中,存在很多关键的决策环节。
(1)优先级。很明显,序列的顺序直接反映了母板以及子板在算法执行过程中的优先级,也严重影响解的质量。若算法对母板和子板序列的扫描起始于首单元而终止于尾单元,则越是靠近首单元的母板或子板,其优先级也就越高。对于一块母板来说,其优先级越高,也就意味着其选择子板的优先权越高,同时其备选子板集合也越大。实际人工下料中,往往优先考虑一维下料。据此,本文设计了两种优先级:一是面积优先级,即将母板序列和子板序列按照面积非减和非增的顺序进行排序;二是宽度优先级,即将母板序列和子板序列按照宽度非减和非增的顺序进行排序。
(2)下料合理性判断方法。根据几何约束,主要从宽度和长度两方面来判断母板与子板匹配的合理性,即子板必须能够从母板上切割得到,也就是说,子板的长边长度不得超过母板的长边长度,同时子板的短边长度不得超过母板的短边长度。
(3)下料方案决策方法。如图3所示,下料包括“AI型”、“AII型”、“BI型”和“BII型”四种方案。本文定义了两种决策方法:随机决策方法和最适面积决策方法。
随机决策方法。决策下料方案时,随机地从四种方案中选择一种。这种方法不仅可以扩大解的搜索空间,而且比较便于实现。
最适面积决策方法。首先,以每种母板下料方案中产生的两块新母板(包括面积为零的母板)为基准,分别从子板序列中挑选可从其上下料的最大面积子板,选中的子板的面积则记为该新母板的最适面积,当然,两块新母板不能重复选择同一块子板,如果新母板的面积为零,则将其最适面积记为零;然后,分别计算每种母板下料方案中两块新母板的最适面积之和;最后,按新母板的最适面积之和最大的下料方案进行决策。
(4)序列更新方法。对当前子板序列进行扫描的过程中,若找到适合下料的子板,则依据下料方案进行切割,并更新当前的母板和子板序列。更新过程主要是将已下料母板和子板信息分别从序列中删除,同时将下料后获得的新母板(面积不为零的)按优先级插入到序列中。
若对现有的全部子板扫描过后,仍未找到适合当前母板下料的子板,此时更新操作即是将当前母板信息从序列中删除。
(5)算法终止准则。本文将母板序列或子板序列为空作为整个启发式算法结束的充分必要条件。
4 算法性能测试
如前所述,启发式算法求解二维下料问题的关键在于优先级的确定和下料方案的决策,本文分别设计了两种优先级规则和两种下料方案,两两组合后形成了四个结构相同的启发式算法。下面将对四种启发式算法进行实验并对比其性能。
本文利用计算机随机产生了涉及8种规模的模拟数据,即母板数分别为10、20、50、80、100、200、300、500的情况,每种规模产生6组数据进行测试,利用其平均结果对算法性能进行评价。母板长度在4000mm到25000mm之间,宽度在1300mm到4800mm之间;子板长度在3000mm到25000mm之间,宽度在900mm到4800mm之间;全部为均匀分布。
算法均在Visual C++ 6.0环境下采用C++语言编程实现,并在具有3.0G主频的Pentium(R)4系列CPU、1G物理内存、Windows XP操作系统的计算机上进行了性能测试。
表1为算法平均测试结果,其中,H1表示采用宽度优先级规则和随机决策方法实现的启发式算法,H2表示采用宽度优先级规则和最适面积决策方法实现的启发式算法,H3表示采用面积优先级规则和随机决策方法实现的启发式算法,H4表示采用面积优先级规则和最适面积决策方法实现的启发式算法。