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

摘要

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

目录

声明

摘要

第1章绪论

1．1调度问题概述

1．2算法设计与分析

1．3并行车间作业调度问题模型

1．4论文概述

第2章m个并行两阶段自由车间作业调度问题

2．1 引言

2．2符号定义

2．3 问题Pm(O2)‖Cmax的动态规划算法设计

2．4 问题Pm(O2)‖Cmax的一个完全多项式时间近似方案(FPTAS)

2．5本章小结

第3章m个并行κ阶段自由车间作业调度问题

3．1 引言

3．3 问题Pm(Ok)‖Cmax的一个多项式时间近似方案(PTAS)

3．4本章小结

第4章并行两阶段流水车间作业调度问题

4．1 引言

4．2 问题P(F2)‖Cmax特殊实例的框架以及混合整数规划

4．3 问题P(F2)‖Cmax的一个多项式时间近似方案(PTAS)

4．4本章小结

第5章总结与展望

参考文献

附录

致谢