Online scheduling to minimize average stretch

S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes E. Gehrke

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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. The main contribution of this paper is to show that the shortest remaining processing time (SRPT) algorithm is O(1)-competitive with respect to average stretch for both uniprocessors and 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 9 + 2√6 ≤ 14. Furthermore, we establish constant-factor lower bounds on the competitive ratio of any online algorithm for both uniprocessors and multiprocessors.

    Original languageEnglish (US)
    Pages (from-to)433-452
    Number of pages20
    JournalSIAM Journal on Computing
    Volume34
    Issue number2
    DOIs
    StatePublished - 2005

    Keywords

    • Competitive ratio
    • Online algorithms
    • Scheduling
    • Shortest remaining processing time (SRPT)
    • Slowdown
    • Stretch

    ASJC Scopus subject areas

    • Computer Science(all)
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Online scheduling to minimize average stretch'. Together they form a unique fingerprint.

    Cite this