Online scheduling of equal-processing-time task systems

Yumei Huo; Joseph Y.T. Leung; Xin Wang

doi:10.1016/j.tcs.2008.03.026

Online scheduling of equal-processing-time task systems

Yumei Huo, Joseph Y.T. Leung, Xin Wang

Computer Science

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

4 Scopus citations

Abstract

We consider the problem of online scheduling a set of equal-processing-time tasks with precedence constraints so as to minimize the makespan. For arbitrary precedence constraints, it is known that any list scheduling algorithm has a competitive ratio of 2 - 1 / m, where m is the number of machines. We show that for intree precedence constraints, Hu's algorithm yields an asymptotic competitive ratio of 3/2.

Original language	English (US)
Pages (from-to)	85-95
Number of pages	11
Journal	Theoretical Computer Science
Volume	401
Issue number	1-3
DOIs	https://doi.org/10.1016/j.tcs.2008.03.026
State	Published - Jul 23 2008

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Keywords

Competitive ratio
Equal-processing-time tasks
Intree precedence constraints
Makespan
Online scheduling
Parallel and identical machines

Access to Document

10.1016/j.tcs.2008.03.026

Cite this

@article{818747f4f9a944888e3472a4882b2749,

title = "Online scheduling of equal-processing-time task systems",

abstract = "We consider the problem of online scheduling a set of equal-processing-time tasks with precedence constraints so as to minimize the makespan. For arbitrary precedence constraints, it is known that any list scheduling algorithm has a competitive ratio of 2 - 1 / m, where m is the number of machines. We show that for intree precedence constraints, Hu's algorithm yields an asymptotic competitive ratio of 3/2.",

keywords = "Competitive ratio, Equal-processing-time tasks, Intree precedence constraints, Makespan, Online scheduling, Parallel and identical machines",

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

note = "Funding Information: The work of the first author was supported in part by the PSC-CUNY research fund. The work of the second author was supported in part by the NSF grant DMI-0556010.",

year = "2008",

month = jul,

day = "23",

doi = "10.1016/j.tcs.2008.03.026",

language = "English (US)",

volume = "401",

pages = "85--95",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Online scheduling of equal-processing-time task systems

AU - Huo, Yumei

AU - Leung, Joseph Y.T.

AU - Wang, Xin

N1 - Funding Information: The work of the first author was supported in part by the PSC-CUNY research fund. The work of the second author was supported in part by the NSF grant DMI-0556010.

PY - 2008/7/23

Y1 - 2008/7/23

N2 - We consider the problem of online scheduling a set of equal-processing-time tasks with precedence constraints so as to minimize the makespan. For arbitrary precedence constraints, it is known that any list scheduling algorithm has a competitive ratio of 2 - 1 / m, where m is the number of machines. We show that for intree precedence constraints, Hu's algorithm yields an asymptotic competitive ratio of 3/2.

AB - We consider the problem of online scheduling a set of equal-processing-time tasks with precedence constraints so as to minimize the makespan. For arbitrary precedence constraints, it is known that any list scheduling algorithm has a competitive ratio of 2 - 1 / m, where m is the number of machines. We show that for intree precedence constraints, Hu's algorithm yields an asymptotic competitive ratio of 3/2.

KW - Competitive ratio

KW - Equal-processing-time tasks

KW - Intree precedence constraints

KW - Makespan

KW - Online scheduling

KW - Parallel and identical machines

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

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

U2 - 10.1016/j.tcs.2008.03.026

DO - 10.1016/j.tcs.2008.03.026

M3 - Article

AN - SCOPUS:45049087046

SN - 0304-3975

VL - 401

SP - 85

EP - 95

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-3

ER -

Online scheduling of equal-processing-time task systems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this