𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Randomized on-line scheduling on three processors

✍ Scribed by Tomáš Tichý

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
202 KB
Volume
32
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

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 .

📜 SIMILAR VOLUMES

Randomized on-line scheduling on two uni
Randomized on-line scheduling on two uniform machines
✍ Leah Epstein; John Noga; Steve Seiden; Jiří Sgall; Gerhard Woeginger 📂 Article 📅 2001 🏛 Springer US 🌐 English ⚖ 178 KB

We study the problem of on-line scheduling on two uniform machines with speeds 1 and s\*1. A +1.61803 competitive deterministic algorithm was already known. We present the "rst randomized results for this problem: We show that randomization does not help for speeds s\*2, but does help for all s(2. W

Randomized On-line Scheduling of Paralle
Randomized On-line Scheduling of Parallel Jobs
✍ Jiřı́ Sgall 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 230 KB

We study randomized on-line scheduling on mesh machines. We show that for scheduling independent jobs randomized algorithms can achieve a significantly better performance than deterministic ones; on the other hand with dependencies randomization does not help.

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

A comparison of heuristics for schedulin
A comparison of heuristics for scheduling multiprocessor tasks on three dedicated processors
✍ A.K. Amoura; E. Bampis; Y. Manoussakis; Zs. Tuza 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 266 KB

We consider the problem of scheduling a set of independent multiprocessor tasks on three dedicated processors in order to minimize the makespan. We propose a new heuristic, called Divide Uniprocessor Tasks (DUT), and we provide simulation results comparing the eectiveness of DUT with previously know