关于单机两个客户竞争排序问题1||∑w_j^Ac_j^A:f_(max)~B≤Q的一个注记  

A Note on the Single Machine Competitive Scheduling Problem with Two-agent 1||Σw_j^Ac_j^A:f_(max)~B≤Q

作　　者：罗文昌[1,2] 李剑秋[3] 

机构地区：[1]宁波大学理学院,宁波315211 [2]浙江大学数学系,杭州310027 [3]浙江工商大学杭州商学院,杭州310018

出　　处：《应用数学学报》2011年第1期73-80,共8页Acta Mathematicae Applicatae Sinica

基　　金：国家自然科学基金(11071215);宁波大学学科科研基金(xk1061)资助项目

摘　　要：研究了单机两个客户竞争排序问题1‖∑w_j^Ac_j^A:f_(max)~B≤Q,证明了该问题与问题1|MA_i|∑w_jc_j及问题1|h_i,pmtn|∑w_jc_j之间是相互等价的.对w_j=p_j时的特殊情形,指出了问题1‖∑w_j^Ac_j^A:f_(max)~B≤Q存在近似比为2的最长处理时间优先算法(LPT)且该界是紧的,对w_j任意的一般情形,指出了问题1‖∑w_j^Ac_j^A:f_(max)~B≤Q存在近似比为4+ε的近似算法.当客户B的工件数是常数时,对问题1‖∑w_j^Ac_j^A:f_(max)~B≤Q则给出了伪多项式时间的动态规划算法.此外,指出了问题1‖∑w_j^Ac_j^A:∑w_j^Bc_j^B≤Q具有多项式时间近似方案(PTAS).In this paper,we consider a single machine competitive scheduling problem with two-agent 1｜｜∑wj^Acj^A：fmax^B≤Q and prove that the problems 1｜｜∑wj^Acj^A：fmax^B≤Q, 1｜MAi｜Σwjcj and 1｜hi,pmtn｜Σwjcj are equivalent.For the special case with w_j = p_j,we show that there exists a 2-approximation algorithm which is named as longest-processing-time -first（LPT） algorithm and the bound is tight.As for the general case with arbitrary w_j,we argue that there exists a（4＋ε）-approximation algorithm.when the number of jobs belonging to agent B is fixed,we then propose a pseudo-polynomial time dynamic programming algorithm.Moreover,we point out that the problem 1｜｜∑wj^Acj^A：fmax^B≤Q admits a polynomial time approximation scheme（PTAS）.

关 键 词：两个客户 竞争排序 多个维护 近似算法 

分 类 号：O221.7[理学—运筹学与控制论]