Minimizing total completion time for UET tasks with release time and outtree precedence constraints

Yumei Huo; Joseph Y.T. Leung

doi:10.1007/s00186-005-0009-5

Minimizing total completion time for UET tasks with release time and outtree precedence constraints

Yumei Huo, Joseph Y.T. Leung

Computer Science

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

4 Scopus citations

Abstract

Brucker et al. (Math Methods Oper Res 56: 407-412, 2003) have given an O(n ²)-time algorithm for the problems P | p_j = 1, r _j , outtree |∑ C_j and P | pmtn, p_j = 1, r_j, outtree | ∑ C_j . In this note, we show that their algorithm admits an O(n log n)-time implementation.

Original language	English (US)
Pages (from-to)	275-279
Number of pages	5
Journal	Mathematical Methods of Operations Research
Volume	62
Issue number	2
DOIs	https://doi.org/10.1007/s00186-005-0009-5
State	Published - Nov 2005

All Science Journal Classification (ASJC) codes

Software
General Mathematics
Management Science and Operations Research

Keywords

Nonpreemptive scheduling
Outtree
Parallel and identical machines
Preemptive scheduling
Scheduling
Total completion time

Access to Document

10.1007/s00186-005-0009-5

Cite this

@article{ccd6d722422b4a34b280da27be17b2ba,

title = "Minimizing total completion time for UET tasks with release time and outtree precedence constraints",

abstract = "Brucker et al. (Math Methods Oper Res 56: 407-412, 2003) have given an O(n 2)-time algorithm for the problems P | pj = 1, r j , outtree |∑ Cj and P | pmtn, pj = 1, rj, outtree | ∑ Cj . In this note, we show that their algorithm admits an O(n log n)-time implementation.",

keywords = "Nonpreemptive scheduling, Outtree, Parallel and identical machines, Preemptive scheduling, Scheduling, Total completion time",

author = "Yumei Huo and Leung, {Joseph Y.T.}",

year = "2005",

month = nov,

doi = "10.1007/s00186-005-0009-5",

language = "English (US)",

volume = "62",

pages = "275--279",

journal = "Mathematical Methods of Operations Research",

issn = "1432-2994",

publisher = "Physica-Verlag",

number = "2",

}

TY - JOUR

T1 - Minimizing total completion time for UET tasks with release time and outtree precedence constraints

AU - Huo, Yumei

AU - Leung, Joseph Y.T.

PY - 2005/11

Y1 - 2005/11

N2 - Brucker et al. (Math Methods Oper Res 56: 407-412, 2003) have given an O(n 2)-time algorithm for the problems P | pj = 1, r j , outtree |∑ Cj and P | pmtn, pj = 1, rj, outtree | ∑ Cj . In this note, we show that their algorithm admits an O(n log n)-time implementation.

AB - Brucker et al. (Math Methods Oper Res 56: 407-412, 2003) have given an O(n 2)-time algorithm for the problems P | pj = 1, r j , outtree |∑ Cj and P | pmtn, pj = 1, rj, outtree | ∑ Cj . In this note, we show that their algorithm admits an O(n log n)-time implementation.

KW - Nonpreemptive scheduling

KW - Outtree

KW - Parallel and identical machines

KW - Preemptive scheduling

KW - Scheduling

KW - Total completion time

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

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

U2 - 10.1007/s00186-005-0009-5

DO - 10.1007/s00186-005-0009-5

M3 - Article

AN - SCOPUS:27844527883

SN - 1432-2994

VL - 62

SP - 275

EP - 279

JO - Mathematical Methods of Operations Research

JF - Mathematical Methods of Operations Research

IS - 2

ER -

Minimizing total completion time for UET tasks with release time and outtree precedence constraints

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this