TY - JOUR

T1 - Pareto-optimization of three-agent scheduling to minimize the total weighted completion time, weighted number of tardy jobs, and total weighted late work

AU - Zhang, Yuan

AU - Yuan, Jinjiang

AU - Ng, Chi To

AU - Cheng, Tai Chiu E.

N1 - Funding Information:
National Natural Science Foundation of China, 11671368; 11771406; 12071442 Funding information
Funding Information:
The authors would like to thank the Associate Editor and three anonymous referees for their constructive comments and kind suggestions. This research was supported in part by the NSFC under grant numbers 12071442, 11671368 and 11771406.
Publisher Copyright:
© 2020 Wiley Periodicals LLC
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2020

Y1 - 2020

N2 - We consider three-agent scheduling on a single machine in which the criteria of the three agents are to minimize the total weighted completion time, the weighted number of tardy jobs, and the total weighted late work, respectively. The problem is to find the set of all the Pareto-optimal points, that is, the Pareto frontier, and their corresponding Pareto-optimal schedules. Since the above problem is unary NP-hard, we study the problem under the restriction that the jobs of the first agent have inversely agreeable processing times and weights, that is, the smaller the processing time of a job is, the greater its weight is. For this restricted problem, which is NP-hard, we present a pseudo-polynomial-time algorithm to find the Pareto frontier. We also show that, for various special versions, the time complexity of solving the problem can be further reduced.

AB - We consider three-agent scheduling on a single machine in which the criteria of the three agents are to minimize the total weighted completion time, the weighted number of tardy jobs, and the total weighted late work, respectively. The problem is to find the set of all the Pareto-optimal points, that is, the Pareto frontier, and their corresponding Pareto-optimal schedules. Since the above problem is unary NP-hard, we study the problem under the restriction that the jobs of the first agent have inversely agreeable processing times and weights, that is, the smaller the processing time of a job is, the greater its weight is. For this restricted problem, which is NP-hard, we present a pseudo-polynomial-time algorithm to find the Pareto frontier. We also show that, for various special versions, the time complexity of solving the problem can be further reduced.

KW - scheduling

KW - three-agent Pareto-optimization

KW - total weighted completion time

KW - total weighted late work

KW - weighted number of tardy jobs

UR - http://www.scopus.com/inward/record.url?scp=85096673977&partnerID=8YFLogxK

U2 - 10.1002/nav.21961

DO - 10.1002/nav.21961

M3 - Journal article

AN - SCOPUS:85096673977

JO - Naval Research Logistics

JF - Naval Research Logistics

SN - 0894-069X

ER -