Improved competitive algorithms for two-processor real-time systems

The problem of competitive on-line scheduling in two-processor real-time environments is studied. The model of Koren and Shasha is followed: Every task has a deadline and a value that it obtains only if it completes by its deadline - the value being its computation time. The goal is to design on-line schedulers with worst-case guarantees compared with a clairvoyant scheduler. Koren and Shasha gave algorithms for the migration and no-migration models, with competitive multipliers of 2 and 3, respectively. In this article, we give an algorithm for the no-migration model with an improved competitive multiplier of 2(1+16). We also show that the competitive multiplier for the migration model can be lowered by using a fast processor and a slow processor, compared with using several parallel and identical processors with the same aggregate computing power.