Scheduling two agents with sum-of-processing-times-based deterioration on a single machine

摘要

A new scheduling model with two-agent and sum-of-processing-times-based deterioration is proposed in this paper. Two agents compete to perform their respective jobs on a common single machine and each agent has his own criterion to optimize. The sum-of-processing-times-based deterioration of a job is that the actual job processing time is a function of the sum of the normal processing times of the already processed jobs. The objective is to minimize the total completion time of the first agent with the restriction that the makespan of the second agent cannot exceed a given upper bound. The optimal properties of the problems are given and the optimal polynomial time algorithms are proposed to solve the scheduling problems.