集成电路板单一下料的动态规划算法

摘要：针对集成电路板单一下料问题,提出两种动态规划算法:基本算法和改进算法,采用分支定界技术加速问题求解。将集成电路板单一下料过程分为两个阶段:第1阶段将板材剪切成相同尺寸的矩形工作板,第2阶段将工作板切成矩形单元板。优化目标为单张板材中所布局的矩形单元板数最大。改进算法利用动态规划算法的全容量特性,通过排除无潜力工作板,大幅度地缩短计算时间。实验结果表明:改进算法保证了解的最优性,使材料利用率达到最大;同时,算法求解速度快,计算时间均在0.4s以内,可以满足集成电路板制造业优化下料和网上订单系统的实时报价需要。