2005, English, Article edition: On-line Time-Constrained Scheduling Problem for the Size on k machines Thibault, Nicolas; Laforest, Christian

User activity

Share to:
 
Bookmark: http://trove.nla.gov.au/version/209678
Physical Description
  • text
Published
  • HAL - CCSD
  • 2005
Language
  • English

Edition details

Title
  • On-line Time-Constrained Scheduling Problem for the Size on k machines
Author
  • Thibault, Nicolas
  • Laforest, Christian
Published
  • HAL - CCSD
  • 2005
Physical Description
  • text
Subjects
Notes
  • 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.
  • HAL:hal-00341386, version 1
  • HAL:http:/​/​hal.archives-ouvertes.fr/​hal-00341386/​en/​
  • DOI:10.1109/​ISPAN.2005.65
Language
  • English
Contributed by
OAIster

Get this edition

  • Set up My libraries

    How do I set up "My libraries"?

    In order to set up a list of libraries that you have access to, you must first login or sign up. Then set up a personal list of libraries from your profile page by clicking on your user name at the top right of any screen.

  • All (1)
  • Unknown (1)
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.
None of your libraries hold this item.

User activity


e.g. test cricket, Perth (WA), "Parkes, Henry"

Separate different tags with a comma. To include a comma in your tag, surround the tag with double quotes.

Be the first to add a tag for this edition

Be the first to add this to a list

Comments and reviews

What are comments? Add a comment

No user comments or reviews for this version

Add a comment