学位论文 > 优秀研究生学位论文题录展示

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

作　者: 郑文
导　师: 崔耀东
学　校: 广西大学
专　业: 计算机技术
关键词: 一维下料开堆切割工艺递归算法多线程编程线性规划
分类号: TP301.6
类　型: 硕士论文
年　份: 2011年
下　载: 54次
引　用: 0次
阅　读: 论文下载

内容摘要

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

全文目录

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

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

内容摘要

全文目录

相似论文