Citation
Scheduling On A Single Machine To Minimize Total Flow Time With Job Rejections. In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA, pages 562-572, 2005.
Paper
Abstract
We consider the problem of minimizing flow time on a single machine supporting preemption that can reject jobs at a cost. Even if all jobs have the same rejection cost, we show that no online algorithm can have competitive ratio better than (2 + SQRT(2))/2 ~= 1.707 in general or e/(e-1) ~= 1.582 if all jobs are known to have the same processing time. We also give an optimal offline algorithm for unit-length jobs with arbitrary rejection costs. This leads to a pair of 2-competitive online algorithms for unit-length jobs, one when all rejection costs are equal and one when they are arbitrary. Finally, we show that the offline problem is NP-hard even when each job’s rejection cost is proportional to its processing time.
You can download the pdf of this publication from here
doi
This publication does not have a doi, so we cannot provide a link to the original source
What is a doi?: A doi (Document Object Identifier) is a unique identifier for sicientific papers (and occasionally other material). This provides direct access to the location where the original article is published using the URL http://dx.doi/org/xxxx (replacing xxx with the doi). See http://dx.doi.org/ for more information
URL
This pubication does not have a URL associated with it.
The URL is only provided if there is additional information that might be useful. For example, where the entry is a book chapter, the URL might link to the book itself.
Bibtex
@INPROCEEDINGS{2005-562-572-P, author = {D. P. Bunde},
title = {Scheduling On A Single Machine To Minimize Total Flow Time With Job Rejections},
booktitle = {In proceedings of the 2nd Multidisciplinary International Conference on Scheduling : Theory and Applications (MISTA 2005), 18 -21 July 2005, New York, USA},
year = {2005},
editor = {G. Kendall and L. Lei and M. Pinedo},
pages = {562--572},
note = {Paper},
abstract = {We consider the problem of minimizing flow time on a single machine supporting preemption that can reject jobs at a cost. Even if all jobs have the same rejection cost, we show that no online algorithm can have competitive ratio better than (2 + SQRT(2))/2 ~= 1.707 in general or e/(e-1) ~= 1.582 if all jobs are known to have the same processing time. We also give an optimal offline algorithm for unit-length jobs with arbitrary rejection costs. This leads to a pair of 2-competitive online algorithms for unit-length jobs, one when all rejection costs are equal and one when they are arbitrary. Finally, we show that the offline problem is NP-hard even when each job’s rejection cost is proportional to its processing time.},
owner = {Faizah Hamdan},
timestamp = {2012.05.21},
webpdf = {2005-562-572-P.pdf} }