Two-agent single-machine scheduling with deteriorating jobs

•We study some two-agent single-machine scheduling problems with increasing linear job deterioration.•We consider six different combinations of two-agent objective functions.•We discuss complexities and develop polynomial-time algorithms of the proposed problems.

We consider several two-agent single-machine scheduling problems with deteriorating jobs. By deteriorating jobs we mean that the actual processing time of any job of the two agents is an increasing linear function of its starting time. Each agent wants to minimize a certain objective function, which depends on the completion times of its jobs only. The goal is to schedule the jobs such that the performance of the schedule is satisfactory with respect to the objective functions of both agents. We consider six scheduling problems associated with different combinations of the two agents’ objective functions, which include the maximum cost, total weighted completion time, discounted total weighted completion time, maximum earliness cost, total earliness, and total weighted earliness. We examine different scenarios depending on the trade-off between the two agents. Under each scenario, we address the computational complexity and solvability issues of various problems that seek to find the optimal solution for one agent, subject to an upper bound on the maximum (earliness) cost of the other agent.