Semi-online scheduling with two GoS levels and unit processing time.

Abstract: In this paper, we consider two semi-online scheduling problems of parallel machines with two GoS (grade of service) levels and unit processing time, in which the objective is to minimize the makespan. Assume that the GoS levels of the first s machines are 2 and that of the last machines are 1 where m is the number of machines. The first problem is the lookahead version where an online algorithm is able to foresee the information of the next k jobs. The second problem is the buffer version where a buffer is available for storing at most g jobs. For the both versions, we prove that the lookahead ability or the buffer is useless for designing algorithm when or . We also show that no online algorithm has a competitive ratio less than for any constant k or g. Moreover, we present two optimal online algorithms for and . At last, for the case with only two machines, we prove that the two algorithms can get their best possible competitive ratio when and . [Copyright &y& Elsevier]