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.

  • 1
    $\begingroup$ Please clarify: At what time does the size of a job become known, and at what time does it have to be scheduled? $\endgroup$ – gnasher729 Jul 21 '20 at 17:32
  • $\begingroup$ 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. $\endgroup$ – Felix Jul 22 '20 at 13:43
  • $\begingroup$ To make the problem clear, can you please describe how to get $\frac 32$ bound for $2$ machines? $\endgroup$ – Dmitry Jul 23 '20 at 5:33
  • $\begingroup$ 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. $\endgroup$ – Felix Jul 23 '20 at 8:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.