Scheduling jobs with equal processing times subject to machine eligibility constraints

Kangbok Lee; Joseph Y.T. Leung; Michael L. Pinedo

doi:10.1007/s10951-010-0190-0

Scheduling jobs with equal processing times subject to machine eligibility constraints

Kangbok Lee, Joseph Y.T. Leung, Michael L. Pinedo

Computer Science

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

43 Scopus citations

Abstract

We consider the problem of nonpreemptively scheduling a set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a prespecified set of machines on which it can be processed, called its eligible set. We consider the most general case of machine eligibility constraints as well as special cases of nested and inclusive eligible sets. Both online and offline models are considered. For offline problems we develop optimal algorithms that run in polynomial time, while for online problems we focus on the development of optimal algorithms of a new and more elaborate structure as well as approximation algorithms with good competitive ratios.

Original language	English (US)
Pages (from-to)	27-38
Number of pages	12
Journal	Journal of Scheduling
Volume	14
Issue number	1
DOIs	https://doi.org/10.1007/s10951-010-0190-0
State	Published - Feb 2011

All Science Journal Classification (ASJC) codes

Software
General Engineering
Management Science and Operations Research
Artificial Intelligence

Keywords

Competitive ratio
Eligibility constraint
Equal-processing-time jobs
Makespan
Nested and inclusive eligible sets
Online and offline scheduling
Parallel machine scheduling
Worst-case ratio

Access to Document

10.1007/s10951-010-0190-0

Cite this

@article{871378aa5bd647ca96622c4820b633b1,

title = "Scheduling jobs with equal processing times subject to machine eligibility constraints",

abstract = "We consider the problem of nonpreemptively scheduling a set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a prespecified set of machines on which it can be processed, called its eligible set. We consider the most general case of machine eligibility constraints as well as special cases of nested and inclusive eligible sets. Both online and offline models are considered. For offline problems we develop optimal algorithms that run in polynomial time, while for online problems we focus on the development of optimal algorithms of a new and more elaborate structure as well as approximation algorithms with good competitive ratios.",

keywords = "Competitive ratio, Eligibility constraint, Equal-processing-time jobs, Makespan, Nested and inclusive eligible sets, Online and offline scheduling, Parallel machine scheduling, Worst-case ratio",

author = "Kangbok Lee and Leung, {Joseph Y.T.} and Pinedo, {Michael L.}",

note = "Funding Information: K. Lee{\textquoteright}s work supported by the Korea Research Foundation Grant KRF-2007-357-D00270. J.Y.-T. Leung{\textquoteright}s work supported in part by NSF Grant DMI-0556010. M.L. Pinedo{\textquoteright}s work supported in part by NSF Grant DMI-0555999.",

year = "2011",

month = feb,

doi = "10.1007/s10951-010-0190-0",

language = "English (US)",

volume = "14",

pages = "27--38",

journal = "Journal of Scheduling",

issn = "1094-6136",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Scheduling jobs with equal processing times subject to machine eligibility constraints

AU - Lee, Kangbok

AU - Leung, Joseph Y.T.

AU - Pinedo, Michael L.

N1 - Funding Information: K. Lee’s work supported by the Korea Research Foundation Grant KRF-2007-357-D00270. J.Y.-T. Leung’s work supported in part by NSF Grant DMI-0556010. M.L. Pinedo’s work supported in part by NSF Grant DMI-0555999.

PY - 2011/2

Y1 - 2011/2

N2 - We consider the problem of nonpreemptively scheduling a set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a prespecified set of machines on which it can be processed, called its eligible set. We consider the most general case of machine eligibility constraints as well as special cases of nested and inclusive eligible sets. Both online and offline models are considered. For offline problems we develop optimal algorithms that run in polynomial time, while for online problems we focus on the development of optimal algorithms of a new and more elaborate structure as well as approximation algorithms with good competitive ratios.

AB - We consider the problem of nonpreemptively scheduling a set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a prespecified set of machines on which it can be processed, called its eligible set. We consider the most general case of machine eligibility constraints as well as special cases of nested and inclusive eligible sets. Both online and offline models are considered. For offline problems we develop optimal algorithms that run in polynomial time, while for online problems we focus on the development of optimal algorithms of a new and more elaborate structure as well as approximation algorithms with good competitive ratios.

KW - Competitive ratio

KW - Eligibility constraint

KW - Equal-processing-time jobs

KW - Makespan

KW - Nested and inclusive eligible sets

KW - Online and offline scheduling

KW - Parallel machine scheduling

KW - Worst-case ratio

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

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

U2 - 10.1007/s10951-010-0190-0

DO - 10.1007/s10951-010-0190-0

M3 - Article

AN - SCOPUS:79952625663

SN - 1094-6136

VL - 14

SP - 27

EP - 38

JO - Journal of Scheduling

JF - Journal of Scheduling

IS - 1

ER -

Scheduling jobs with equal processing times subject to machine eligibility constraints

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this