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

Authors: Poon, Chung1; Yu, Wenci2

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

Publisher: Springer

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content

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: 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

The full text electronic article is available for purchase. You will be able to download the full text electronic article after payment.

$47.00 plus tax      Refund Policy

 

OR

Back to top

Key:
Free Content - Free Content
New Content - New Content
Subscribed Content - Subscribed Content
Free Trial Content - Free Trial Content
Share this item with others: These icons link to social bookmarking sites where readers can share and discover new web pages.
Page Help Click here for Page Help
Shopping cart
Tools
Sign in






Need to register?
Sign up here
Text size: A | A | A | A