CAJ | 학술논문

讨论一维下料问题,对原有的基于顺序价值修正的启发式算法进行改进.每次使用动态规划算法求解当前最优排样方式的背包问题,保存多个价值最优的排样方式提供给 SHP 算法选择,修改对应的回退算法,提高算法的计算效率.综合考虑材料利用率和可重复次数,优先选择有利于后面排样方式生成的排样方式.在记录下的大量较优结果中,最终选取满足需要的排样方案进行使用.在计算过程中,结合多线程技术,进一步提高计算效率.实验结果表明,改进后的算法能够有效地提高材料利用率,简化切割方式,在计算时间上优势明显.
토론일유하료문제,대원유적기우순서개치수정적계발식산법진행개진.매차사용동태규화산법구해당전최우배양방식적배포문제,보존다개개치최우적배양방식제공급 SHP 산법선택,수개대응적회퇴산법,제고산법적계산효솔.종합고필재료이용솔화가중복차수,우선선택유리우후면배양방식생성적배양방식.재기록하적대량교우결과중,최종선취만족수요적배양방안진행사용.재계산과정중,결합다선정기술,진일보제고계산효솔.실험결과표명,개진후적산법능구유효지제고재료이용솔,간화절할방식,재계산시간상우세명현.
This paper discusses the One-Dimensional Cutting Stock Problem, improves the original heuristic algorithm based on Sequential Value Correction. Every time it uses dynamic programming algorithm to solve the bounded knapsack problem of opti-mal cutting pattern and preserves many cutting patterns of best value to provide for SHP algorithm selection, modifies the corre-sponding backtrack algorithm to improve the computing efficiency. It comprehensively considers the utilization rate and repeatable times of materials, gives priority to choose the pattern helpful to generate the one behind. From the lots of better results recorded, it finally chooses the scheme meeting needs to use. In the calculating process, it combines with the multi-threading technology to further improve computational efficiency. The experiment results indicate that the improved algorithm can improve the material utilization ratio effectively, simplify the cutting process, and have an obvious advantage in computation time.