loading...
On-line Time-Constrained Scheduling Problem for the Size on \kappa machines
Las Vegas, Nevada, USA December 07-December 09
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.658th International Symposium on Parall ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Nicolas Thibault, Universite d' Evry, France
Christian Laforest, Universite d' Evry, France
In this paper we consider the problem of scheduling online jobs on \kappa identical machines. Technically, our system is composed of \kappa identical machines and each job is defined by a triplet r = (l,r,p) where l denotes its left border, its right border and p its length. When a job is revealed, it can be rejected or scheduled on one of the \kappa machines In this last case, it can suppress already scheduled jobs. The goal is to maximize the size of the schedule (i.e. the number of jobs scheduled and not (later) suppressed). We propose an algorithm called OLUW.It is (4\min (\beta ,\left\lfloor {Log_2 (\gamma )} \right\rfloor + 1)) competitive, where \beta is the number of different job lengths appearing in the on-line input sequence and \gamma is the ratio between the length of the longest job and the length of the shortest job in the sequence. To the best of our knowledge, OLUW is the first on-line algorithm maximizing the size with guarantees on the competitive ratio for the timeconstrained scheduling problem on \kappa machines.
Citation:
Nicolas Thibault, Christian Laforest, "On-line Time-Constrained Scheduling Problem for the Size on \kappa machines," ispan, pp.20-24, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.