Quick minimization of tardy processing time on a single machine

DOI10.1007/978-3-031-38906-1_42MaRDI QIDQ6139045zbMATH OpenOpenAlexFDO

Authors Baruch Schieber, Pranav Sitaraman

Publication date 16 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.05460

zbMATH Keywords

convolutionschedulingtardy processing time

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

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 equivalent, up to logarithmic factors, to 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 $ildeOleft(P^{2-1/alpha}ight)$ running time, where $ildeOleft(P^{a}lphaight)$ is the running time of a $(max,min)$-skewed-convolution of vectors of size $P$. This results in a $ildeOleft(P^{7/5}ight)$ time algorithm for tardy processing time minimization, an improvement over the previously known $ildeOleft(P^{5/3}ight)$ time algorithm.

Cites work

• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Faster minimization of tardy processing time on a single machine
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)

Cited in

(6)

• Minimizing tardy processing time on a single machine in near-linear time
• Minimizing tardy processing time on a single machine in near-linear time
• Minimizing the weighted number of tardy jobs is W[1]-hard
• Single-machine scheduling to minimize the number of tardy jobs with release dates
• Minimizing the number of tardy jobs with uniform processing times on parallel machines
• Minimizing the weighted number of tardy jobs is W[1]-hard

This page was built for publication: Quick minimization of tardy processing time on a single machine

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139045)