We present a deterministic online algorithm for scheduling two parallel machines when jobs arrive over time and show that it is 1/2(5 - root5) approximate to 1.38198-competitive. The best previously known algorithm is (3/2)-competitive. Our upper bound matches a previously known lower bound, and thus our algorithm has the best possible competitive ratio. We also present a lower bound of 1.21207 on the competitive ratio of any randomized online algorithm for any number of machines. This improves a previous result of 4 - 2 root2 approximate to 1.17157. (C) 2001 Elsevier Science B.V. All rights reserved. [References: 23]
展开▼
