2026-07-23T04:16:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3857 2024-03-06T10:34:32Z ddc:004 open_access

Scheduling with Setup Costs and Monotone Penalties Khandekar, Rohit Hildrum, Kirsten Rajan, Deepak Wolf, Joel Scheduling resource augmentation approximation algorithm preemption setup times We consider single processor preemptive scheduling with job-dependent setup times. In this model, a job-dependent 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 non-preemptive scheduling as well. The objective is to minimize the sum of any general non-negative, non-decreasing cost functions of the completion times of the jobs -- this generalizes objectives of minimizing weighted flow time, flow-time 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 non-preemptive 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rohit Khandekar and Kirsten Hildrum and Deepak Rajan and Joel Wolf 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.185 urn:nbn:de:0030-drops-38576 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.185 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode