Antoniadis, Antonios ;
Hoeksma, Ruben ;
Meißner, Julie ;
Verschae, José ;
Wiese, Andreas
A QPTAS for the General Scheduling Problem with Identical Release Dates
Abstract
The General Scheduling Problem (GSP) generalizes scheduling problems with sum of cost objectives such as weighted flow time and weighted tardiness. Given a set of jobs with processing times, release dates, and job dependent cost functions, we seek to find a minimum cost preemptive schedule on a single machine. The best known algorithm for this problem and also for weighted flow time/tardiness is an O(loglog P)approximation (where P denotes the range of the job processing times), while the best lower bound shows only strong NPhardness. When release dates are identical there is also a gap: the problem remains strongly NPhard and the best known approximation algorithm has a ratio of e+\epsilon (running in quasipolynomial time). We reduce the latter gap by giving a QPTAS if the numbers in the input are quasipolynomially bounded, ruling out the existence of an APXhardness proof unless NP\subseteq DTIME(2^polylog(n)). Our techniques are based on the QPTAS known for the UFPCover problem, a particular case of GSP where we must pick a subset of intervals (jobs) on the real line with associated heights and costs. If an interval is selected, its height will help cover a given demand on any point contained within the interval. We reduce our problem to a generalization of UFPCover and use a sophisticated divideandconquer procedure with interdependent nonsymmetric subproblems.
We also present a pseudopolynomial time approximation scheme for two variants of UFPCover. For the case of agreeable intervals we give an algorithm based on a new dynamic programming approach which might be useful for other problems of this type. The second one is a resource augmentation setting where we are allowed to slightly enlarge each interval.
BibTeX  Entry
@InProceedings{antoniadis_et_al:LIPIcs:2017:7457,
author = {Antonios Antoniadis and Ruben Hoeksma and Julie Mei{\ss}ner and Jos{\'e} Verschae and Andreas Wiese},
title = {{A QPTAS for the General Scheduling Problem with Identical Release Dates}},
booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
pages = {31:131:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770415},
ISSN = {18688969},
year = {2017},
volume = {80},
editor = {Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7457},
URN = {urn:nbn:de:0030drops74575},
doi = {10.4230/LIPIcs.ICALP.2017.31},
annote = {Keywords: Generalized Scheduling, QPTAS, Unsplittable Flows}
}
2017
Keywords: 

Generalized Scheduling, QPTAS, Unsplittable Flows 
Seminar: 

44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Issue date: 

2017 
Date of publication: 

2017 