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

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.

• Please clarify: At what time does the size of a job become known, and at what time does it have to be scheduled? – gnasher729 Jul 21 '20 at 17:32
• Jobs become known one after another and need to be scheduled immediately. For example if a instance is given by $\sigma=(1,2,3)$ you need to schedule $1$ on one of the three machines, then $2$ then $3$. Each without knowing what job comes next and without moving them again. – Felix Jul 22 '20 at 13:43
• To make the problem clear, can you please describe how to get $\frac 32$ bound for $2$ machines? – user114966 Jul 23 '20 at 5:33
• Consider $\sigma=(k,k,2k)$ with $k\in\mathbb{N}$. Every deterministic algorithm must place the first and second job each on its own machine. (Since otherwise the sequence with only the first two jobs would imply $2$-competitiveness). Afterwards the job of size $2k$ arrives and is placed w.l.o.g on machine $M_1$. This results in a makespan of $3$ whilst the optimal offline algorithm on $\sigma=(k,k,2,k)$ could reach a makespan of $2$. Thus no det. algorithm can result in a $c<3/2$-competitive algorithm on $2$ machines. – Felix Jul 23 '20 at 8:36