Two-Agent Supply Chain Scheduling Problem to Minimize the Sum of the Total Weighted Completion Time and Batch Cost

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 32-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.