关于单机两个客户竞争排序问题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‖∑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）.