集成電路板單一下料的動態(tài)規(guī)劃算法

摘要：針對集成電路板單一下料問題,提出兩種動態(tài)規(guī)劃算法:基本算法和改進(jìn)算法,采用分支定界技術(shù)加速問題求解。將集成電路板單一下料過程分為兩個階段:第1階段將板材剪切成相同尺寸的矩形工作板,第2階段將工作板切成矩形單元板。優(yōu)化目標(biāo)為單張板材中所布局的矩形單元板數(shù)最大。改進(jìn)算法利用動態(tài)規(guī)劃算法的全容量特性,通過排除無潛力工作板,大幅度地縮短計算時間。實驗結(jié)果表明:改進(jìn)算法保證了解的最優(yōu)性,使材料利用率達(dá)到最大;同時,算法求解速度快,計算時間均在0.4s以內(nèi),可以滿足集成電路板制造業(yè)優(yōu)化下料和網(wǎng)上訂單系統(tǒng)的實時報價需要。