Complexity of server scheduling on parallel dedicated machines subject to fixed job sequences

T. C.E. Cheng; Svetlana A. Kravchenko; Bertrand M.T. Lin

doi:10.1080/01605682.2020.1779625

Complexity of server scheduling on parallel dedicated machines subject to fixed job sequences

T. C.E. Cheng, Svetlana A. Kravchenko, Bertrand M.T. Lin

Research output: Journal article publication › Journal article › Academic research › peer-review

2 Citations (Scopus)

Abstract

We study server scheduling on parallel dedicated machines to minimize the makespan subject to given processing sequences. Before a job starts its processing on its designated machine, a loading operation must be performed, which is undertaken by a server shared by all the jobs. While the two-machine problem is polynomially solvable, we show that the problem becomes binary NP-hard when the number of machines is three, and propose a pseudo-polynomial algorithm to solve the problem with a constant number of machines.

Original language	English
Journal	Journal of the Operational Research Society
DOIs	https://doi.org/10.1080/01605682.2020.1779625
Publication status	Accepted/In press - 2020

Keywords

complexity
dynamic programming
fixed job sequence
makespan
Parallel machines
single server

ASJC Scopus subject areas

Management Information Systems
Strategy and Management
Management Science and Operations Research
Marketing

More information

10.1080/01605682.2020.1779625

Cite this

@article{69c4dc43aae94d6798ae6143108198bf,

title = "Complexity of server scheduling on parallel dedicated machines subject to fixed job sequences",

abstract = "We study server scheduling on parallel dedicated machines to minimize the makespan subject to given processing sequences. Before a job starts its processing on its designated machine, a loading operation must be performed, which is undertaken by a server shared by all the jobs. While the two-machine problem is polynomially solvable, we show that the problem becomes binary NP-hard when the number of machines is three, and propose a pseudo-polynomial algorithm to solve the problem with a constant number of machines.",

keywords = "complexity, dynamic programming, fixed job sequence, makespan, Parallel machines, single server",

author = "Cheng, {T. C.E.} and Kravchenko, {Svetlana A.} and Lin, {Bertrand M.T.}",

year = "2020",

doi = "10.1080/01605682.2020.1779625",

language = "English",

journal = "Journal of the Operational Research Society",

issn = "0160-5682",

publisher = "Palgrave Macmillan Ltd.",

}

TY - JOUR

T1 - Complexity of server scheduling on parallel dedicated machines subject to fixed job sequences

AU - Cheng, T. C.E.

AU - Kravchenko, Svetlana A.

AU - Lin, Bertrand M.T.

PY - 2020

Y1 - 2020

N2 - We study server scheduling on parallel dedicated machines to minimize the makespan subject to given processing sequences. Before a job starts its processing on its designated machine, a loading operation must be performed, which is undertaken by a server shared by all the jobs. While the two-machine problem is polynomially solvable, we show that the problem becomes binary NP-hard when the number of machines is three, and propose a pseudo-polynomial algorithm to solve the problem with a constant number of machines.

AB - We study server scheduling on parallel dedicated machines to minimize the makespan subject to given processing sequences. Before a job starts its processing on its designated machine, a loading operation must be performed, which is undertaken by a server shared by all the jobs. While the two-machine problem is polynomially solvable, we show that the problem becomes binary NP-hard when the number of machines is three, and propose a pseudo-polynomial algorithm to solve the problem with a constant number of machines.

KW - complexity

KW - dynamic programming

KW - fixed job sequence

KW - makespan

KW - Parallel machines

KW - single server

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

U2 - 10.1080/01605682.2020.1779625

DO - 10.1080/01605682.2020.1779625

M3 - Journal article

AN - SCOPUS:85088956871

JO - Journal of the Operational Research Society

JF - Journal of the Operational Research Society

SN - 0160-5682

ER -

Complexity of server scheduling on parallel dedicated machines subject to fixed job sequences

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this