计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2014年
5期
1511-1515
,共5页
季君%邢斐斐%杜钧%师宁%崔耀东
季君%邢斐斐%杜鈞%師寧%崔耀東
계군%형비비%두균%사저%최요동
布局%同形块%动态规划%背包问题
佈跼%同形塊%動態規劃%揹包問題
포국%동형괴%동태규화%배포문제
layout%same-shape block%dynamic programming%knapsack problem
为解决大规模二维布局问题,提出一种生成同形块两阶段布局方式的确定型算法.首先通过动态规划确定最优同形块;然后求解背包问题确定同形块在同形级中的布局方式和同形级在同形段中的最优布局方式;最后选择两个同形段生成最优同形块布局方式.通过43道基准测题,将该算法与经典两阶段和三块算法进行比较.实验结果表明,该算法不仅能满足剪切工艺,在计算时间和板材利用率上优于以上算法,而且能在合理时间内取得好的优化结果.
為解決大規模二維佈跼問題,提齣一種生成同形塊兩階段佈跼方式的確定型算法.首先通過動態規劃確定最優同形塊;然後求解揹包問題確定同形塊在同形級中的佈跼方式和同形級在同形段中的最優佈跼方式;最後選擇兩箇同形段生成最優同形塊佈跼方式.通過43道基準測題,將該算法與經典兩階段和三塊算法進行比較.實驗結果錶明,該算法不僅能滿足剪切工藝,在計算時間和闆材利用率上優于以上算法,而且能在閤理時間內取得好的優化結果.
위해결대규모이유포국문제,제출일충생성동형괴량계단포국방식적학정형산법.수선통과동태규화학정최우동형괴;연후구해배포문제학정동형괴재동형급중적포국방식화동형급재동형단중적최우포국방식;최후선택량개동형단생성최우동형괴포국방식.통과43도기준측제,장해산법여경전량계단화삼괴산법진행비교.실험결과표명,해산법불부능만족전절공예,재계산시간화판재이용솔상우우이상산법,이차능재합리시간내취득호적우화결과.