Approximation Algorithms in Batch Processing

Xiaotie Deng; Chung Keung Poon; Yuzhong Zhang

doi:10.1023/A:1027316504440

Approximation Algorithms in Batch Processing

Xiaotie Deng
, Chung Keung Poon
, Yuzhong Zhang

Department of Computer Science

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

81 Citations (Scopus)

Abstract

A polynomial approximation scheme for minimizing makespan in a batch processing system under dynamic job arrivals is presented. A lower bound of (√5 +1)/2 on the competitive ratio of any on-line algorithm is proved. This is matched by an on-line algorithm for the special case of unbounded machine capacity.
© 2003 Kluwer Academic Publishers

Original language	English
Pages (from-to)	247-257
Journal	Journal of Combinatorial Optimization
Volume	7
Issue number	3
DOIs	https://doi.org/10.1023/A:1027316504440
Publication status	Published - Sept 2003

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Funding

This research is supported by a grant from the Research Grants Council of the Hong Kong SAR (Project No. CityU 1074/00E), a grant from City University of Hong Kong (Project No. 7001119), a grant from NSF China and Shandong and the Grant of Young and Middle-aged Scientists in Shandong, China.

Research Keywords

Batch
Makespan
On-line
Release time
Scheduling

RGC Funding Information

RGC-funded

Access Output

10.1023/A:1027316504440

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{1c97c863a383452d971e1b003a83c9a5,

title = "Approximation Algorithms in Batch Processing",

abstract = "A polynomial approximation scheme for minimizing makespan in a batch processing system under dynamic job arrivals is presented. A lower bound of (√5 +1)/2 on the competitive ratio of any on-line algorithm is proved. This is matched by an on-line algorithm for the special case of unbounded machine capacity. {\textcopyright} 2003 Kluwer Academic Publishers",

keywords = "Batch, Makespan, On-line, Release time, Scheduling",

author = "Xiaotie Deng and Poon, \{Chung Keung\} and Yuzhong Zhang",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "2003",

month = sep,

doi = "10.1023/A:1027316504440",

language = "English",

volume = "7",

pages = "247--257",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Approximation Algorithms in Batch Processing

AU - Deng, Xiaotie

AU - Poon, Chung Keung

AU - Zhang, Yuzhong

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 2003/9

Y1 - 2003/9

N2 - A polynomial approximation scheme for minimizing makespan in a batch processing system under dynamic job arrivals is presented. A lower bound of (√5 +1)/2 on the competitive ratio of any on-line algorithm is proved. This is matched by an on-line algorithm for the special case of unbounded machine capacity. © 2003 Kluwer Academic Publishers

AB - A polynomial approximation scheme for minimizing makespan in a batch processing system under dynamic job arrivals is presented. A lower bound of (√5 +1)/2 on the competitive ratio of any on-line algorithm is proved. This is matched by an on-line algorithm for the special case of unbounded machine capacity. © 2003 Kluwer Academic Publishers

KW - Batch

KW - Makespan

KW - On-line

KW - Release time

KW - Scheduling

UR - https://www.scopus.com/pages/publications/0344443737

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0344443737&origin=recordpage

U2 - 10.1023/A:1027316504440

DO - 10.1023/A:1027316504440

M3 - RGC 21 - Publication in refereed journal

SN - 1382-6905

VL - 7

SP - 247

EP - 257

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 3

ER -

Approximation Algorithms in Batch Processing

Abstract

Bibliographical note

Funding

Research Keywords

RGC Funding Information

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this