论文摘要
排序论是运筹学的一个重要分支。排序问题经常在实际应用中出现，比如网络通信中信道分配均衡问题，大型的并行计算问题，柔性生产系统中任务排序问题，等等。在线排序是排序论当前研究的热点问题之一。而对于现实中的在线问题，虽然工件的全部信息并不知道，但根据问题的实际背景，我们往往知道后续工件的部分信息，而且常常是利用了这些部分信息后能够设计出比不利用这些信息时更好的在线算法。我们把这样的问题称为半在线（semi online）问题，相应的算法称为半在线算法。本文主要研究两类两台平行机（two parallel machines）的半在线排序问题，并分析确定性半在线算法的竞争比（competitive ratio）。论文中主要研究了三个模型，并针对每个模型都给出了相应的半在线算法。全文共分三章。第一章是绪论部分，主要介绍排序问题的背景内容以及相应的准备知识。第二章主要研究了两类带机器准备时间的两台同类机半在线排序问题。假设两台机器的速度和准备时间分别为s1=1，s2=s≥1，r1=r≥0，r2=0。一类问题是最大工件加工时间已知的半在线排序，目标函数为极大化最小机器完工时间，即Q2，r1|pmax|Cmin。我们给出了竞争比至少为s+1/2s+1的MIN半在线算法，且此算法对于该问题的竞争比是紧的。另一类问题是所有工件总加工时间已知的半在线排序，目标函数为极小化最大机器完工时间的问题，即Q2，r1|sum|Cmax。我们给出了竞争比不超过2（s+1）/2s+1的MH半在线算法。第三章主要介绍了带缓冲区的两台同型机半在线排序问题，其中缓冲区的长度为k（即每次至多容纳k个工件）。目标函数为极大化最小机器负载的问题，即P2|buffer|Cmin。我们设计了竞争比至少为2/3的半在线算法。