𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An optimal algorithm for preemptive on-line scheduling

✍ Scribed by Bo Chen; André van Vliet; Gerhard J. Woeginger

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
286 KB
Volume
18
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On-line scheduling to minimize max flow
On-line scheduling to minimize max flow time: an optimal preemptive algorithm
✍ Christoph Ambühl; Monaldo Mastrolilli 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 170 KB

We investigate the maximum flow time minimization problem of on-line scheduling jobs on m identical parallel machines. When preemption is allowed, we derive an optimal algorithm with competitive ratio 2 -1/m. When preemption is not allowed and m = 2, we show that the First In First Out heuristic ach

An Optimal Multiprocessor Real-Time Sche
An Optimal Multiprocessor Real-Time Scheduling Algorithm
✍ Ashok Khemka; R.K. Shyamasundar 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 170 KB

An optimal scheduling algorithm is described that feasibly schedules a set of m periodic tasks on n processors before their respective deadlines, if the task set satisfies certain conditions. The complexity of this scheduling algorithm in terms of the number of scheduled tasks and the number of proc