Online Scheduling to Minimize Average Stretch

We consider the classical problem of online job scheduling on uniprocessor and multiprocessor machines. For a given job, we measure the quality of service provided by an algorithm by the stretch of the job, which is defined as the ratio of the amount of time that the job spends in the system to the processing time of the job. For a given sequence of jobs, we measure the performance of an algorithm by the average stretch achieved by the algorithm over all the jobs in the sequence. The average stretch metric has been used to evaluate the performance of scheduling algorithms in many applications arising in databases, networks and systems; however no formal analysis of scheduling algorithms is known for the average stretch metric. The main contribution of the paper is to show that the shortest remaining processing time algorithm (SRPT) is O(l)-competitive with respect to average stretch for both uniprocessors as well as multiprocessors. For uniprocessors, we prove that SRPT is 2-competitive; we also establish an essentially matching lower bound on the competitive ratio of SRPT. For multiprocessors, we show that the competitive ratio of SRPT is at most 14. Furthermore, we establish constant-factor lower bounds on the competitive ratio of any online algorithm for both uniprocessors and multiprocessors.

Authors

• S. Muthukrishnan 0001
• Rajmohan Rajaraman
• Anthony Shaheen
• Johannes Gehrke

Keywords

• Delay
• Time measurement
• Processor scheduling
• Computer science
• Application specific integrated circuits
• Databases
• Throughput
• Online Scheduling
• Average Stretch
• Lower Bound
• Processing Time
• Constant Factor
• Scheduling Algorithm
• Online Algorithm
• Average Metrics
• Job Sequence
• Competitive Ratio
• Time Step
• Response Time
• Sustained Release
• Web Server
• Completion Time
• Positive Integer
• Positive Real
• Optimal Schedule
• End Of Step
• Work Unit
• Average Response Time
• Start Of Phase
• Proof Of The Lemma
• End Of Each Time Step
• Induction Hypothesis
• Single Processor
• Induction Step
• Part Of The Map
• Multiset
• Alternative Schedules