陈 燕， 刘 咏， 谢琪琦， 崔耀东

(1. 广西大学计算机与电子信息学院，广西 南宁 530004；2. 华南理工大学工商管理学院，广东 广州 510640)

基于梯形和平行四边形的圆片剪冲下料算法设计与实现

陈 燕1,2， 刘 咏1， 谢琪琦1， 崔耀东1

(1. 广西大学计算机与电子信息学院，广西 南宁 530004；2. 华南理工大学工商管理学院，广东 广州 510640)

提出一种在矩形板材上引入梯形条带来进行排样的方法，首先用两条平行的分界线将板材分为两个大小一致的直角梯形段和一个平行四边形段，分别采用递归算法和动态规划算法确定梯形段和平行四边形段中条带的最优组合，从而确定最优排样方式；再结合线性规划算法解决圆片下料问题，使得整个下料方案的材料利用率最大化。最后采用大量随机生成的例题进行实验，实验结果表明该算法能有效提高材料利用率。

圆片排样；剪冲下料；平行四边形条带；梯形条带

随着资源和能源危机的出现，要求各企业不断提高原材料利用率、减少切割能源消耗，于是研究下料利用率高且切割工艺简单的布局优化算法，切割与装填布局(cutting and packing, C&P)[1]问题越来越受到各制造企业的关注。特别地，圆片下料问题广泛存在机械制造、电机、船舶、航空航天等行业中，例如：电机定子和转子铁心是用硅钢圆片制作而成；家居的锅、壶、盆是用不

锈钢圆片制作的，等等。这些行业每年消耗的金属板材量达千万吨，且原材料费用占生产成本的60%以上，因此提高材料利用率能够为企业带来非常可观的经济效益。……