𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Partial servicing of on-line jobs

✍ Scribed by Rob van Stee; Han La Poutré

Book ID
102397847
Publisher
Springer US
Year
2001
Tongue
English
Weight
255 KB
Volume
4
Category
Article
ISSN
1094-6136

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of scheduling jobs online, where jobs may be served partially in order to optimize the overall use of the machines. Service requests arrive online to be executed immediately. The scheduler must decide how long and if it will run a job (that is, it must ÿx the quality of service level of the job) at the time of arrival of the job. We assume that preemption is not allowed.

We give lower bounds on the competitive ratio and present algorithms for jobs with varying sizes and for jobs with uniform size, and for jobs that can be run for an arbitrary time or only for some ÿxed fraction of their full execution time.

📜 SIMILAR VOLUMES

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.

Maximizing job benefits on-line
Maximizing job benefits on-line
✍ Baruch Awerbuch; Yossi Azar; Oded Regev 📂 Article 📅 2001 🏛 Springer US 🌐 English ⚖ 81 KB

We consider a beneÿt model for on-line preemptive scheduling. In this model jobs arrive at the on-line scheduler at their release time. Each job arrives with its own execution time and beneÿt function. The ow time of a job is the time that passes from its release to its completion. The beneÿt functi

On an on-line scheduling problem for par
On an on-line scheduling problem for parallel jobs
✍ Edwin Naroska; Uwe Schwiegelshohn 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 101 KB

This paper addresses the non-preemptive on-line scheduling of parallel jobs. In particular we assume that the release dates and the processing times of the jobs are unknown. It is already known that for this problem Garey and Graham's list scheduling algorithm achieves the competitive factor 2 -1 m