Two Models Of On-line Scheduling With Rejection

In classic problems of scheduling theory,all information of jobs are released before the beginning of scheduling.In practice,the information of jobs are not known in advance,but released one by one along with the flowing of time.The scheduler has to make scheduling decisions without knowledge of future release jobs.In this article,the problem is considered in an on-line-over-time fashion.It is firstly proposed and researched by Bartal etal for the problem of multi-processors scheduling with rejection.The goal is to minimize the sum of makespan and punishment which is caused by the rejected jobs.For the on-line-over-list case,they gave a possiblely optimal algorithm of which compctive ratio is at most 2 +α.Generally speaking,the single parallel-batching processor scheduling is ralative with the multi-processors scheduling.In this paper we consider two on-line models of single parallel-batching processor and two identical processors.We can express this problem with three parameters as 1|on-line,p-batch,b=∞,l_j = up_j|w,P₂|on-line,γ_j,l_j= up_j|w, where u∈(0,1),w = max{r_i,c_j}+P(R).The main conclusion of this article,are gained by the analysis of H^∞algorithm and AR algorithm.For the single parallel-batching processor case,the competive ratio of H^∞algorithm is at most(1 +α)/u;For the multi-processors case,the competive ratio of AR algorithm is at most 1 + 2u.In this article,we also get the lower bounds of them by the adversary-method.