Scheduling uniform machines on-line requires nondecreasing speed ratios

A.P.A. Vestjens

Abstract

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 language English Eindhoven Technische Universiteit Eindhoven 10 Published - 1994

Publication series

Name Memorandum COSOR 9435 0926-4493

Fingerprint

Scheduling algorithms
Scheduling
Processing

Cite this

Vestjens, A. P. A. (1994). Scheduling uniform machines on-line requires nondecreasing speed ratios. (Memorandum COSOR; Vol. 9435). Eindhoven: Technische Universiteit Eindhoven.
Vestjens, A.P.A. / Scheduling uniform machines on-line requires nondecreasing speed ratios. Eindhoven : Technische Universiteit Eindhoven, 1994. 10 p. (Memorandum COSOR).
@book{911befe1ac874ff7acd0abdce0025408,
title = "Scheduling uniform machines on-line requires nondecreasing speed ratios",
abstract = "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.",
author = "A.P.A. Vestjens",
year = "1994",
language = "English",
series = "Memorandum COSOR",
publisher = "Technische Universiteit Eindhoven",

}

Vestjens, APA 1994, Scheduling uniform machines on-line requires nondecreasing speed ratios. Memorandum COSOR, vol. 9435, Technische Universiteit Eindhoven, Eindhoven.

Scheduling uniform machines on-line requires nondecreasing speed ratios. / Vestjens, A.P.A.

Eindhoven : Technische Universiteit Eindhoven, 1994. 10 p. (Memorandum COSOR; Vol. 9435).

TY - BOOK

T1 - Scheduling uniform machines on-line requires nondecreasing speed ratios

AU - Vestjens, A.P.A.

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

M3 - Report

T3 - Memorandum COSOR

BT - Scheduling uniform machines on-line requires nondecreasing speed ratios

PB - Technische Universiteit Eindhoven

CY - Eindhoven

ER -

Vestjens APA. Scheduling uniform machines on-line requires nondecreasing speed ratios. Eindhoven: Technische Universiteit Eindhoven, 1994. 10 p. (Memorandum COSOR).