一维下料问题的一种混合启发式算法

管卫利，龚 击，薛焕堂

1 引言

下料问题广泛的出现在机械制造业的生产过程中，其实质是对有限资源进行合理安排使得资源利用率最高[1-2]。一维下料问题是指：将库存线材原料切割成若干种所需零件，每种零件具有特定的长度和需求量，寻求一种下料方案使得线材利用率最高。管材，型材，棒材的切割下料均属于一维下料问题。下料方案由多种切割方式按照一定数量组合而成，切割方式是指零件在单根线材上的排列方式。目前一维下料问题的解决方法可分为两大类：以切割方式为导向的方法和以零件为导向的方法[3]。以切割方式为导向的方法首先组合零件形成多种不同的切割方式，然后确定每种切割方式所使用的数量。文献[4]针对一维下料问题提出了一种基于遗传算法的随机搜索模型，通过在可行的切割方式集合中进行迭代搜索来产生下料方案。文献[5]提出了一种顺序启发式算法，首先求出所有可行的切割方式，然后按照一定的启发式规则搜索所有可能的切割方式组合，选择一组最优切割方式形成下料方案。

以零件为导向的方法按顺序生成下料方案中各切割方式，每个切割方式满足部分零件需求量，直到所有零件需求量得到满足后终止切割方式的生成。文献[6]提出了一种基于多级序列思想的下料算法，将下料问题转化为多级序列优化问题，每级对应单根线材切割方式的求解问题，用剩余零件需求量构造每级最优序列。……