TY - GEN

T1 - Quick Minimization of Tardy Processing Time on a Single Machine

AU - Schieber, Baruch

AU - Sitaraman, Pranav

N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2023.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - convolution

KW - scheduling

KW - tardy processing time

UR - http://www.scopus.com/inward/record.url?scp=85172733877&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85172733877&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-38906-1_42

DO - 10.1007/978-3-031-38906-1_42

M3 - Conference contribution

AN - SCOPUS:85172733877

SN - 9783031389054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 637

EP - 643

BT - Algorithms and Data Structures - 18th International Symposium, WADS 2023, Proceedings

A2 - Morin, Pat

A2 - Suri, Subhash

PB - Springer Science and Business Media Deutschland GmbH

T2 - 18th International Symposium on Algorithms and Data Structures, WADS 2023

Y2 - 31 July 2023 through 2 August 2023

ER -