Please use this identifier to cite or link to this item:
Title: Reallocation problems in scheduling
Authors: A.Bender, M.
Farach-Colton, M.
Fekete, S.R.
Fineman, J.T.
Gilbert, S. 
Keywords: Online problems
Issue Date: 2013
Source: A.Bender, M.,Farach-Colton, M.,Fekete, S.R.,Fineman, J.T.,Gilbert, S. (2013). Reallocation problems in scheduling. Annual ACM Symposium on Parallelism in Algorithms and Architectures : 271-279. ScholarBank@NUS Repository.
Abstract: In traditional on-line problems, such as scheduling, requests arrive over time, demanding available resources. As each request arrives, some resources may have to be irrevocably committed to servicing that request. In many situations, however, it may be possible or even necessary to reallocate previously allocated resources in order to satisfy a new request. This reallocation has a cost. This paper shows how to service the requests while minimizing the reallocation cost. We focus on the classic problem of scheduling jobs on a multiprocessor system. Each unit-size job has a time window in which it can be executed. Jobs are dynamically added and removed from the system. We provide an algorithm that maintains a valid schedule, as long as a sufficiently feasible schedule exists. The algorithm reschedules only O(min{log*n, log*A}) jobs for each job that is inserted or deleted from the system, where n is the number of active jobs and △ is the size of the largest window. © 2013 ACM.
Source Title: Annual ACM Symposium on Parallelism in Algorithms and Architectures
ISBN: 9781450315722
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Feb 17, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.