论文部分内容阅读
机器排序和机器覆盖经常在实际运用中出现，比如在网络通信中信道分配均衡问题，大型的并行计算问题，柔性生产系统中任务排序问题，等等.这篇论文主要研究m台同型机的半在线排序问题，目标为极大化最小机器负载.论文中研究了多个模型，针对每个模型都给出了下界并设计了相应的半在线算法，有的算法是最优算法.全文共分为四章.
第一章是绪论部分，主要介绍排序问题的基本概念和基础知识.
第二章主要研究了已知工件总加工时间或最大工件加工时间的半在线平行机排序问题Pm‖Cmin.分别给出了问题Pm|sum|Cmin和Pm|max|Cmin的最优算法.算法的竞争比均是m-1.
第三章主要研究了复合半在线排序问题Pm|sum＆max|Cmin和Pm|opt＆max|Cmin.对于问题Pm|sum&max|Cmin，我们给出了m≥3时的最优算法.算法的竞争比在m=3时是3/2，m≥4时为m-2.对于问题Pm|opt＆max|Cmin，当机器数为两台时，设计了竞争比为5/4的最优算法OM2，当m≥3时，设计了竞争比为2-1/m-1的算法OMm，其中当m=3，4，5时，OMm为最优算法.
第四章主要研究了排序问题Pm|k-bounded|Cmin和Pm|opt＆k-bounded|Cmin.首先证明了LS算法是问题Pm|k-bounded|Cmin的最优算法，竞争比为mk/mk-m+1.对于问题Pm|opt＆k-bounded|Cmin，给出了下界：若m≤2k+1，下界为2k+1/2k；否则为m/m-1.并设计了竞争比为mk+m-1/mk的算法kFillm.