若干并行车间作业调度问题研究

论文摘要

并行车间作业调度问题源于大数据云计算领域,是近几年调度问题研究中的一个热点问题.本文主要针对并行车间作业的调度问题进行研究,研究的重点是问题的近似方案设计和最坏情况界分析.本文研究了m个并行k阶段自由车间作业调度问题,分别考虑了k=2和k为任意值情形下的问题;研究了并行两阶段流水车间作业调度问题,考虑了并行的流水作业车间数为问题的输入情形下的模型.全文共分五章.第一章首先简要介绍了调度问题的一些基本概念以及相关预备知识,接着论述了并行车间作业调度问题模型的相关研究成果.第二章主要研究m个并行两阶段自由车间作业调度问题.在该问题中,每个工件都有两道自由作业工序,每个工件需要在m个并行的两阶段自由车间作业中选择一个进行加工,并且每个工件在加工过程中不允许中断,目标是极小化最后完工工件的完工时间.用三参数法表示为Pm（O2）‖Cmax.针对该问题,本文给出了一个完全多项式时间近似方案（FPTAS）.第三章主要研究m个并行k阶段自由车间作业调度问题.在该问题中,每个工件都有k道自由作业工序,每个工件需要在m个并行的k阶段自由车间作业中选择一个进行加工,并且每个工件在加工过程中不允许中断,目标是极小化最后完工工件的完工时间.用三参数法表示为Pm（Ok）‖Cmax.针对该问题,本文给出了一个多项式时间近似方案（PTAS）.第四章主要研究并行两阶段流水车间作业调度问题.在该问题中,每个工件都有两道流水作业工序,每个工件需要在任意个并行的两阶段流水车间作业中选择一个进行加工,这里并行流水车间的个数是问题的一个输入.并且每个工件在加工过程中不允许中断,目标是极小化最后完工工件的完工时间.用三参数法表示为P（F2）‖Cmax.针对该问题,本文给出了一个多项式时间近似方案（PTAS）.第五章总结全文并提出相关问题进一步的研究方向.

论文目录

• 摘要
• Abstract
• 1 绪论
•   1.1 调度问题概述
•   1.2 算法设计与分析
•   1.3 并行车间作业调度问题模型
•   1.4 论文概述
• 2 m个并行两阶段自由车间作业调调度问题
•   2.1 引言
•   2.2 符号定义
• m（O₂）‖C_max的动态规划算法设计'>  2.3 问题P_m（O₂）‖C_max的动态规划算法设计
• m（O₂）‖C_max的一个完全多项式时间近似方案（FPTAS）'>  2.4 问题P_m（O₂）‖C_max的一个完全多项式时间近似方案（FPTAS）
•   2.5 本章小结
• 3 m个并行k阶段自由车间作业调调度问题
•   3.1 引言
• m（O_k）‖C_max的一些性质和概念'>  3.2 问题P_m（O_k）‖C_max的一些性质和概念
• m（O_k）‖C_max的一个多项式时间近似方案（PTAS）'>  3.3 问题P_m（O_k）‖C_max的一个多项式时间近似方案（PTAS）
•   3.4 本章小结
• 4 并行两阶段流水车间作业调度问题
•   4.1 引言
• 2）‖C_max特殊实例的框架以及混合整数规划'>  4.2 问题P（F₂）‖C_max特殊实例的框架以及混合整数规划
• 2）‖C_max的一个多项式时间近似方案（PTAS）'>  4.3 问题P（F₂）‖C_max的一个多项式时间近似方案（PTAS）
•   4.4 本章小结
• 5 总结与展望
• 参考文献
• 附录
• 致谢

文章来源

类型: 硕士论文

作者: 金茹燕

导师: 董建明,胡觉亮

关键词: 调度问题,并行流水车间作业,并行自由车间作业,动态规划,线性规划,完全多项式时间近似方案

来源: 浙江理工大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 浙江理工大学

分类号: O224

总页数: 54

文件大小: 1897K

下载量: 125