Approzimation Schemes for Scheduling on Parallel Machines with GoS Levels
We consider the offline scheduling problem of minimizing the makespan on m parallel and identical machines with certain feature. Every job and machine are labeled with the grade of service (GoS) levels, and each job can only be processed by the machine whose GoS level is no more than that of the job. In this paper, we present a polynomial time approximation scheme (PTAS) with running time O (nlogn) for the special case where the GoS level is either 1 or 2, where the hidden constant depends exponentially on the reciprocal value of the desired
Approzimation algorithm GoS level Makespan PTAS FPTAS
Weidong Li Jianping Li Tongquan Zhang
Department of Mathematics, Yunnan University, Kunming 650091, PR China School of Mathematics and Computer Science Yunnan Nationalities University, Kunming, 650031, PR Chin
国际会议
张家界
英文
53-60
2009-09-20（万方平台首次上网日期，不代表论文的发表时间）