Quick Minimization of Tardy Processing Time on a Single Machine

Baruch Schieber, Pranav Sitaraman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of minimizing the total processing time of tardy jobs on a single machine. This is a classical scheduling problem, first considered by [Lawler and Moore 1969], that also generalizes the Subset Sum problem. Recently, it was shown that this problem can be solved efficiently by computing (max, min ) -skewed-convolutions. The running time of the resulting algorithm is the same, up to logarithmic factors, as the time it takes to compute a (max, min ) -skewed-convolution of two vectors of integers whose sum is O(P), where P is the sum of the jobs’ processing times. We further improve the running time of the minimum tardy processing time computation by introducing a job “bundling” technique and achieve a O~(P2-1/α) running time, where O~(Pα) is the running time of a (max, min ) -skewed-convolution of vectors of size P. This results in a O~(P7/5) time algorithm for tardy processing time minimization, an improvement over the previously known O~(P5/3) time algorithm.

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings
EditorsPat Morin, Subhash Suri
PublisherSpringer Science and Business Media Deutschland GmbH
Pages637-643
Number of pages7
ISBN (Print)9783031389054
DOIs
StatePublished - 2023
Event18th International Symposium on Algorithms and Data Structures, WADS 2023 - Montreal, Canada
Duration: Jul 31 2023Aug 2 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14079 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Symposium on Algorithms and Data Structures, WADS 2023
Country/TerritoryCanada
CityMontreal
Period7/31/238/2/23

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • convolution
  • scheduling
  • tardy processing time

Fingerprint

Dive into the research topics of 'Quick Minimization of Tardy Processing Time on a Single Machine'. Together they form a unique fingerprint.

Cite this