Two-agent scheduling of time-dependent jobs

We consider the problem of scheduling deteriorating jobs or shortening jobs with two agents A and B. We are interested in generating all Pareto‐optimal schedules for the two criteria: (1) the total completion time of the jobs in A and the maximum cost of the jobs in B, and (2) the maximum cost of the jobs in A and the maximum cost of the jobs in B. We show that all Pareto‐optimal schedules for both problems can be generated in polynomial time, whether the jobs are deteriorating or shortening.