Rescheduling to Minimize the Total Completion Time under a Limit on the Total Completion Time of The Original Jobs

摘要

We consider the rescheduling problems arising when two agents, each with a set of nonpreemptive jobs, compete to perform their respective jobs on a common processing resource. Each agent wants to minimize a certain objective function, which depends on the completion time of its jobs only. In this paper, we consider the two agents rescheduling problem for jobs on a single machine to minimize total completion time under a limit on the total completion time of the original jobs. We show that the considered problems can be solved in polynomial time or pseudopolynomial time.