Deadline scheduling part 1 — overview and theory

Posted Jan 16, 2018 19:30 UTC (Tue) by jreiser (subscriber, #11027)
In reply to: Deadline scheduling part 1 — overview and theory by Cyberax
Parent article: Deadline scheduling part 1 — overview and theory

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.