𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Note on scheduling intervals on-line

✍ Scribed by Ulrich Faigle; Willem M. Nawijn

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
375 KB
Volume
58
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A note on on-line scheduling with partia
A note on on-line scheduling with partial information
✍ Guochuan Zhang; Deshi Ye πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 411 KB

we consider a variant of on-line scheduling, where partial information on future jobs is known beforehand. Assume that the last job will be the longest (with the longest execution time). We provide the beat possible on-line algorithms with competitive ratios \/z and 3/2, respectively, for m = 2 and

On-line scheduling revisited
On-line scheduling revisited
✍ Rudolf Fleischer; Michaela Wahl πŸ“‚ Article πŸ“… 2000 πŸ› Springer US 🌐 English βš– 98 KB
A note on LPT scheduling
A note on LPT scheduling
✍ Bo Chen πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 219 KB
Randomized on-line scheduling on three p
Randomized on-line scheduling on three processors
✍ TomΓ‘Ε‘ TichΓ½ πŸ“‚ Article πŸ“… 2004 πŸ› Elsevier Science 🌐 English βš– 202 KB

We consider a randomized on-line scheduling problem where each job has to be scheduled on any of m identical processors. The objective is to minimize the expected makespan. We show that the competitive ratio of any randomized algorithm for m = 3 processors must be strictly greater than 27 19 .