论文部分内容阅读
本文研究了在线Dial-a-Ride问题，考虑了目标函数是最大完工时间的多服务器问题和目标函数是总流水时间的单服务器问题。得到了一些结果。
在第二章中，研究了在线多服务器问题，应用REPLAN和IGNORE思想得到了解决此问题的PAH算法，并且证明了此算法的竞争比为2。在第三章中，研究了目标函数是总流程时间的单服务器在线问题。证明了此问题在一般的对手，即oblivious对手下，没有竞争比是常数的算法。并且按照相对竞争比的思想，限制了对手的能力，给出了限制对手这个概念。最后并证明了在限制对手下，此问题的下界是2。