An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines

Q. Q. Nong; Edwin Tai Chiu Cheng; Chi To Ng

doi:10.1016/j.orl.2008.03.004

An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines

Q. Q. Nong, Edwin Tai Chiu Cheng, Chi To Ng

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

20 Citations (Scopus)

Abstract

We consider the problem of on-line scheduling a set of n jobs on two parallel batch processing machines. The objective is to minimize the makespan. We provide an algorithm for the problem that is better than one given in the literature, improving the competitive ratio from frac(3, 2) to sqrt(2).

Original language	English
Pages (from-to)	584-588
Number of pages	5
Journal	Operations Research Letters
Volume	36
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2008.03.004
Publication status	Published - 1 Sept 2008

Keywords

Batch
Competitive ratio
On-line scheduling
Parallel machines
Worst-case analysis

ASJC Scopus subject areas

Management Science and Operations Research
Statistics, Probability and Uncertainty
Discrete Mathematics and Combinatorics
Modelling and Simulation

More information

10.1016/j.orl.2008.03.004

http://hdl.handle.net/10397/1267

Cite this

@article{77b7b62785c14d86ab32ed52b938918b,

title = "An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines",

abstract = "We consider the problem of on-line scheduling a set of n jobs on two parallel batch processing machines. The objective is to minimize the makespan. We provide an algorithm for the problem that is better than one given in the literature, improving the competitive ratio from frac(3, 2) to sqrt(2).",

keywords = "Batch, Competitive ratio, On-line scheduling, Parallel machines, Worst-case analysis",

author = "Nong, {Q. Q.} and Cheng, {Edwin Tai Chiu} and Ng, {Chi To}",

year = "2008",

month = sep,

day = "1",

doi = "10.1016/j.orl.2008.03.004",

language = "English",

volume = "36",

pages = "584--588",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines

AU - Nong, Q. Q.

AU - Cheng, Edwin Tai Chiu

AU - Ng, Chi To

PY - 2008/9/1

Y1 - 2008/9/1

N2 - We consider the problem of on-line scheduling a set of n jobs on two parallel batch processing machines. The objective is to minimize the makespan. We provide an algorithm for the problem that is better than one given in the literature, improving the competitive ratio from frac(3, 2) to sqrt(2).

AB - We consider the problem of on-line scheduling a set of n jobs on two parallel batch processing machines. The objective is to minimize the makespan. We provide an algorithm for the problem that is better than one given in the literature, improving the competitive ratio from frac(3, 2) to sqrt(2).

KW - Batch

KW - Competitive ratio

KW - On-line scheduling

KW - Parallel machines

KW - Worst-case analysis

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

U2 - 10.1016/j.orl.2008.03.004

DO - 10.1016/j.orl.2008.03.004

M3 - Journal article

SN - 0167-6377

VL - 36

SP - 584

EP - 588

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

An improved on-line algorithm for scheduling on two unrestrictive parallel batch processing machines

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this