关键词: 排序, ND双代理, 拒绝费用, 拟多项式时间算法, 全多项式时间近似方案

Abstract:

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.

Key words: scheduling, ND two-agent, rejection cost, pseudo-polynomial time algorithm, fully polynomial-time approximation scheme