Scheduling uniform machines on-line requires nondecreasing speed ratios

A.P.A. Vestjens

    Research output: Book/ReportReportAcademic

    25 Downloads (Pure)


    We consider the following on-line scheduling problem. We have to schedule n independent jobs, where n is unknown, on m uniform parallel machines so as to minimize the makespan; preemption is allowed. Each job becomes available at its release date, and this release date is not known beforehand; its processing requirement becomes known at its arrival. We show that if only a finite number of preemptions is allowed, then there exists an algorithm that solves the problem if and only if $s_{i-1}/s_i \leq s_i/s_{i+1}$ for all i = 2, ... , m -1, where s_i denotes the ith largest machine speed. We also show that if this condition is satisfied, then O(mn) preemptions are necessary, and we provide an example to show that this bound is tight. Keywords: on-line algorithms, preemptive scheduling, uniform machines.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherTechnische Universiteit Eindhoven
    Number of pages10
    Publication statusPublished - 1994

    Publication series

    NameMemorandum COSOR
    ISSN (Print)0926-4493

    Fingerprint Dive into the research topics of 'Scheduling uniform machines on-line requires nondecreasing speed ratios'. Together they form a unique fingerprint.

    Cite this