Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work

Ruyan He; Jinjiang Yuan; C. T. Ng; T. C.E. Cheng

doi:10.1007/s10878-021-00697-2

Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work

Ruyan He, Jinjiang Yuan, C. T. Ng, T. C.E. Cheng

Research output: Journal article publication › Journal article › Academic research › peer-review

12 Citations (Scopus)

Abstract

We consider the single-machine preemptive Pareto-scheduling problem with two competing agents A and B, where agent A wants to minimize the number of its jobs (the A-jobs) that is tardy, while agent B wants to minimize the total late work of its jobs (the B-jobs). We provide an O(nn_Alog n_A+ n_Blog n_B) -time algorithm that generates all the Pareto-optimal points, where n_A is the number of the A-jobs, n_B is the number of the B-jobs, and n= n_A+ n_B.

Original language	English
Pages (from-to)	504-525
Number of pages	22
Journal	Journal of Combinatorial Optimization
Volume	41
Issue number	2
DOIs	https://doi.org/10.1007/s10878-021-00697-2
Publication status	Published - Feb 2021

Keywords

Number of tardy jobs
Pareto-scheduling
Scheduling
Total late work
Two agents

ASJC Scopus subject areas

Computer Science Applications
Discrete Mathematics and Combinatorics
Control and Optimization
Computational Theory and Mathematics
Applied Mathematics

More information

10.1007/s10878-021-00697-2

http://hdl.handle.net/10397/94212

Cite this

@article{c4e5cf6a15a9494da5fd2a2b3108ef97,

title = "Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work",

abstract = "We consider the single-machine preemptive Pareto-scheduling problem with two competing agents A and B, where agent A wants to minimize the number of its jobs (the A-jobs) that is tardy, while agent B wants to minimize the total late work of its jobs (the B-jobs). We provide an O(nnAlog nA+ nBlog nB) -time algorithm that generates all the Pareto-optimal points, where nA is the number of the A-jobs, nB is the number of the B-jobs, and n= nA+ nB.",

keywords = "Number of tardy jobs, Pareto-scheduling, Scheduling, Total late work, Two agents",

author = "Ruyan He and Jinjiang Yuan and Ng, {C. T.} and Cheng, {T. C.E.}",

note = "Funding Information: We would like to thank the Associate Editor and two anonymous referees for their many helpful comments and suggestions. This research was supported in part by the NSFC under grant numbers 12071442 and 11771406. Publisher Copyright: {\textcopyright} 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",

year = "2021",

month = feb,

doi = "10.1007/s10878-021-00697-2",

language = "English",

volume = "41",

pages = "504--525",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work

AU - He, Ruyan

AU - Yuan, Jinjiang

AU - Ng, C. T.

AU - Cheng, T. C.E.

N1 - Funding Information: We would like to thank the Associate Editor and two anonymous referees for their many helpful comments and suggestions. This research was supported in part by the NSFC under grant numbers 12071442 and 11771406. Publisher Copyright: © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC part of Springer Nature. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/2

Y1 - 2021/2

N2 - We consider the single-machine preemptive Pareto-scheduling problem with two competing agents A and B, where agent A wants to minimize the number of its jobs (the A-jobs) that is tardy, while agent B wants to minimize the total late work of its jobs (the B-jobs). We provide an O(nnAlog nA+ nBlog nB) -time algorithm that generates all the Pareto-optimal points, where nA is the number of the A-jobs, nB is the number of the B-jobs, and n= nA+ nB.

AB - We consider the single-machine preemptive Pareto-scheduling problem with two competing agents A and B, where agent A wants to minimize the number of its jobs (the A-jobs) that is tardy, while agent B wants to minimize the total late work of its jobs (the B-jobs). We provide an O(nnAlog nA+ nBlog nB) -time algorithm that generates all the Pareto-optimal points, where nA is the number of the A-jobs, nB is the number of the B-jobs, and n= nA+ nB.

KW - Number of tardy jobs

KW - Pareto-scheduling

KW - Scheduling

KW - Total late work

KW - Two agents

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

U2 - 10.1007/s10878-021-00697-2

DO - 10.1007/s10878-021-00697-2

M3 - Journal article

AN - SCOPUS:85099567065

SN - 1382-6905

VL - 41

SP - 504

EP - 525

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 2

ER -

Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this