基于多线程的并行分支定界算法框架及其应用

摘要

随着信息产业技术的快速发展，多核处理器成为处理器市场上的主流产品，开发并行程序，充分利用多核处理器的多个内核成为程序开发的趋势。并行算法作为并行程序开发的核心，是算法研究的一个新的方向。但并行算法的设计与实现向来都比较复杂，所以研究具有通用性的并行算法框架具有现实意义。
　　本文针对求解优化问题中常用的分支定界算法进行研究，将分支定界算法分割成与问题相关和与问题无关的部分，进而设计基于多线程的并行分支定界算法框架。应用并行分支定界算法框架对板坯出库问题进行求解，并通过实验验证了算法框架的高效性。
　　基于多线程的并行分支定界算法框架共有三个模块，分别是结点定义模块、相关接口模块和并行分支定界算法求解模块。结点定义模块和相关接口模块对应分支定界算法中与问题相关的部分，开发人员在使用框架求解具体问题时，需要对这两个模块中的结点类型和相关接口函数进行定义。求解模块对应分支定界算法中与问题无关的部分，该模块为并行分支定界算法的核心。其主要内容为并行环境参数的设置，分支定界算法的并行化等内容，开发人员在使用框架时不需要对模块的内容进行编辑。
　　综上所述，本文提出了基于多线程的并行分支定界算法框架。算法框架采用Windows多线程编程技术中的Win32 API实现算法的并行化，可以有效的提高CPU使用率。使用并行分支定界算法框架求解问题时，将会提高算法设计的重复利用性，减少了开发人员的工作量，具有一定的实际应用价值。

目录

声明

摘要

第1章 绪论

1．1 研究背景

1．2 国内外研究现状

1．3 研究意义和研究目的

1．4 本文的组织结构

第2章 分支定界算法和多线程技术

2．1 分支定界算法

2．1．1 基本原理

2．1．2 分支定界算法的分类

2．1．3 分支定界算法的改进

2．1．4 分支定界算法的应用

2．2 多线程编程

2．2．1 进程和线程

2．2．2 线程的操作

2．2．3 多线程编程技术

2．3 本章小结

第3章 并行分支定界算法框架的设计与实现

3．1 引言

3．2 并行分支定界算法框架的设计

3．2．1 框架的结构

3．2．2 框架的设计模式

3．3 并行分支定界算法框架的实现

3．3．1 结点定义模块的实现

3．3．2 接口模块的实现

3．3．3 并行分支定界算法求解模块的实现

3．4 并行化分支定界算法框架的使用方法

3．4．1 背包问题简介

3．4．2 使用并行分支定界算法框架求解背包问题

3．4．3 实验结果

3．5 本章小结

第4章 在热轧板坯出库问题上的应用

4．1 引言

4．2 板坯出库问题的数学描述

4．3 使用并行分支定界算法框架求解板坯出库问题

4．3．1 结点类型的定义

4．3．2 初始化接口函数的定义

4．3．3 可行解判断接口函数的定义

4．3．4 分支操作接口函数的定义

4．3．5 界值接口函数的定义

4．3．6 结点调整接口函数的定义

4．3．7 全局解更新接口函数

4．4 实验结果与分析

4．4．1 实验配置

4．4．2 实验结果

4．5 本章小结

第5章 总结与展望

参考文献

致谢