On-Line Scheduling Algorithms for a Batch Machine with Finite Capacity

Authors: Poon, Chung¹; Yu, Wenci²

Source: Journal of Combinatorial Optimization, Volume 9, Number 2, March 2005 , pp. 167-186(20)

Publisher: Springer

Buy & download fulltext article:

Price: $47.00 plus tax (Refund Policy)

Abstract:

We study the problem of on-line scheduling jobs with release dates on a batch machine of finite capacity with the objective of minimizing the makespan. We generalize several existing algorithms for the problem to a class of on-line algorithms that are 2-competitive for any arbitrary finite machine capacity. Then, we show that one of these generalized algorithms is in fact 7/4-competitive for machine capacity 2. This is the first on-line algorithm for a finite machine capacity with competitive ratio less than 2.

Keywords: scheduling; batch machine; release time; makespan; on-line

Document Type: Research article

DOI: http://dx.doi.org/10.1007/s10878-005-6855-5

Affiliations: 1: Department of Computer Science, City U. of Hong Kong, China, Email: ckpoon@cs.cityu.edu.hk 2: Institute of Applied Mathematics, East China U. of Science and Technology, China, Email: wcyu@ecust.edu.cn

Publication date: 2005-03-01