An approximation algorithm for parallel machine scheduling with a common server

Guoqing Wang; Edwin Tai Chiu Cheng

doi:10.1057/palgrave.jors.2601074

An approximation algorithm for parallel machine scheduling with a common server

Guoqing Wang, Edwin Tai Chiu Cheng

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

26 Citations (Scopus)

Abstract

In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem.

Original language	English
Pages (from-to)	234-237
Number of pages	4
Journal	Journal of the Operational Research Society
Volume	52
Issue number	2
DOIs	https://doi.org/10.1057/palgrave.jors.2601074
Publication status	Published - 1 Jan 2001

Keywords

Approximation algorithm
Parallel machine scheduling
Worst-case analysis

ASJC Scopus subject areas

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

More information

10.1057/palgrave.jors.2601074

Cite this

@article{1bbdce5bcf22472a9183867b0652a359,

title = "An approximation algorithm for parallel machine scheduling with a common server",

abstract = "In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem.",

keywords = "Approximation algorithm, Parallel machine scheduling, Worst-case analysis",

author = "Guoqing Wang and Cheng, {Edwin Tai Chiu}",

year = "2001",

month = jan,

day = "1",

doi = "10.1057/palgrave.jors.2601074",

language = "English",

volume = "52",

pages = "234--237",

journal = "Journal of the Operational Research Society",

issn = "0160-5682",

publisher = "Taylor and Francis Ltd.",

number = "2",

}

TY - JOUR

T1 - An approximation algorithm for parallel machine scheduling with a common server

AU - Wang, Guoqing

AU - Cheng, Edwin Tai Chiu

PY - 2001/1/1

Y1 - 2001/1/1

N2 - In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem.

AB - In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem.

KW - Approximation algorithm

KW - Parallel machine scheduling

KW - Worst-case analysis

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

U2 - 10.1057/palgrave.jors.2601074

DO - 10.1057/palgrave.jors.2601074

M3 - Journal article

SN - 0160-5682

VL - 52

SP - 234

EP - 237

JO - Journal of the Operational Research Society

JF - Journal of the Operational Research Society

IS - 2

ER -

An approximation algorithm for parallel machine scheduling with a common server

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this