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.
