基于贪心混合定位算法三阶段排样问题研究

Research on Three-stage Nesting Problem Based on Greedy Hybrid Positioning Algorithm

针对三阶段排样板材利用率问题,提出了基于贪心混合定位算法的三阶段排样优化方法。以板材利用率为优化目标,首先建立带约束的混合整数规划模型,对三阶段排样问题进行分割;其次将板材分成3个分区并使用贪心算法对输入序列进行排序优化;最后使用混合定位算法对候选矩形件找最优板材放置分区。研究采用数据规模为3 000块矩形件的4组板材数据集进行验证,结果表明,所提模型较其他算法板材利用率得到提高,且运行时长大幅缩短。

A three-stage layout optimization method based on greedy hybrid positioning algorithm was proposed to solve the utilization problem of three-stage layout.Taking the utilization rate of sheet metal as the optimization objective,firstly,a constrained mixed integer programming model is established to segment the three-stage layout problem;secondly,the plate is divided into three partitions and the input sequence is sorted and optimized by greedy algorithm;finally,a hybrid positioning algorithm is used to find the optimal plate placement partition for the candidate rectangular parts.Four sets of plate data with a data scale of 3000 rectangular pieces are used to verify the results.The results show that the proposed model has higher plate utilization and shorter running time than other algorithms.