本文我们考虑单机上工件可拒绝的ND双代理排序问题。在该问题中, 假设有两个代理$A$和$B$他们的工件集合分别记为$\mathcal{J}^A$和$\mathcal{J}^B$。在经典的CO双代理排序模型中, 总是假设两个代理之间是竞争的, 即$\mathcal{J}^A\cap \mathcal{J}^B=\varnothing$。而在ND双代理排序问题中, 我们允许两个代理有共同的工件, 即允许$\mathcal{J}^A\cap \mathcal{J}^B\neq \varnothing$。在工件可拒绝排序中, 每个工件或者被接收并安排在机器上进行加工, 或者被拒绝并支付一个对应的拒绝费用。在本文中, 我们研究了工件可拒绝的ND双代理排序问题。特别地, 我们考虑了一个约束型排序问题。即在满足代理$B$接收工件的最大完工时间$C_{\max}^B$与拒绝工件的总拒绝费用之和不超过一个给定的正整数$Q$的前提下, 我们的目标是最小化代理$A$中接收工件的总完工时间$\sum C_j^A$与拒绝工件的总拒绝费用之和。对该问题, 我们给出了一个拟多项式时间算法以及一个全多项式时间近似方案。

In this paper, we consider the ND two-agent scheduling problem with rejection on a single machine. In this problem, there are two agents $A $ and $B $ and the job sets of them are denoted by $\mathcal{J}^A $ and $\mathcal{J}^B$ respectively. In the classical CO two-agent scheduling, two agents are competitive, i.e., $\mathcal{J}^A\cap \mathcal{J}^B=\varnothing $. However, in the ND two-agent scheduling, two agents may have common jobs, i.e., $\mathcal{J}^A\cap \mathcal{J}^B\neq\varnothing $ is allowed. In scheduling problems with rejection, each job is either accepted and processed on the machine, or rejected by paying a corresponding rejection cost. In this paper, we study the ND two-agent scheduling with rejection. In particular, we consider a constrained scheduling problem. That is, the objective is to minimize the sum of the total completion time $\sum C_j^A $ of accepted $A $-jobs and the total rejection cost of rejected $A $-jobs subject to an upper bound $Q $ on the sum of the makespan $C_{\max}^B $ of accepted $B $-jobs and the total rejection cost of the rejected $B $-jobs. For this problem, we provide a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme.