TransWikia.com

Scheduling jobs online on 3 identical machines - a lower bound of 5/3

Computer Science Asked on November 5, 2021

Consider the Online Scheduling Problem with $3$ identical machines. Jobs, with arbitrary size arrive online one after another and need to be scheduled immediately on one of the $3$ machines without ever moving them again.

How can I show, that there can’t be any deterministic Online-Algorithm which achieves a competitive ratio of $c<frac{5}{3}$.

This should be solved by just giving some instance $sigma$ and arguing that no det. algorithm can do better.
Same can easily be done for $2$ machines and $c<frac{3}{2}$. Sadly I can’t find any solution to this (more or less) textbook question.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP