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.
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP