𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Randomized On-line Scheduling of Parallel Jobs

✍ Scribed by Jiřı́ Sgall

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
230 KB
Volume
21
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Scheduling jobs and maintenance activiti
Scheduling jobs and maintenance activities on parallel machines
✍ Chung-Yee Lee; Zhi-Long Chen 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB 👁 1 views

Most machine scheduling models assume that the machines are available all of the time. However, in most realistic situations, machines need to be maintained and hence may become unavailable during certain periods. In this paper, we study the problem of processing a set of n jobs on m parallel machin

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

Exact algorithms for scheduling multiple
Exact algorithms for scheduling multiple families of jobs on parallel machines
✍ Zhi-Long Chen; Warren B. Powell 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB

## Abstract In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent o

A metric of fairness for parallel job sc
A metric of fairness for parallel job schedulers
✍ John Ngubiri; Mario van Vliet 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 428 KB 👁 1 views

## Abstract Fairness is an important aspect in queuing systems. Several fairness measures have been proposed in queuing systems in general and parallel job scheduling in particular. Generally, a scheduler is considered unfair if some jobs are discriminated whereas others are favored. Some of the me