基于GPU高性能计算的切割与布局问题的并行求解方法研究的综述报告.docx

基于GPU高性能计算的切割与布局问题的并行求解方法研究的综述报告
【前言】
切割与布局问题（CuttingandPackingProblem，CPP）是制造业和物流业中常见的优化问题，旨在将一个或多个物品（如，纸张、钢材、零件等）放置到一个或多个容器内，以最小化某种成本（如，废料、能耗、时间等）。该问题涉及到的实际应用广泛，如纸张横切、板材裁剪、物流装载等。为了提高求解效率和质量，近年来越来越多的研究者将GPU高性能计算技术应用于CPP的并行求解中，取得了不俗的成果。本文旨在对该领域的相关工作进行梳理和综述。
【切割问题的分类和解法】
切割问题可以分为单品切割、多品切割和有限模式切割。其中，单品切割指的是将一张材料（如，纸张、布料等）切割成若干子材料，多品切割指的是将多种原材料切割成所需尺寸和数量的部件，有限模式切割指的是在有限种材料模型和切割方案下，最大化产生部件价值。根据搜索方法的不同，CPP的解法可以分为贪心算法、动态规划、回溯算法、遗传算法、模拟退火、粒子群等优化算法。这些算法各有特点，可以根据实际应用场景选择合适的算法。
【GPU高性能计算与CPP解法】
CUDA是由英伟达公司开发的一种并行计算框架，利用GPU的并行计算能力加速计算密集型应用程序的执行，具有高效、灵活、可扩展等优点。近年来，越来越多的研究者将CUDA应用于CPP的并行求解中。例如，基于盒子约束模型（BoxConstraintsModel，BCM）的二维切割问题的GPU并行解法（徐正卿等，2017）利用GPU的并行计算能力，将其简化为线性规划形式，并采用单纯形法进行求解。同样的，基于Hopfield神经网络模型的三维装箱问题也可以利用GPU来加速求解（王旭东等，2016）。这些工作的共同之处在于使用GPU加速求解过程中的瓶颈部分，并且取得了不俗的性能提升。
【结论】
本文综述了基于GPU高性能计算的CPP求解方法。通过对现有的文献进行梳理和分析，我们发现，GPU并行计算技术在CPP求解中具有潜力和优势。然而，仍然存在一些尚未解决的问题，如GPU和CPU之间的数据传输、负载均衡等。因此，未来的研究方向可以集中在解决这些问题上，进一步提高CPP求解的效率和质量。