Summary: We study the two-agent scheduling with rejection on two parallel machines. There are two competing agents \(A\) and \(B\) with job families \(\mathcal{J}^A\) and \(\mathcal{J}^B\), respectively. \(A\) job in \(\mathcal{J}^A\) or \(\mathcal{J}^B\) is either rejected, in which case a rejection penalty will be incurred, or accepted and processed on one of the two parallel machines. The objective is to minimize the sum of the given objective function \(f^A\) of the accepted \(A\)-jobs and the total rejection penalty of the rejected \(A\)-jobs subject to an upper bound on the sum of the given objective function \(f^B\) of the accepted \(B\)-jobs and the total rejection penalty of the rejected \(B\)-jobs, where \(f^A\) and \(f^B\) are non-decreasing functions on the completion time of the accepted \(A\)-jobs and accepted \(B\)-jobs, respectively. We consider four scheduling problems associated with different combinations of the two agents’ objective functions, \(f^A=\sum C_j^A\) and \(f^B\in\{C_{\max}^B,L_{\max}^B,\sum C_j^B,\sum w_j^BU_j^B\}\). When \((f^A,f^B)=(\sum C_j^A,C_{\max}^B)\), we provide two pseudo-polynomial time algorithms and a fully polynomial-time approximation scheme (FPTAS). For the other problems, we give a pseudo-polynomial time algorithm, respectively.