机器带准备时间的两台同类机半在线排序

摘要

本文研究了机器带准备时间两台同类机半在线排序问题及其近似算法. 全文共分三章.第一章简要介绍了排序问题的背景、基本概念、半在线排序问题、机器带准备时间的排序问题.第二章讨论了机器带准备时间的两台同类机已知工件总加工时间半在线排序问题，目标函数为极小化最大机器完工时间和极小化最大工件完工时间，给出了此问题的近似算法，证明了其竞争比为√2，并证明了不存在竞争比小于(1+√3)/2的近似算法.第三章讨论了机器带准备时间的两台同类机已知工件最大加工时间半在线排序问题，目标函数为极小化最大机器完工时间和极小化最大工件完工时间，给出了此问题的近似算法，证明了其竞争比为3/2，并证明了不存在竞争比小于√2的近似算法.可以看出对于已知工件总加工时间和已知工件最大加工时间的两台同类机半在线排序问题，机器带准备时间与否不改变其竞争比.

目录

文摘

英文文摘

第一章 引言

第二章 已知工件总加工时间半在线排序问题

第三章 已知工件最大加工时间半在线排序问题

参考文献

攻读硕士期间完成的论文

致谢