A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions

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

doi:10.1016/j.disopt.2009.02.002

A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions

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

Computer Science

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

7 Scopus citations

Abstract

We consider the problem of preemptively scheduling n independent jobs on m parallel machines so as to minimize the makespan. Each job J_j has a release time r_j and it can only be processed on a subset of machines M_j. The machines are linearly ordered. Each job J_j has a machine index a_j such that M_j = {M_aj, M_{aj + 1}, ..., M_m}. We first show that there is no 1-competitive online algorithm for this problem. We then give an offline algorithm with a running time of O (n k log P + m n k² + m³ k), where k is the number of distinct release times and P is the total processing time of all jobs.

Original language	English (US)
Pages (from-to)	292-298
Number of pages	7
Journal	Discrete Optimization
Volume	6
Issue number	3
DOIs	https://doi.org/10.1016/j.disopt.2009.02.002
State	Published - Aug 2009

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computational Theory and Mathematics
Applied Mathematics

Keywords

Inclusive processing set
Makespan minimization
Polynomial-time algorithms
Preemptive scheduling
Release time

Access to Document

10.1016/j.disopt.2009.02.002

Cite this

@article{95347c00017347d690f951d71b5f914f,

title = "A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions",

abstract = "We consider the problem of preemptively scheduling n independent jobs on m parallel machines so as to minimize the makespan. Each job Jj has a release time rj and it can only be processed on a subset of machines Mj. The machines are linearly ordered. Each job Jj has a machine index aj such that Mj = {Maj, Maj + 1, ..., Mm}. We first show that there is no 1-competitive online algorithm for this problem. We then give an offline algorithm with a running time of O (n k log P + m n k2 + m3 k), where k is the number of distinct release times and P is the total processing time of all jobs.",

keywords = "Inclusive processing set, Makespan minimization, Polynomial-time algorithms, Preemptive scheduling, Release time",

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

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

year = "2009",

month = aug,

doi = "10.1016/j.disopt.2009.02.002",

language = "English (US)",

volume = "6",

pages = "292--298",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions

AU - Huo, Yumei

AU - Leung, Joseph Y.T.

AU - Wang, Xin

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

PY - 2009/8

Y1 - 2009/8

N2 - We consider the problem of preemptively scheduling n independent jobs on m parallel machines so as to minimize the makespan. Each job Jj has a release time rj and it can only be processed on a subset of machines Mj. The machines are linearly ordered. Each job Jj has a machine index aj such that Mj = {Maj, Maj + 1, ..., Mm}. We first show that there is no 1-competitive online algorithm for this problem. We then give an offline algorithm with a running time of O (n k log P + m n k2 + m3 k), where k is the number of distinct release times and P is the total processing time of all jobs.

AB - We consider the problem of preemptively scheduling n independent jobs on m parallel machines so as to minimize the makespan. Each job Jj has a release time rj and it can only be processed on a subset of machines Mj. The machines are linearly ordered. Each job Jj has a machine index aj such that Mj = {Maj, Maj + 1, ..., Mm}. We first show that there is no 1-competitive online algorithm for this problem. We then give an offline algorithm with a running time of O (n k log P + m n k2 + m3 k), where k is the number of distinct release times and P is the total processing time of all jobs.

KW - Inclusive processing set

KW - Makespan minimization

KW - Polynomial-time algorithms

KW - Preemptive scheduling

KW - Release time

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

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

U2 - 10.1016/j.disopt.2009.02.002

DO - 10.1016/j.disopt.2009.02.002

M3 - Article

AN - SCOPUS:67349097086

SN - 1572-5286

VL - 6

SP - 292

EP - 298

JO - Discrete Optimization

JF - Discrete Optimization

IS - 3

ER -

A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this