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. constructed an algorithm that has a competitive ratio of at most 1 + 1/m~(1/2). It seems futile to look for better algorithms with respect to this measurement. To allow a more finegrained 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 m~(1/2) or m~(1/2)/2 while reading about log_2(m~(1/2)) advice bits. Then, we describe a deterministic online algorithm with a competitive ratio of at most 0.67m~(1/2). 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, 8 log_2 (m)~(1/2) m~(1/4) / b~(1/2)}.
展开▼
