A QPTAS for the general scheduling problem with identical release dates

Antonios Antoniadis, Ruben Hoeksma, Julie Meißner, José Verschae, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)
8 Downloads (Pure)

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(log log P)-approximation (where P denotes the range of the job processing times), while the best lower bound shows only strong NP-hardness. When release dates are identical there is also a gap: the problem remains strongly NP-hard and the best known approximation algorithm has a ratio of e+ϵ (running in quasi-polynomial time). We reduce the latter gap by giving a QPTAS if the numbers in the input are quasi-polynomially bounded, ruling out the existence of an APX-hardness proof unless NP ⊆ DTIME(2polylog(n)). Our techniques are based on the QPTAS known for the UFP-Cover 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 UFP-Cover and use a sophisticated divide-and-conquer procedure with interdependent non-symmetric subproblems. We also present a pseudo-polynomial 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.

Original languageEnglish
Title of host publication44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
EditorsAnca Muscholl, Piotr Indyk, Fabian Kuhn, Ioannis Chatzigiannakis
PublisherDagstuhl
Pages31:1-31:14
Number of pages14
ISBN (Electronic)9783959770415
DOIs
Publication statusPublished - 1 Jul 2017
Externally publishedYes
Event44th International Colloquium on Automata, Languages, and Programming, ICALP 2017 - Warsaw, Poland
Duration: 10 Jul 201714 Jul 2017
Conference number: 44

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherDagstuhl
Volume80
ISSN (Print)1868-8969

Conference

Conference44th International Colloquium on Automata, Languages, and Programming, ICALP 2017
Abbreviated titleICALP 2017
Country/TerritoryPoland
CityWarsaw
Period10/07/1714/07/17

Keywords

  • Generalized Scheduling
  • QPTAS
  • Unsplittable flows

Fingerprint

Dive into the research topics of 'A QPTAS for the general scheduling problem with identical release dates'. Together they form a unique fingerprint.

Cite this