An optimal online algorithm for scheduling two machines with release times

AbstractWe present a deterministic online algorithm for scheduling two parallel machines when jobs arrive over time and show that it is 12(5−5)≈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−22≈1.17157