椭圆形件二维下料问题研究

作     者：彭瑶瑶 

作者单位：西华师范大学 

学位级别：硕士

导师姓名：谭代伦

授予年度：2022年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：椭圆形件 二维下料 同质条带 数学模型 遗传算法 

摘      要：二维下料问题是公认的NP-hard问题。随着经济发展,椭圆形件下料在制造业、化工业中频繁出现,求解椭圆形件二维下料问题往往需要在各式各样的原材料上切割出成品或半成品。传统的椭圆形件二维下料大多依靠人工排列,没有综合性的比较和分析,而且人工排列下料往往会造成生产时间长、切割成本大、资源浪费多的不良后果。目前也尚无文献对该类问题提出针对性的模型与算法,所以本文对椭圆形件二维下料问题的研究是具有实际生产理论指导意义的。（1）将实际问题抽象出来,将单规格椭圆形件下料问题转化为数学问题。虽然当前尚无文献对椭圆形件下料问题开展研究,但其仍然属于二维下料问题,具有二维下料问题的基本性质,所以结合椭圆形件下料的独特性与一般二维下料问题的普遍特征,考虑余料利用,建立以除去最后一块板材的原材料面积利用率为目标函数的数学模型。（2）考虑到椭圆在矩形板材上的摆放是多种多样的,先利用几何关系,构造出常见的三种排列方式:并排、品排、斜排（α=45°）,其次计算得到不同类型条带的长、宽与椭圆个数的数量关系表达式,并为其编号。此时,将切割方案表示成一串可重复且不定长的字符串形式,字符来源于前面给出的类型编号,结合切割方向和椭圆需求量就可以开始切割。根据切割方案的特点确定编码规则,采用符号编码设计遗传算法,对给定的单规格椭圆形件下料问题进行求解,最终得到浪费板材少、最后一块板材余料多且原材料面积利用率为0.8883的下料方案,实验结果表明该算法的确可用于求解此类问题,且求解效率高。（3）对于多规格椭圆形件二维下料问题,随着椭圆规格的增多,条带类型成倍增加,难度、复杂度陡然增加,首先考虑到余料与切割下料问题的特点,建立以除去最后一块板材的原材料面积利用率为目标函数的数学模型;其次以单规格椭圆形件下料的排列方式为基础,确定同质情形下的多规格椭圆形件的条带类型,再为不同类型条带计算出椭圆数量关系表达式,并为其编号,建立一个针对多种规格椭圆形件下料的符号对应表,并以此确定编码方案,设计遗传算法求解;最后实例验证,得到最后一块板材利用率低至0.2834,而原材料面积利用率为0.8813的下料方案,结果表明所建立的模型刻画准确可用,求解效率高,下料方案优,可推广至实际问题使用。