一种“一刀切”式矩形件优化排样混合算法

Hybrid algorithm of guillotine rectangular cutting problem

对"一刀切"矩形件排样问题,提出一种将启发式递归与免疫克隆算法相结合的混合优化方法。首先,提出一种启发式递归算法,利用该算法逐次生成利用率最高的条料,直到所有矩形件均生成条料;然后利用免疫克隆算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少,即使总的板材利用率达到了最大。对两个典型算例进行计算,并与相关文献比较,表明了算法的有效性。

A hybrid algorithm of combining heuristic recursive algorithm with immune clone algorithm was presented tot solving the guillotine rectangular cutting problem. Firstly, a recursive algorithm of heuristic was proposed for converting all rectangle parts to the strips of high utilization ratio. Secondly, the immune clone algorithm was used and the optimal order of these strips was obtained for minimizing the quantity of boards. Two typical examples were computed and the results were compared with that of other related papers. The results indicate the effectiveness and efficiency of the algorithm.