Semi-Online Scheduling with Machine Cost

For most scheduling problems the set of machines is fixed initially andremains unchanged for the duration of the problem. Recently Imreh andNogaproposed to add the concept of machine cost to schedulingproblems and considered the so-called List Model problem. An onlinealgorithm with a competitive ratio 1.618 was given while the lowerbound is 4/3. In this paper, two different semi-online versions of thisproblem are studied. In the first case, it is assumed that theprocessing time of the largest job is known a priori. A semi-onlinealgorithm is presented with the competitive ratio at most 1.5309 while thelower bound is 4/3. In the second case, it is assumed that the totalprocessing time of all jobs is known in advance. A semi-online algorithmis presented with the competitive ratio at most 1.414 while the lower boundis 1.161. It is shown that the additional partial available informationabout the jobs leads to the possibility of constructing a schedule witha smaller competitive ratio than that of online algorithms.