Advice Complexity of Fine-Grained Job Shop Scheduling

Abstract

We study the advice complexity, which is a tool to measure the amount of information necessary to achieve a certain output quality, of a specific online scheduling problem. A great deal of research has been carried out in this field; however, this paper studies the problem in a new setting. We redefine the cost function of the considered job shop scheduling problem. Up to now, the makespan was taken as the cost function. Thus, every algorithm has a cost of at least $m$ and at most $2m$ and is, as a consequence, at least $2$-competitive, where $m$ denotes the number of jobs. Moreover, Hromkovič et al. [8] constructed an algorithm that has a competitive ratio of at most $1+1/\sqrt{m}$. It seems futile to look for better algorithms with respect to this measurement. To allow a more fine-grained analysis, we take the delay of an algorithm as its cost. We prove that with this new cost measure, the best algorithms so far have competitive ratios of $\sqrt{m}$ or $\sqrt{m}/2$ while reading about $\log _2(\sqrt{m})$ advice bits. Then, we describe a deterministic online algorithm with a competitive ratio of at most $0.67\sqrt{m}$. We use this deterministic algorithm to construct an online algorithm with advice that reads $b \ge 2\log _2(m)+1$ advice bits and has a competitive ratio of at most $\max \{6,\sqrt{8\log _2(m)}\root 4 \of {m}/\sqrt{b}\}$.

This work was partially supported by the SNF grant 200021-141089.