论文部分内容阅读
论文主要研究了两类排序问题：一类是己知最大工件加工时间的半在线平行机排序问题；另一类是关于工件加工时间恶化单处理机排序问题。目标函数主要考虑了最大完工时间(Cmax)、总完工时间(∑Cj)、最大延误时间(Lmax)。全文共分四章。
第一章是绪论部分，主要介绍排序问题相关的一些基本概念和预备知识，调度理论中常用的各种专业术语和已有的一些结果。
第二章主要研究了已知最大工件加工时间半在线平行机排序问题针对三台机的情况。本文设计了一个竞争比为3/2的算法，并且证明了此界是紧的。特别地，对于m台机的情况，本文给出了此问题的一个下界为√33+3/6。
第三章主要是关于工件加工时间恶化问题的若干研究，总结并证明了一些性质，相应的设计了一些新的模型，给出了一些算法。
第四章主要回顾了本文的一些结论，探讨了解决问题中存在的困难，并指出了以后进一步的研究方向，提出了个人看法。