Minimizing the weighted number of tardy task units

Joseph Y.T. Leung; Vincent K.M. Yu; W. D. Wei

doi:10.1016/0166-218X(92)00037-M

Minimizing the weighted number of tardy task units

Joseph Y.T. Leung, Vincent K.M. Yu, W. D. Wei

Research output: Contribution to journal › Article › peer-review

31 Scopus citations

Abstract

The problem of minimizing the weighted number of tardy task units on a single processor is considered. We give an O(n log n + kn)-time algorithm for a set of n tasks with k distinct weights. The relation of this problem with that of minimizing the total weighted error in the imprecise computation model is also discussed.

Original language	English (US)
Pages (from-to)	307-316
Number of pages	10
Journal	Discrete Applied Mathematics
Volume	51
Issue number	3
DOIs	https://doi.org/10.1016/0166-218X(92)00037-M
State	Published - Jul 6 1994
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Keywords

Feasible schedule
Imprecise computation
Late task
On-time task
Preemptive schedule
Single processor
Tardy task units

Access to Document

10.1016/0166-218X(92)00037-M

Cite this

@article{2d271f297ff24c3181d74268239286eb,

title = "Minimizing the weighted number of tardy task units",

abstract = "The problem of minimizing the weighted number of tardy task units on a single processor is considered. We give an O(n log n + kn)-time algorithm for a set of n tasks with k distinct weights. The relation of this problem with that of minimizing the total weighted error in the imprecise computation model is also discussed.",

keywords = "Feasible schedule, Imprecise computation, Late task, On-time task, Preemptive schedule, Single processor, Tardy task units",

author = "Leung, {Joseph Y.T.} and Yu, {Vincent K.M.} and Wei, {W. D.}",

note = "Funding Information: *Corresponding author. +Research supported in part by the ONR grant N00014-91-J-1383, Instruments, Inc., and in part by a grant from the National Education of China.",

year = "1994",

month = jul,

day = "6",

doi = "10.1016/0166-218X(92)00037-M",

language = "English (US)",

volume = "51",

pages = "307--316",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - Minimizing the weighted number of tardy task units

AU - Leung, Joseph Y.T.

AU - Yu, Vincent K.M.

AU - Wei, W. D.

N1 - Funding Information: *Corresponding author. +Research supported in part by the ONR grant N00014-91-J-1383, Instruments, Inc., and in part by a grant from the National Education of China.

PY - 1994/7/6

Y1 - 1994/7/6

N2 - The problem of minimizing the weighted number of tardy task units on a single processor is considered. We give an O(n log n + kn)-time algorithm for a set of n tasks with k distinct weights. The relation of this problem with that of minimizing the total weighted error in the imprecise computation model is also discussed.

AB - The problem of minimizing the weighted number of tardy task units on a single processor is considered. We give an O(n log n + kn)-time algorithm for a set of n tasks with k distinct weights. The relation of this problem with that of minimizing the total weighted error in the imprecise computation model is also discussed.

KW - Feasible schedule

KW - Imprecise computation

KW - Late task

KW - On-time task

KW - Preemptive schedule

KW - Single processor

KW - Tardy task units

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

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

U2 - 10.1016/0166-218X(92)00037-M

DO - 10.1016/0166-218X(92)00037-M

M3 - Article

AN - SCOPUS:0005435448

SN - 0166-218X

VL - 51

SP - 307

EP - 316

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 3

ER -

Minimizing the weighted number of tardy task units

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this