The Library
On-line scheduling a batch processing system to minimize total weighted job completion time
Tools
UNSPECIFIED (2001) On-line scheduling a batch processing system to minimize total weighted job completion time. In: 12th Annual International Symposium on Algorithms and Computation, CHRISTCHURCH, NEW ZEALAND, DEC 19-21, 2001. Published in: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2223 pp. 380-389. ISBN 3-540-42985-9. ISSN 0302-9743.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
Scheduling a batch processing system has been extensively studied in the last decade. A batch processing system is modelled as a machine that can process up to b jobs simultaneously as a batch. The scheduling problem involves assigning all n jobs to batches and determining the batch sequence in such a way that certain objective function of job completion times C-j is minimized. In this paper, we address the scheduling problem under the on-line setting in the sense that we construct our schedule irrevocably as time proceeds and do not know of the existence of any job that may arrive later. Our objective is to minimize the total weighted completion time Sigma w(j)C(j). We provide a linear time on-line algorithm for the unrestrictive model (i.e., b greater than or equal to n) and show that the algorithm is 10/3-competitive. For the restrictive model (i.e., b < n), we first consider the (off-line) problem of finding a maximum independent vertex set in an interval graph with cost constraint (MISCP), which is NP-hard. We give a dual fully polynomial time approximation scheme for MISCP, which leads us to a (4 + epsilon)-competitive on-line algorithm for any epsilon > 0 for the original on-line scheduling problem. These two on-line algorithms are the first deterministic algorithms of constant performance guarantees.
Item Type: | Conference Item (UNSPECIFIED) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
Journal or Publication Title: | ALGORITHMS AND COMPUTATION, PROCEEDINGS | ||||
Publisher: | SPRINGER-VERLAG BERLIN | ||||
ISBN: | 3-540-42985-9 | ||||
ISSN: | 0302-9743 | ||||
Editor: | Eades, P and Takaoka, T | ||||
Official Date: | 2001 | ||||
Dates: |
|
||||
Volume: | 2223 | ||||
Number of Pages: | 10 | ||||
Page Range: | pp. 380-389 | ||||
Publication Status: | Published | ||||
Title of Event: | 12th Annual International Symposium on Algorithms and Computation | ||||
Location of Event: | CHRISTCHURCH, NEW ZEALAND | ||||
Date(s) of Event: | DEC 19-21, 2001 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |