Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Online Scheduling of Equal-Length Jobs on Parallel Machines
| Book Series | Lecture Notes in Computer Science |
| Publisher | Springer Berlin / Heidelberg |
| ISSN | 0302-9743 (Print) 1611-3349 (Online) |
| Volume | Volume 4698/2007 |
| Book | Algorithms – ESA 2007 |
| DOI | 10.1007/978-3-540-75520-3 |
| Copyright | 2007 |
| ISBN | 978-3-540-75519-7 |
| DOI | 10.1007/978-3-540-75520-3_39 |
| Pages | 427-438 |
| Subject Collection | Computer Science |
| SpringerLink Date | Monday, September 17, 2007 |
| |
|
Online Scheduling of Equal-Length Jobs on Parallel Machines
Jihuan Ding1, 2  , Tomáš Ebenlendr3 , Jiří Sgall3 and Guochuan Zhang1
| (1) |
Dept. of Mathematics, Zhejiang Univ., Hangzhou 310027, China |
| (2) |
College of Operations Research and Management Science, Qufu Normal Univ., Rizhao 276826, China |
| (3) |
Institute of Mathematics, AS CR, Žitná 25, CZ-11567 Praha 1, Czech Republic |
Abstract
We study on-line scheduling of equal-length jobs on parallel machines. Our main result is an algorithm with competitive ratio
decreasing to e/( e − 1) ≈ 1.58 as the number of machine increases. For m ≥ 3, this is the first algorithm better than 2-competitive greedy algorithm.
Our algorithm has an additional property called immediate decision: at each time, it is immediately decided for each newly released job if it will be scheduled, and if so, then also the time
interval and machine where it is scheduled is fixed and cannot be changed later. We show that for two machines, no deterministic
algorithm with immediate decision is better than 1.8-competitive; this lower bound shows that our algorithm is optimal for
m = 2 in this restricted model. We give some additional lower bounds for algorithms with immediate decision.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|