Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost

• Two-agent Pareto optimization scheduling.
• The number of tardy jobs and the maximum cost.
• Optimal and Pareto optimal schedules.
• Strongly polynomial-time algorithm.

This paper investigates the Pareto optimization scheduling problem on a single machine with two competing agents A and B in which agent A wants to minimize the number of tardy A-jobs and agent B wants to minimize the maximum cost of B-jobs. In the literature, the constrained optimization problem of minimizing the number of tardy A-jobs under the restriction that the maximum cost of B-jobs is bounded is solved in polynomial time. This implies that the corresponding Pareto optimization scheduling problem can be solved in a weakly polynomial time. In this paper, by presenting a new algorithm for the constrained optimization problem, we provide a strongly polynomial-time algorithm for the corresponding Pareto optimization scheduling problem. Experimentation results show that the proposed algorithm for the considered problem is efficient.