Abstract: We consider a two-agent scheduling problem with rejection on a single machine. For the problem, we have two agents A and B and each agent has its own job set and cost function. A job of agent A is either accepted or rejected with a certain rejection penalty having to be paid. The jobs of agent B must be accepted. The cost function of agent A is the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. The cost function of agent B is the maximum lateness. The objective of the scheduling problem is to minimize the cost function of agent A, given that the cost function of agent B does not exceed a fixed value. For this problem, we give a full polynomial-time approximation scheme.

Key words: scheduling, agent, rejection, approximation scheme