基于多线程求解一维下料问题的递归算法

摘要

下料问题广泛应用于国民经济的许多行业,如何提高原材料利用率,降低成本,简化切割工艺,是各企业关注的焦点。一维下料问题是指在下料时只需要考虑一个方向的尺寸,因此又被称为线材下料问题。“堆”是指在下料过程中用来存放各种毛坯的容器,处于打开状态的堆称为“开堆”。下料过程的不同时刻,开堆数可能不同,其最大值称为最大开堆数。因下料场地面积一定,(最大)开堆数往往会受到限制。
　　 本文研究的是一种长度线材上的下料问题。提出采用递归精确算法约束一个排样方式中所含毛坯种数,以减少(最大)开堆数和简化切割工艺。此外,针对递归技术是精确算法,计算时间较长的缺陷,先后运用上界法和多线程技术对递归算法进行改进,有效减少运算时间。同时,保证较高的材料利用率,并实现一维下料系统。通过实验数据测试,证实本文算法的正确性和有效性。本文所做主要工作如下:
　　 首先,针对本文的研究内容,建立当前最好排样方式的计算模型,采用递归技术求解基于该模型的背包问题,生成线材中所含毛坯总价值最大的当前最好排样方式。接着,先后运用上界法、多线程技术对递归算法进行改进,并利用同步函数实现当前最好排样方式的更新。
　　 然后,将一维下料问题的线性整数规划模型松弛得到线性规划模型,将生成的最好排样方式与线性规划结合,利用延迟列生成法求得线性规划问题的最优解,并采取适当的方法取整,得到一维下料问题的近似最优解。
　　 最后,在基于多线程递归算法的基础上开发一维下料系统,提供人性化的输入输出界面,能够满足用户订制的需求。实验计算结果表明,本文所述方法,可以有效地减少所需下料场地的面积和简化切割工艺。