Deadline scheduling part 1 — overview and theory

Posted Jan 16, 2018 19:09 UTC (Tue) by Cyberax (✭ supporter ✭, #52523)
Parent article: Deadline scheduling part 1 — overview and theory

> Distribution of tasks to processors turns out to be an NP-hard problem (a bin-packing problem, essentially) and, due to other anomalies, there is no dominance of one scheduling algorithm over any others.
Fortunately, the most naive bin-packing algorithm produces results that are at most 2 times worse than the optimal packing.

Deadline scheduling part 1 — overview and theory

Posted Jan 16, 2018 19:30 UTC (Tue) by jreiser (subscriber, #11027) [Link] (2 responses)

The bin-packing strategy First Fit Decreasing has a tight bound of 11/9 optimal, plus 2/3.

Deadline scheduling part 1 — overview and theory

Posted Jan 16, 2018 20:27 UTC (Tue) by bristot-memorial (guest, #61569) [Link] (1 responses)

There are some nice results with semi-partitioned scheduling in the academic world, like this:

http://drops.dagstuhl.de/opus/volltexte/2017/7165/pdf/LIP...

Actually, we are already working on it, but still, it is not optimal.

Deadline scheduling part 1 — overview and theory

Posted Jan 16, 2018 21:33 UTC (Tue) by Cyberax (✭ supporter ✭, #52523) [Link]

Back when I was doing schedulers for distributed computing, we converged on a bin-packing algorithm with some heuristics to handle its pathological cases.

It worked wonders and was simple to implement.