平行机可中断半在线排序问题的若干研究

摘要

本文主要研究平行机可中断半在线排序问题.在论文的第一章里，首先简要介绍了组合优化、排序问题、算法及竞争比等基本概念，并且总结了近年来出现的几个相关的半在线模型及结果. 在第二章中，详细介绍了两台同型机上的两类可中断半在线排序问题，其目标函数为极大化最小机器完工时间Cmin.在第一节中首先对可中断排序问题的背景及发展作了详细介绍.在第二节中研究了已知所有工件的加工时间均在p和rp(p＞0，r≥1)之间的半在线排序模型.对任意参数r，设计了一个最优半在线算法，当1≤r＜2时，这个半在线算法的竞争比至多为4+r/4，而当r≥2时，它的竞争比至多为3/2.在第三节中，对已知最大工件加工时间的半在线模型作了研究，得到了一个竞争比为5/4的最优半在线算法.

目录

文摘

英文文摘

第一章绪论

第二章可中断半在线排序问题

参考文献

攻读硕士期间完成的论文

致谢