一维下料问题的AB分类法

Applying AB classification method in one-dimensional cutting stock problem

为了解决大规模的一维下料问题的计算困难,根据一维下料问题的特点,把贪心算法和随机搜索技术有机地结合起来,利用随机搜索技术对贪心算法进行了有效的改进,提出了一种简单实用的AB分类法。实验表明,该算法对规模较大的问题也能较快地获得问题最优解或精度较高的近似最优解。

In order to solve large-scale one-dimensional cutting stock problem of calculating difficulties, according to the characteristics of one-dimensional cutting stock problem, the author used random search technology to improve the greedy algorithm and put forward a kind of simple and practical classification method named AB. Experiments show that the algorithm for larger problems can quickly obtain the optimal solution or approximate optimal solution with high accuracy.