Two-agent single-machine scheduling problem is considered in this paper.
Agent A’s goal is to minimize the sum of the total weighted delivery time and the total
delivery cost, and agent B has the delivery time window. First, the NP-hardness of the
general problem is proved, and then two special cases are considered. One case is that
A’s jobs have agreeable ratio and this problem is still NP-hard. A pseudo-polynomial
dynamic programming algorithm and a 3
2 -approximation algorithm are designed. In
the other case, A’s jobs have agreeable ratio and B’s jobs have deadline at the same
time. This problem is polynomial solvable.