This paper studies online job scheduling on multiprocessors and, in particular, investigates the algorithms SRPT and SJF for minimizing total stretch, where the stretch of a job is its flow time (response time) divided by its processing time. SRPT is perhaps the most well-studied algorithm for minimizing total flow time or stretch. This paper gives the first resource augmentation analysis of the total stretch of SRPT, showing that it is indeed O(1)-speed 1-competitive. This paper also gives a simple lower bound result that SRPT is not s-speed 1-competitive for any s < 1.5. This paper also makes contribution to the analysis of SJF. Extending the work of [4], we are able to show that SJF is O(1)-speed 1-competitive for minimizing total stretch. More interestingly, we find that the competitiveness of SJF can be reduced arbitrarily by increasing the processor speed (precisely, SJF is O(s)-speed (1/s)-competitive for any s ≥ 1). We conjecture that SRPT also admits a similar result.
展开▼
