最大化加工收益调度问题算法研究

论文摘要

本文研究了 m（m≥2）台并行机、带有公共交付期的最大化（权重）加工收益调度问题。该问题被认为是NP-hard,也就是说,除非P=NP,否则无法在多项式时间内找到一个精确算法来求解该问题。并行机是指系统内具有多台速度相同的处理机,每个工件只需在任意一台机器上加工即可;公共交付期是指所有工件具有相同的交付期;加工收益是指工件在交付期之前所完成的工作量。本文研究了该调度问题无权重和带权重模型,并分别提出了不同的算法。对于不带权重的模型,本文提出了一个完全多项式时间近似方案（FPTAS）,近似比为1/1-ε（ε为很小的误差值）,其时间复杂度为O（（1/ε）mnm+1）（m为并行机数量）。该算法不仅适用于两台并行机,对任意的m台并行机同样适用。本文给出FPTAS的证明过程,并与前人结果——多项式时间近似方案（PTAS）—进行了对比实验。实验结果表明,对于相同的ε,本文提出的FPTAS的运行时间要远远优于PTAS的运行时间,且FPTAS的计算精度更高。此外,PTAS的运行时间随ε的减小呈指数增长,而FPTAS的运行时间依然为多项式增长。对于带权重的模型,本文提出了一个伪多项式时间复杂度的动态规划,其时间复杂度为O（max{nlogn,ndm}）。这表明即使考虑权重,问题的复杂性也没有变化（依然为弱NP-hard）。此外,本文针对动态规划的运行时间进行了数值实验。实验结果表明:在内存空间充足的前提下,该算法的运行时间随着工件数量的增加变化缓慢,可以在有效的时间内解决规模较大的问题实例。

论文目录

• 摘要
• Abstract
• 1 绪论
•   1.1 问题介绍
•     1.1.1 研究背景与意义
•     1.1.2 调度问题基础知识
•   1.2 国内外研究现状
•   1.3 本文主要内容及组织结构
• 2 相关理论介绍
•   2.1 复杂性理论介绍
•   2.2 求解优化问题的常用算法
•   2.3 动态规划
•   2.4 近似算法
•     2.4.1 近似算法的基本概念
•     2.4.2 PTAS和 FPTAS介绍
•   2.5 本章小结
• 3 求解Pm| dj= d| max（X）的FPTAS
•   3.1 问题定义
•     3.1.1 问题描述
•     3.1.2 概念定义
•   3.2 FPTAS的设计与分析
•     3.2.1 预备算法介绍
•     3.2.2 FPTAS的设计
•   3.3 计算实例
•   3.4 数值实验
•     3.4.1 测试数据集与测试环境
•     3.4.2 对比实验
•   3.5 本章小结
• 4 求解Pm| dj= d| max（Xw）的相关算法
•   4.1 问题定义
•     4.1.1 问题描述
•     4.1.2 概念定义
•   4.2 算法设计与分析
•     4.2.1 最优解性质分析
•     4.2.2 动态规划算法设计与分析
•     4.2.3 枚举算法设计与分析
•   4.3 数值实验
•     4.3.1 测试数据集与测试环境
•     4.3.2 动态规划与枚举算法对比实验
•   4.4 本章小结
• 结论
• 参考文献
• 致谢

文章来源

类型: 硕士论文

作者: 梁亚歌

导师: 韩鑫

关键词: 并行机,公共交付期,加工收益,完全多项式时间近似方案,动态规划

来源: 大连理工大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 大连理工大学

分类号: O221.3

DOI: 10.26991/d.cnki.gdllu.2019.002991

总页数: 59

文件大小: 1247K

下载量: 14