计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2009年
3期
505-512
,共8页
蒋兴波%吕肖庆%刘成城%李沫楠
蔣興波%呂肖慶%劉成城%李沫楠
장흥파%려초경%류성성%리말남
NP难问题%矩形条带装箱问题%混合算法%动态匹配启发式算法%遗传算法
NP難問題%矩形條帶裝箱問題%混閤算法%動態匹配啟髮式算法%遺傳算法
NP난문제%구형조대장상문제%혼합산법%동태필배계발식산법%유전산법
矩形条带装箱问(RSPP)是指将一组矩形装入在一个宽度固定高度不限的矩形容器中,以期获得最小装箱高度.RSPP理论上属于NP难问题,在新闻组版、布料下料以及金属切割等工业领域中有着广泛的应用.为解决该问题,采用了一种混合算法,即将一种新的启发式算法--动态匹配算法--与遗传算法结合起来.混合算法中,动态匹配算法能根据4类启发式规则动态选择与装填区域相匹配的下一个待装矩形,同时将装箱后所需容器高度用遗传算法的进化策略进行优化.时2组标准测试问题的计算结果表明,相对于文献中的已有算法,提出的算法更加有效.
矩形條帶裝箱問(RSPP)是指將一組矩形裝入在一箇寬度固定高度不限的矩形容器中,以期穫得最小裝箱高度.RSPP理論上屬于NP難問題,在新聞組版、佈料下料以及金屬切割等工業領域中有著廣汎的應用.為解決該問題,採用瞭一種混閤算法,即將一種新的啟髮式算法--動態匹配算法--與遺傳算法結閤起來.混閤算法中,動態匹配算法能根據4類啟髮式規則動態選擇與裝填區域相匹配的下一箇待裝矩形,同時將裝箱後所需容器高度用遺傳算法的進化策略進行優化.時2組標準測試問題的計算結果錶明,相對于文獻中的已有算法,提齣的算法更加有效.
구형조대장상문(RSPP)시지장일조구형장입재일개관도고정고도불한적구형용기중,이기획득최소장상고도.RSPP이론상속우NP난문제,재신문조판、포료하료이급금속절할등공업영역중유착엄범적응용.위해결해문제,채용료일충혼합산법,즉장일충신적계발식산법--동태필배산법--여유전산법결합기래.혼합산법중,동태필배산법능근거4류계발식규칙동태선택여장전구역상필배적하일개대장구형,동시장장상후소수용기고도용유전산법적진화책략진행우화.시2조표준측시문제적계산결과표명,상대우문헌중적이유산법,제출적산법경가유효.
