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 J(A) and J(B), respectively. A job in J(A) or J(B) 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 f(A) 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 f(B) 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 f(A) and f(B) are non-decreasing functions on the completion times of their respective jobs. We show that, for all pairs (f(A), f(B)) is an element of {(C-max(A), C-max(B)), (L-max(A), L-max(B)), (Sigma C-j(A), L-max(B)), (Sigma C-j(A), L-max(B)), (Sigma C-j(A), Sigma w(j)(B)U(j)(B))}, the problems are NP-hard. When (f(A),f(B)) = (C-max(A), L-max(B)), we provide a pseudo-polynomial-time algorithm. Moreover, when (f(A),f(B)) = (C-max(A), L-max(B)) and all B-jobs are accepted, we give a 2-approximation algorithm and an fully polynomial-time approximation scheme. Finally, for (f(A),f(B)) is an element of {(Sigma C-j(A), L-max(B)), (Sigma C-j(A), Sigma w(j)(B)U(j)(B))}K, we present pseudo-polynomial-time algorithms, respectively. (C) 2014 Elsevier Inc. All rights reserved.