Single-machine scheduling of proportionally deteriorating jobs by two agents

We consider a problem of scheduling a set of independent jobs by two agents on a single machine. Every agent has its own subset of jobs to be scheduled and uses its own optimality criterion. The processing time of each job proportionally deteriorates with respect to the starting time of the job. The problem is to find a schedule that minimizes the total tardiness of the first agent, provided that no tardy job is allowed for the second agent. We prove basic properties of the problem and give a lower bound on the optimal value of the total tardiness criterion. On the basis of these results, we propose a branch-and-bound algorithm and an evolutionary algorithm for the problem. Computational experiments show that the exact algorithm solves instances up to 50 jobs in a reasonably short time and that solutions obtained by the metaheuristic are close to optimal ones.