𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Semi on-line scheduling on three processors with known sum of

✍ Scribed by Enrico Angelelli; Maria Grazia Speranza; Zsolt Tuza

Publisher
Springer US
Year
2007
Tongue
English
Weight
274 KB
Volume
10
Category
Article
ISSN
1094-6136

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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 .

On-line scheduling of multi-core process
On-line scheduling of multi-core processor tasks with virtualization
✍ Deshi Ye; Guochuan Zhang πŸ“‚ Article πŸ“… 2010 πŸ› Elsevier Science 🌐 English βš– 580 KB

We consider an on-line list scheduling problem of multi-core processor tasks with virtualization to minimize makespan. The competitive ratio of an on-line algorithm is shown for every specific m, where m is the number of processors. Better on-line algorithms are presented for a small number of proce

Efficiency and effectiveness of normal s
Efficiency and effectiveness of normal schedules on three dedicated processors
✍ P. Dell'Olmo; M.G. Speranza; Zs. Tuza πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 637 KB

A set of tasks has to be scheduled on three processors and each task requires that a set of the processors be available for a given processing time. The objective of the problem is to determine a nonpreemptive schedule with minimum makespan. The problem is known to be NP-hard in the strong sense. A