Khandekar, Rohit ;
Hildrum, Kirsten ;
Rajan, Deepak ;
Wolf, Joel
Scheduling with Setup Costs and Monotone Penalties
Abstract
We consider single processor preemptive scheduling with jobdependent setup times. In this model, a jobdependent setup time is incurred when a job is started for the first time, and each time it is restarted after preemption. This model is a common generalization of preemptive scheduling, and actually of nonpreemptive scheduling as well. The objective is to minimize the sum of any general nonnegative, nondecreasing cost functions of the completion times of the jobs  this generalizes objectives of minimizing weighted flow time, flowtime squared, tardiness or the number of tardy jobs among many others. Our main result is a randomized polynomial time O(1)speed O(1)approximation algorithm for this problem. Without speedup, no polynomial time finite multiplicative approximation is possible unless P=NP.
We extend the approach of Bansal et al. (FOCS 2007) of rounding a linear programming relaxation which accounts for costs incurred due to the nonpreemptive nature of the schedule. A key new idea used in the rounding is that a point in the intersection polytope of two matroids can be decomposed as a convex combination of incidence vectors of sets that are independent in both matroids. In fact, we use this for the intersection of a partition matroid and a laminar matroid, in which case the decomposition can be found efficiently using network flows.
Our approach gives a randomized polynomial time offline O(1)speed O(1)approximation algorithm for the broadcast scheduling problem with general cost functions as well.
BibTeX  Entry
@InProceedings{khandekar_et_al:LIPIcs:2012:3857,
author = {Rohit Khandekar and Kirsten Hildrum and Deepak Rajan and Joel Wolf},
title = {{Scheduling with Setup Costs and Monotone Penalties}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
pages = {185198},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897477},
ISSN = {18688969},
year = {2012},
volume = {18},
editor = {Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3857},
URN = {urn:nbn:de:0030drops38576},
doi = {10.4230/LIPIcs.FSTTCS.2012.185},
annote = {Keywords: Scheduling, resource augmentation, approximation algorithm, preemption, setup times}
}
2012
Keywords: 

Scheduling, resource augmentation, approximation algorithm, preemption, setup times 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Issue date: 

2012 
Date of publication: 

2012 