基于在线检测动态一维下料问题的GPU并行蚁群算法

GPU parallel ant colony algorithm for the dynamic one-dimensional cutting stock problem based on the on-line detection

随着在线检测技术发展,生产线上的物料需要根据检测结果进行快速切割。已有一维下料优化问题是根据全局目标进行建模的,其最优化算法不能满足实时调整切割方案的要求。本文首先根据物料在线检测及切割特点提出了动态多规格一维下料优化问题,并给出最优化模型;然后结合GPU特点创建并行蚁群算法来求解多规格动态一维下料问题,以保证在有限时间内求得近似最优结果;经过算法分析证明,对于大规模数据变量,并行蚁群算法效率高于传统蚁群算法。通过实验表明,在大规模数据量下,此并行蚁群算法与传统蚁群算法和分支定界算法相比,能够在较短时间内得到较优切割方案。

With the technology development in on-line detection, materials on the product line need to be cut quickly according to the re- sult of real-time detection. As existing one-dimensional cutting stock problems （CSP） focus on themodel global optimization solution, their algorithms are not suitable to compute the optimal cutting pattern which are often adjusted by the detection. Here, the dynamic one- dimensional CSP with multiple stock lengths is proposed to support the characteristics, which cuts the optimal stock base on on-line de- tection. In order to gain the approximate optimal solution in the limited time, a parallel ant colony（ACO） algorithm is created by the fea- ture of GPU. Through the analysis, the parallel ACO algorithm has better performance than classical ACO algorithm when they process large - scale variables. Experimental results confirm that the GPU parallel ACO algorithm can obtain the better solution in a short time, compared with classical ACO algorithm and the branch-and-bound algorithm.