Scheduling problems with two competing agents to minimized weighted earliness-tardiness

We study scheduling problems with two competing agents, sharing the same machines. All the jobs of both agents have identical processing times and a common due date. Each agent needs to process a set of jobs, and has his own objective function. The objective of the first agent is total weighted earliness-tardiness, whereas the objective of the second agent is maximum weighted deviation from the common due date. Our goal is to minimize the objective of the first agent, subject to an upper bound on the objective value of the second agent. We consider a single machine, and parallel (both identical and uniform) machine settings. An optimal solution in all cases is shown to be obtained in polynomial time by solving a number of linear assignment problems. We show that the running times of the single and the parallel identical machine algorithms are O(nm+3), where n is the number of jobs and m is the number of machines. The algorithm for solving the problem on parallel uniform machine requires O(nm+3m3) time, and under very reasonable assumptions on the machine speeds, is reduced to O(nm+3). Since the number of machines is given, these running times are polynomial in the number of jobs.