Two-agent scheduling with rejection on a single machine

In this paper, we consider the two-agent scheduling problem with rejection on a single machine. In the problem we have two agents A and B with job families JA and JB, respectively. A job in JA or JB is either accepted and processed on the machine, or rejected with a certain rejection penalty having to be paid. The objective is to minimize the sum of the given objective function fA of the accepted jobs and total rejection penalty of the rejected jobs of the first agent A, given that the second agent B only accepts schedules such that the sum of the given objective function fB of the accepted jobs and total rejection penalty of the rejected jobs of the agent B does not exceed a fixed value Q (Q is a positive integer), where fA and fB are non-decreasing functions on the completion times of their respective jobs. We show that, for all pairs (fA,fB)∈CmaxA,CmaxB,LmaxA,LmaxB,∑CjA,CmaxB,∑CjA,LmaxB,∑CjA,∑wjBUjB, the problems are NP-hard. When (fA,fB)=CmaxA,LmaxB, we provide a pseudo-polynomial-time algorithm. Moreover, when (fA,fB)=CmaxA,LmaxB and all B-jobs are accepted, we give a 2-approximation algorithm and an fully polynomial-time approximation scheme. Finally, for (fA,fB)∈∑CjA,LmaxB,∑CjA,∑wjBUjBK, we present pseudo-polynomial-time algorithms, respectively.