论文部分内容阅读
本文考虑在线的最大完工时间的单机分批排序问题，即1|on-line，B，rj|Cmax。一台批处理机可以同时加工b个工件，同一批工件开工时间和完工时间相同，加工时间等于该批工件中的最大加工时间。每个工件的到达时间事先未知，加工时间在到达时才知道。对于该问题，张国川等人提出两个算法HB和MHB，竞争比都不大于2，对于所有工件分两批到达的特殊情况，算法HB的竞争比为(√5+1)/2，对于一般问题，他们猜测算法MHB可能是最好的在线算法，竞争比可以达到(√5+1)/2。
在本文中，我们给出了工件分三批到达的实例，对于该实例算法HB的竞争比等于2；也给出了当机器容量趋于无穷时，算法MHB的竞争比趋向2的实例，从而证明了在一般情况下算法HB和MHB的竞争比不可能小于2。
另外，我们提出一个新算法，对于一般问题其竞争比为2。特别地，当机器容量等于2时，该算法的竞争比为(√5+5)/4。