Server scheduling on parallel dedicated machines with fixed job sequences

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

doi:10.1002/nav.21846

Server scheduling on parallel dedicated machines with 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

10 Citations (Scopus)

Abstract

We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial-time algorithm to solve the two-machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP-hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.

Original language	English
Pages (from-to)	321-332
Number of pages	12
Journal	Naval Research Logistics
Volume	66
Issue number	4
DOIs	https://doi.org/10.1002/nav.21846
Publication status	Published - Jun 2019

Keywords

fixed job sequence
makespan
parallel dedicated machines
single server

ASJC Scopus subject areas

Modelling and Simulation
Ocean Engineering
Management Science and Operations Research

More information

10.1002/nav.21846

Cite this

@article{a3bce64295054088a1a23efb87ef2db9,

title = "Server scheduling on parallel dedicated machines with fixed job sequences",

abstract = "We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial-time algorithm to solve the two-machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP-hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.",

keywords = "fixed job sequence, makespan, parallel dedicated machines, single server",

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

year = "2019",

month = jun,

doi = "10.1002/nav.21846",

language = "English",

volume = "66",

pages = "321--332",

journal = "Naval Research Logistics",

issn = "0894-069X",

publisher = "John Wiley & Sons Inc.",

number = "4",

}

TY - JOUR

T1 - Server scheduling on parallel dedicated machines with fixed job sequences

AU - Cheng, T. C.E.

AU - Kravchenko, Svetlana A.

AU - Lin, Bertrand M.T.

PY - 2019/6

Y1 - 2019/6

N2 - We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial-time algorithm to solve the two-machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP-hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.

AB - We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial-time algorithm to solve the two-machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP-hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.

KW - fixed job sequence

KW - makespan

KW - parallel dedicated machines

KW - single server

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

U2 - 10.1002/nav.21846

DO - 10.1002/nav.21846

M3 - Journal article

AN - SCOPUS:85065020012

SN - 0894-069X

VL - 66

SP - 321

EP - 332

JO - Naval Research Logistics

JF - Naval Research Logistics

IS - 4

ER -

Server scheduling on parallel dedicated machines with fixed job sequences

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this