Two-agent single-machine scheduling problems under increasing linear deterioration

A new scheduling model in which both two-agent and increasing linear deterioration exist simultaneously is investigated in this paper. The processing time of a job is defined as an increasing linear function of its starting time. Two agents compete to perform their respective jobs on a common single machine and each agent has his own criterion to optimize. We introduce an increasing linear deterioration model into the two-agent single-machine scheduling, where the goal is to minimize the objective function of the first agent with the restriction that the objective function of the second agent cannot exceed a given upper bound. We study two scheduling problems with the different combinations of two agents’ objective functions: makespan, maximum lateness, maximum cost and total completion time. We propose the optimal properties and present the optimal polynomial time algorithms to solve the scheduling problems, respectively.