Advice Complexity of Fine-Grained Job Shop Scheduling

摘要

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, Hromkovic et al. [8] constructed an algorithm that has a competitive ratio of at most 1 + 1/{the square root of}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 {the square root of}m or {the square root of}m/2 while reading about log_2({the square root of}m) advice bits. Then, we describe a deterministic online algorithm with a competitive ratio of at most 0.67{the square root of}m. We use this deterministic algorithm to construct an online algorithm with advice that reads b ≥ 2 log_2(m) + 1 advice bits and has a competitive ratio of at most max{6, {the square root of}(8 log_2 (m)) ~4{the square root of}m/{the square root of}b}.