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

论文摘要

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

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 问题的概述
• 1.3 一维下料问题的研究进展
• 1.4 减少开堆数问题（MOSP）的研究现状
• 1.5 本文的主要工作
• 1.6 章体结构
• 第二章 一维下料问题的数学模型及线性规划方法
• 2.1 一维下料问题的符号描述
• 2.2 建立数学模型
• 2.3 线性规划方法
• 第三章 基于MFC的多线程编程技术
• 3.1 进程与线程的概念
• 3.2 MFC中的多线程编程
• 3.2.1 启动线程
• 3.2.2 线程的同步处理
• 第四章 基于多线程的递归算法
• 4.1 当前最好排样方式计算模型
• 4.2 排样方式生成算法—基于多线程的递归算法
• 4.2.1 基本递归算法
• 4.2.2 运用上界技术改进递归算法
• 4.2.3 运用多线程技术改进递归算法
• 4.3 排样方案生成算法
• 4.4 全文算法流程图
• 第五章 一维下料系统的研制
• 5.1 一维下料系统的菜单结构
• 5.2 使用一维下料系统进行排样
• 第六章 实验计算
• 6.1 排样方案可行性的实验结果
• 6.2 最大开堆数的实验结果
• 6.3 排样方案利用率的实验结果
• 6.4 上界法的实验结果
• 6.5 多线程的实验结果
• 6.6 简化切割工艺的实验结果说明
• 第七章 总结与展望
• 7.1 本文小结
• 7.2 下一步工作
• 参考文献
• 附录A 常用符号说明
• 附录B 主要程序源代码
• 致谢
• 攻读学位期间发表论文情况