کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4626084 | 1631782 | 2016 | 12 صفحه PDF | دانلود رایگان |
• 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.
Journal: Applied Mathematics and Computation - Volume 273, 15 January 2016, Pages 912–923