Single-machine online scheduling to minimize maximum weighted completion time with limited weights
The setting we consider is nonpreemptive single machine online schedul-ing,with the objective to minimize the maximum weighted completion time of jobs.The weight of the job is not only limited strictly within the processing time compass of this job,but also agreeable with processing time of this job,i.e.,apj ≤ wj≤bpj(a≥√52-1b,b≥a)and if wi＞wj,then pi≥pj.Especially,if wi=wj,then pi=pj.Significantly,there are irrelevant jobs arriving online over time and the knowledge of each job Jj,such as its processing length pj and weight wj,is not revealed for the scheduler until it is released at time rj.By means of adversary method,it is explicitly derived that the lower bound of the considered problem is 1+b+a.Then we provide a best possible online algorithm with the competitive ratio of 1+b+a.Moreover,the competitive ratio of this algorithm is√5+1/2,when a=√5-1/2b.
single machineonline schedulingonline algorithmweighted completion time
万方数据
维普
