Approximation Algorithms in Batch Processing

Xiaotie Deng (), Chung Keung Poon () and Yuzhong Zhang ()
Additional contact information
Xiaotie Deng: City University of Hong Kong
Chung Keung Poon: City University of Hong Kong
Yuzhong Zhang: Qufu Normal University

Journal of Combinatorial Optimization, 2003, vol. 7, issue 3, No 4, 247-257

Abstract: Abstract A polynomial approximation scheme for minimizing makespan in a batch processing system under dynamic job arrivals is presented. A lower bound of $${{(\sqrt 5 + 2)} \mathord{\left/ {\vphantom {{(\sqrt 5 + 2)} 2}} \right. \kern-\nulldelimiterspace} 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.

Keywords: scheduling; batch; release time; makespan; on-line (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://link.springer.com/10.1023/A:1027316504440 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:7:y:2003:i:3:d:10.1023_a:1027316504440

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1027316504440

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().