若干加工具有分阶段特性的调度问题研究

声明

摘要

第1章绪论

1．1 调度问题及三参数表示

1．2近似算法和最坏情况界

1．3 多阶段车间作业调度问题

1．4论文概述

第2章流水作业环境下机器具有多功能特性的调度问题

2．1 引言

2．2 问题的形式化描述

2．3问题的1．615-近似算法

2．4算法的最坏情况界分析

2．5本章小结

第3章流水作业机器环境下的加工与运输协同调度问题

3．1 引言

3．2 问题的形式化描述

3．3 问题的(5/3+∈)-近似算法

3．3．1 定义“大工件”和“小工件”

3．3．2定义“配置C”

3．3．3近似算法H

3．3．4 子算法H1

3．4近似算法H的最坏情况界分析

3．5本章小结

第4章两阶段流水作业机器环境下的专用机调度问题

4．1 引言

4．2 问题的形式化描述

4．3 问题F2(Pm，D2)‖Cmax的2-近似算法

4．4问题F2(Pm，D2)‖Cmax的多项式时间近似方案(PTAS)

4．4．1准备

4．4．2刻画工序调度方式

4．4．3 具体的动态规划

4．4．4转化为可行调度

4．5本章小结

第5章并行异顺序作业调度问题研究

5．1 引言

5．2．2 问题Pm(J2)‖Cmax的动态规划算法

5．2．3 问题Pm(J2)‖Cmax的完全多项式时间近似方案(FPTAS)

5．3 问题Pm(Js)‖Cmax的研究

5．3．2 问题Pm(Js)‖Cmax的多项式时间近似方案(PTAs)

5．4本章小结

第6章总结和展望

参考文献

附录

致谢