|
We consider an online scheduling problem on three parallel and identical machines with two grades of service (GoS) levels. Given are three machines and n independent jobs, each job and machine assigned the GoS levels of 1 or 2. The processing rule is that the job is allowed to be processed on some particular machines only when the GoS level of the job is no less than that of the machine, the jobs arrive over time and the three machines are idle at the same time only when all jobs arrived are completed. The objective is to minimize the makespan. In this paper, we show that any online approximation algorithm for the problem under consideration achieves the competitive ratio is no better than 4 / 3 , even for the case where the GoS levels of machines are 1, 2, 2, respectively. Moreover, we present an approximation algorithm with a competitive ratio of 5 / 3which is better than the best known algorithm whose the competitive ratio is 9 / 5 .
|
