Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4626084 | Applied Mathematics and Computation | 2016 | 12 Pages |
•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.